Fórum Root.cz
Hlavní témata => Software => Téma založeno: Randolf 31. 07. 2013, 18:02:41
-
Ahoj,
v kartezkem prostoru mam spoustu (1G) bodu. Potrebuji efektivni indexovaci mechanismus ktery umozni vyhledat vsechny pary s konkretni vzajemnou vzdalenosti (normalni L2 norma, euklidovska vzdalenost). Tedy ne k-nn problem ani nic podobneho, nejedna se dotaz ke konkretnimu bodu.
Vygenerovat brute-force index vzajemnych vzdalenosti kvuli velikosti neni prakticke (1G^2/2 je uz trosku velke :])
Nejake napady?
Za reseni vedouci k odhaleni postupu nabizim pivo pro jednoho co hrdlo raci v prubehu jednoho vecera :D
Diky!
-
no PostgreSQL s nějakým prostorovým rozšířením by na to měla být jako dělaná :)
-
no PostgreSQL s nějakým prostorovým rozšířením by na to měla být jako dělaná :)
Bohuzel, R-tree ani GIST ktere postgre pouziva neumi tento typ dotazu. Jasne, ze PostgreSQL je dobra volba, ale neresi to tu fundamentalni otazku, jak resit ne vzdalenost k jednomu bodu, ale mezi dvema libovolnymi body.
Presto diky :)
Ondra
-
Nedá se o těch datech a dotazovaných vzdálenostech nedá říct nic bližšího? Šlo by to rozdělit na kvadranty "vhodně zvolené velikosti", pak jít po kvadrantech, a spočítat si, ve kterých kvadrantech má smysl pro hledanou vzdálenost hledat body, a v nich pak hledat a porovnávat konkrétní body.
Nebo jestli to není overkill, tak použít http://en.wikipedia.org/wiki/Quadtree. Což by odpovídalo na otázku "jak vhodně zvolit velikost kvadrantu".
-
Pár postřehů:
1) pro člověka, který má ještě natolik funkční mozek, aby to vymyslel, není obávám se pivní opice přitažlivá odměna
2) problém je imho natolik speciální, že nebude existovat hotové obecné řešení v mainstreem db a je třeba řešit nejprve matematicky. Takže bych asi doporučil zkusit i nějaký server, kde se scházejí matematici ;-)
3) pro řešení bude myslím podstatné i to, jestli ta konkrétní dotazovaná vzájemná vzdálenost může být i podstatně větší než typická vzdálenost nejbližších bodů ve vzorku.
4) pokud to vezmu doslovně (konkrétní! vzdálenost), tedy nikoliv vzdálenost v intervalu, půjde to roztřídit možná i nikoliv geometricky, ale numericky na základě nějakého vztahu v hodnotách souřadnic.
-
No ja si myslim, ze takovy index asi nebude, protoze znalost vzdalenosti musis mit nekde ulozenou a to asi bude ta velikost co popisujes.
Ja bych si nejdrive problem zjednodusil na jednodimenzialni problem. Ten bych resil tak, ze bych si vybral kandidaty tim zpusobem, ze bych jel plovoucim oknem pres serazene hodnoty, kde velikost plovouciho okna by byla jako tebou hledana vzdalenost. Vypocet v tomto okne muzes delat budto v krajnich bodech (presna vzdalenost), nebo i v nejake oblasti okolo (+- 5 metru).
Presto je narocnost O(N), protoze to musis jednou projit.
Pro dve dimenze musis efektivne vyhledavat oblasti o velikosti tohoto okna. Myslim, ze navrhovany octtree by sel pouzit. Proste si najdes nadctverec, ktery je dvakrat vetsi nez tvou hledany ctverec a v nem po profiltrovani nemoznych kombinaci, provedes euklidovskou vzdalenost.
Tady bude narocnost podle me O(N*k), kde k je prumerny pocet bodu v tom ctverci bez nesmyslnych vraiant (cim vetsi vzdalenost tim hure).
Kazdopadne bych urcite pouzil rucne napsane reseni. A ne nejakou SQL databazi. 1G bodu muzes nacpat celou do pameti uz prostorove zaindexovane a budes mit rychlost uplne jinde. Stejne budes muset prochazet vse a tudiz to v pameti byt uz muze.
Kdybys nastinil k cemu to potrebujes, mozna by se naslo uplne jine reseni nez vsechny kombinace vzdalenosti...
-
Nechce se mi nad tím moc přemýšlet, ale jako schůdná cesta se mi jeví nasypat data do k-d tree:
https://en.wikipedia.org/wiki/K-d_tree
pak celý prostor rozdělit na (vzájemně se překrývající) podprostory požadované velikosti, ve který se najdou body pomocí range search, což umí k-d tree efektivně:
www.cs.utah.edu/~lifeifei/cs6931/kdtree.pdf
a potom jen vyfiltrovat duplicity.
-
Kdybys nastinil k cemu to potrebujes, mozna by se naslo uplne jine reseni nez vsechny kombinace vzdalenosti...
Tak ono trochu napovi ta euklidovska L2. Takze to bude spis nekde oklo gis/big data swarmu a naopak vypada ze hry porovnavani obrazu. A taky z toho vypadava, ze sem prisel matematik a odkazovat zpatky odkud ocividne prisel je trosku mimo.
-
Prisel jsem trosku pozde, takze muzu jen podporit gamera - kd tree je na tohle velmi dobry. Sam jsem obdobnou ulohu potreboval resit ve sve bakalarce cca 5 let zpatky, tehdy mi takovy dotaz na 1e6 prvcich trval radove vteriny.
Principielne by mela stacit libovolna struktura pro prostorove vyhledavani, ktera obsahuje nejake informace o pozici - tj. quadtree (octree v 3D prostoru), kd-tree (libovolne dimenzionalni prostor), vicerozmerna mrizka (ta by mohla byt skoro nejjednodussi vzhledem, pokud jsem dobre pochopil, k jednotne vzdalenosti, do ktere se vyhledava). Ne zcela vhodny je R-tree (efektivne n-dimenzionalni B-tree). Hodne stesti!
-
Jeste dodam k tomu "radove vteriny" - radove vteriny to bylo samozrejme pro dotaz provedeny postupne na vsech bodech.
-
Kdybys nastinil k cemu to potrebujes, mozna by se naslo uplne jine reseni nez vsechny kombinace vzdalenosti...
Tak ono trochu napovi ta euklidovska L2. Takze to bude spis nekde oklo gis/big data swarmu a naopak vypada ze hry porovnavani obrazu. A taky z toho vypadava, ze sem prisel matematik a odkazovat zpatky odkud ocividne prisel je trosku mimo.
Aha, tak ja tam stale nic nevidim. L2 je jen nazev pro vzdalenost bodu, ne? Take jsem ho nikam neposilal zpatky. Jen rikam, ze nekdy je reseni tam kde se nehleda. Kazdopadne odpoved tohoto vlakna asi je, ze tu nikdo nevi jak by to slo indexovat. Proste se to musi vypocitat. Otazka je uz jen jak rychle, ale to uz je jiny pribeh. Mozna bych zvazil hybridni zpusob, t.j. zaindexovat jen pro vzdalenosti, ktere se budou pouzivat velmi casto (nebo ty co byly prave vypocitany - cache) a zbytek holt pocitat.
-
Dopr... o čem to tady mluvíte? :o
-
Nedá se o těch datech a dotazovaných vzdálenostech nedá říct nic bližšího? Šlo by to rozdělit na kvadranty "vhodně zvolené velikosti", pak jít po kvadrantech, a spočítat si, ve kterých kvadrantech má smysl pro hledanou vzdálenost hledat body, a v nich pak hledat a porovnávat konkrétní body.
Nebo jestli to není overkill, tak použít http://en.wikipedia.org/wiki/Quadtree. Což by odpovídalo na otázku "jak vhodně zvolit velikost kvadrantu".
Jo, R-tree, konkretne octree, samozrejme hodne zrychli vyhledani vsech bodu ktere jsou v urcite vzdalenosti od daneho jednoho. To je jasne. Bohuzel, ja potrebuju vsechny pary takovych bodu z celeho prostoru. Takze to bude mit slozitost cca O(n log n) kdyz uvazuju rovnomerne rozlozeni bodu v prostoru, coz je docela dost... chtel bych se vyhnout nutnosti prochazet body jeden po druhem a hledat k nim parove body.
-
Kazdopadne odpoved tohoto vlakna asi je, ze tu nikdo nevi jak by to slo indexovat.
PostgreSQL umí k-d tree index. Nevím ale, jestli má taky nějaké operátory, kterými se dá udělat range search, nikdy jsem to v databázi nepotřeboval řešit.
-
Pár postřehů:
1) pro člověka, který má ještě natolik funkční mozek, aby to vymyslel, není obávám se pivní opice přitažlivá odměna
2) problém je imho natolik speciální, že nebude existovat hotové obecné řešení v mainstreem db a je třeba řešit nejprve matematicky. Takže bych asi doporučil zkusit i nějaký server, kde se scházejí matematici ;-)
3) pro řešení bude myslím podstatné i to, jestli ta konkrétní dotazovaná vzájemná vzdálenost může být i podstatně větší než typická vzdálenost nejbližších bodů ve vzorku.
4) pokud to vezmu doslovně (konkrétní! vzdálenost), tedy nikoliv vzdálenost v intervalu, půjde to roztřídit možná i nikoliv geometricky, ale numericky na základě nějakého vztahu v hodnotách souřadnic.
:)
Ad 1) To bylo mineno napul jako zert (prestoze mysleny vazne) - spis bych si pak s takovym clovekem rad pokecal
Ad 2) To je dobry napad, zkusim se po nejakych kouknout.
Ad 3) Nejblizsi body ve vzorku radove nekolik jednotek (e.g. metru), dotazovana vzdalenost cca 1-1000 jednotek, muze byt i diskretni (integer)... hmm... co indexovat u bodu histogramy okolnich bodu a potom hledat jen v tech co maji v urcitem binu histogramu nenulovou hodnotu?? Heeej! Dik za nakopnuti :)
Ad 4) Jedna se o hodnotu se znamou kovarianci (nepresnosti) - tedy interval
-
No ja si myslim, ze takovy index asi nebude, protoze znalost vzdalenosti musis mit nekde ulozenou a to asi bude ta velikost co popisujes.
Ja bych si nejdrive problem zjednodusil na jednodimenzialni problem. Ten bych resil tak, ze bych si vybral kandidaty tim zpusobem, ze bych jel plovoucim oknem pres serazene hodnoty, kde velikost plovouciho okna by byla jako tebou hledana vzdalenost. Vypocet v tomto okne muzes delat budto v krajnich bodech (presna vzdalenost), nebo i v nejake oblasti okolo (+- 5 metru).
Presto je narocnost O(N), protoze to musis jednou projit.
Pro dve dimenze musis efektivne vyhledavat oblasti o velikosti tohoto okna. Myslim, ze navrhovany octtree by sel pouzit. Proste si najdes nadctverec, ktery je dvakrat vetsi nez tvou hledany ctverec a v nem po profiltrovani nemoznych kombinaci, provedes euklidovskou vzdalenost.
Tady bude narocnost podle me O(N*k), kde k je prumerny pocet bodu v tom ctverci bez nesmyslnych vraiant (cim vetsi vzdalenost tim hure).
Kazdopadne bych urcite pouzil rucne napsane reseni. A ne nejakou SQL databazi. 1G bodu muzes nacpat celou do pameti uz prostorove zaindexovane a budes mit rychlost uplne jinde. Stejne budes muset prochazet vse a tudiz to v pameti byt uz muze.
Kdybys nastinil k cemu to potrebujes, mozna by se naslo uplne jine reseni nez vsechny kombinace vzdalenosti...
Tve reseni pro jednodimenzionalni problem se mi libi! Bohuzel, nemyslim, nebo alespon nevim jak, tento problem na jednodimenzionalni prevest. Co se tyce dotazu jestli db nebo ne... uvidime. Pokud prijdu na to jak to indexovat, tak abych si nemusel sam implementovat r-tree, a ze jsem hodne liny, asi bych radsi pouzil nejakou DB (scidb, postgre, ...)
-
Nechce se mi nad tím moc přemýšlet, ale jako schůdná cesta se mi jeví nasypat data do k-d tree:
https://en.wikipedia.org/wiki/K-d_tree
pak celý prostor rozdělit na (vzájemně se překrývající) podprostory požadované velikosti, ve který se najdou body pomocí range search, což umí k-d tree efektivně:
www.cs.utah.edu/~lifeifei/cs6931/kdtree.pdf
a potom jen vyfiltrovat duplicity.
Jenze v tu chvili budu muset zase prochazet jeden bod po druhem
-
Kdybys nastinil k cemu to potrebujes, mozna by se naslo uplne jine reseni nez vsechny kombinace vzdalenosti...
Tak ono trochu napovi ta euklidovska L2. Takze to bude spis nekde oklo gis/big data swarmu a naopak vypada ze hry porovnavani obrazu. A taky z toho vypadava, ze sem prisel matematik a odkazovat zpatky odkud ocividne prisel je trosku mimo.
Jedna se o georegistrovane body, jak jsi spravne uhodl. Matematik nejsem, DB specialista uz vubec ne, proto se ptam plena :D
-
Prisel jsem trosku pozde, takze muzu jen podporit gamera - kd tree je na tohle velmi dobry. Sam jsem obdobnou ulohu potreboval resit ve sve bakalarce cca 5 let zpatky, tehdy mi takovy dotaz na 1e6 prvcich trval radove vteriny.
Principielne by mela stacit libovolna struktura pro prostorove vyhledavani, ktera obsahuje nejake informace o pozici - tj. quadtree (octree v 3D prostoru), kd-tree (libovolne dimenzionalni prostor), vicerozmerna mrizka (ta by mohla byt skoro nejjednodussi vzhledem, pokud jsem dobre pochopil, k jednotne vzdalenosti, do ktere se vyhledava). Ne zcela vhodny je R-tree (efektivne n-dimenzionalni B-tree). Hodne stesti!
Hmm.. to mne prekvapuje, protoze musis projit vsechny body a u kazdeho zadat range search ... to by znamenalo, ze takovy stihne databaze pod mikrosekundu, coz mi prijde nerealne... jak to ze To bylo tak rychle?
-
Nechce se mi nad tím moc přemýšlet, ale jako schůdná cesta se mi jeví nasypat data do k-d tree:
https://en.wikipedia.org/wiki/K-d_tree
pak celý prostor rozdělit na (vzájemně se překrývající) podprostory požadované velikosti, ve který se najdou body pomocí range search, což umí k-d tree efektivně:
www.cs.utah.edu/~lifeifei/cs6931/kdtree.pdf
a potom jen vyfiltrovat duplicity.
Jenze v tu chvili budu muset zase prochazet jeden bod po druhem
Neprocházíš všechny body, range search znamená, že hledáš všechno v určité oblasti (nikoliv vzhledem k existujícímu bodu). Stačí celý prostor rozdělit na oblasti a v těch hledat, nemusíš iterovat po bodech.
-
Kazdopadne odpoved tohoto vlakna asi je, ze tu nikdo nevi jak by to slo indexovat.
PostgreSQL umí k-d tree index. Nevím ale, jestli má taky nějaké operátory, kterými se dá udělat range search, nikdy jsem to v databázi nepotřeboval řešit.
Range search jiste, bez problemu, ale vuci zvolene hodnote, ne pres prostor.
-
Nechce se mi nad tím moc přemýšlet, ale jako schůdná cesta se mi jeví nasypat data do k-d tree:
https://en.wikipedia.org/wiki/K-d_tree
pak celý prostor rozdělit na (vzájemně se překrývající) podprostory požadované velikosti, ve který se najdou body pomocí range search, což umí k-d tree efektivně:
www.cs.utah.edu/~lifeifei/cs6931/kdtree.pdf
a potom jen vyfiltrovat duplicity.
Potrebuji vsechny pary bodu z prostoru ktere maji danou vzdalenost, tedy kdyz si zvolim range, akorat vyberu obdelnik ze ktereho mi ma (vsechny) body vratit. Stejne je pak budu muset projit a spocitat vzdalenosti, a to cele pak pro vsechny obdelniky. Alternativou je vzit jeden bod z DB a dat pozadavek na range search v pozadovane vzdalenosti a toto udelat pro vsechny body.
Jenze v tu chvili budu muset zase prochazet jeden bod po druhem
Neprocházíš všechny body, range search znamená, že hledáš všechno v určité oblasti (nikoliv vzhledem k existujícímu bodu). Stačí celý prostor rozdělit na oblasti a v těch hledat, nemusíš iterovat po bodech.
-
Range search jiste, bez problemu, ale vuci zvolene hodnote, ne pres prostor.
Zjednodušeně: pokud vím, jak je ten prostor velký (což vím, protože znám všechny body), tak ten prostor jednoduše rozdělím na N oblastí s velikostí range, která mě zajímá a v těch provedu range search. Typicky těch oblastí bude mnohem méně, než počet bodů. I kdyby to neplatilo (velmi velký prostor, ve kterém jsou body řídce), dá se to optimalizovat, začínám na větších oblastech a zjišťuji, jestli jsou v nich nějaké body. Pokud ne, dál mě nezajímají, pokud ano, metodou půlení intervalu velikosti oblastí se doberu k těm, pro které má smysl počítat range search. Rozhodně nemusím procházet všechny body.
-
Pár postřehů:
Ad 3) Nejblizsi body ve vzorku radove nekolik jednotek (e.g. metru), dotazovana vzdalenost cca 1-1000 jednotek, muze byt i diskretni (integer)... hmm... co indexovat u bodu histogramy okolnich bodu a potom hledat jen v tech co maji v urcitem binu histogramu nenulovou hodnotu?? Heeej! Dik za nakopnuti :)
Ad 4) Jedna se o hodnotu se znamou kovarianci (nepresnosti) - tedy interval
Ad 3 - sem se chtel zeptat, jak to myslis s tim nevyplati... jestli skladovat nebo generovat tu matici vzdalenosti. Ten histogram musis z neceho vyrobit a k tomu potrebujes tu matici vzdalenosti stejne udelat. Viz treba www.cse.ohio-state.edu/dmrl/papers/marsolo_icdm05.pdf
Princip vychazi z tohodle relativne polopate vysvetleno s obrazky www.tcs.tifr.res.in/~ghosh/partha1-lecture.pdf
Jinak pokud chces optimalizovat predvyber pro vypocet neuplne matice vzdalenosti, tak leda koumat neco s http://en.wikipedia.org/wiki/Data_clustering nebo BSP tree co uz tu navrh a zkonstruovat dva s nejmensi delkou hrany o 2*range. V kazdym podprostoru zkonstruovat convex hull T M Chan 1996 a pokud bude mensi nez pozadovana minimalni vzdalenost, tak pak v tom druhym BSP overlay, ktery je posunuty o offset vyloucit jeste vsechny prekryvajici se rozsahy a muzes vsechny body z te oblasti zahodit.
A nebo neco obdobneho, ale napaditejsiho.
-
Range search jiste, bez problemu, ale vuci zvolene hodnote, ne pres prostor.
Zjednodušeně: pokud vím, jak je ten prostor velký (což vím, protože znám všechny body), tak ten prostor jednoduše rozdělím na N oblastí s velikostí range, která mě zajímá a v těch provedu range search. Typicky těch oblastí bude mnohem méně, než počet bodů. I kdyby to neplatilo (velmi velký prostor, ve kterém jsou body řídce), dá se to optimalizovat, začínám na větších oblastech a zjišťuji, jestli jsou v nich nějaké body. Pokud ne, dál mě nezajímají, pokud ano, metodou půlení intervalu velikosti oblastí se doberu k těm, pro které má smysl počítat range search. Rozhodně nemusím procházet všechny body.
V dane oblasti budu mit dejme tomu 1000 bodu. Tak. A jak ted najit vsechny pary, co od sebe jsou vzdalene zrovna napr 53 jednotek? Range search mi vrati body ktere maji pozadovanou vzdalenost k zadanemu bodu - kteremu?
-
Pár postřehů:
Ad 3) Nejblizsi body ve vzorku radove nekolik jednotek (e.g. metru), dotazovana vzdalenost cca 1-1000 jednotek, muze byt i diskretni (integer)... hmm... co indexovat u bodu histogramy okolnich bodu a potom hledat jen v tech co maji v urcitem binu histogramu nenulovou hodnotu?? Heeej! Dik za nakopnuti :)
Ad 4) Jedna se o hodnotu se znamou kovarianci (nepresnosti) - tedy interval
Ad 3 - sem se chtel zeptat, jak to myslis s tim nevyplati... jestli skladovat nebo generovat tu matici vzdalenosti. Ten histogram musis z neceho vyrobit a k tomu potrebujes tu matici vzdalenosti stejne udelat. Viz treba www.cse.ohio-state.edu/dmrl/papers/marsolo_icdm05.pdf
Princip vychazi z tohodle relativne polopate vysvetleno s obrazky www.tcs.tifr.res.in/~ghosh/partha1-lecture.pdf
Jinak pokud chces optimalizovat predvyber pro vypocet neuplne matice vzdalenosti, tak leda koumat neco s http://en.wikipedia.org/wiki/Data_clustering nebo BSP tree co uz tu navrh a zkonstruovat dva s nejmensi delkou hrany o 2*range. V kazdym podprostoru zkonstruovat convex hull T M Chan 1996 a pokud bude mensi nez pozadovana minimalni vzdalenost, tak pak v tom druhym BSP overlay, ktery je posunuty o offset vyloucit jeste vsechny prekryvajici se rozsahy a muzes vsechny body z te oblasti zahodit.
A nebo neco obdobneho, ale napaditejsiho.
Projdu si to, ted jsem v praci a musim makat na uplne jinych vecech :) Pak odpovim.
K otazce co se mi nevypleti - no ty vzdalenosti minimalne jednou proste spocitat musim, to je jasne, takze slo o to, aby index nemel pro 1G double precision bodu 1G^2x8B = 8x10^18B :)
Zatim se ale priklanim k tomu udelat si index tech histogramu vzdalenosti k jednotlivym bodum - pokud ho zapisu kompaktne, bude mit dejme tomu nekolik GB, coz uz je vpohode... potom jen z indexu vyberu ty body, ktere maji nejaky bod v danem rozsahu vzdalenosti a rucne pro ne overim jestli sedi i presna kontrola + najdu duplicity --> tohle by mohlo jit.
-
Jak velký bude ten prostor, pokud bych to počítal diskrétně (stačí řádově na počet bodů)?
-
Jak velký bude ten prostor, pokud bych to počítal diskrétně (stačí řádově na počet bodů)?
Prostor je neomezeny. Nejlepe spojity, ale diskretizaci se nebranim, takze pak by to bylo dejme tomu 1Mx1M bunek.
-
V dane oblasti budu mit dejme tomu 1000 bodu. Tak. A jak ted najit vsechny pary, co od sebe jsou vzdalene zrovna napr 53 jednotek? Range search mi vrati body ktere maji pozadovanou vzdalenost k zadanemu bodu - kteremu?
Prošel bych celý prostor (rozdělený na N oblastí), range searchem bych vybral možné kandidáty (všechny body v oblasti) a pro všechny body z té oblasti a pro všechny oblasti bych zkostruoval tabulku:
BOD1 BOD2 VZDALENOST
V té tabulkce nebudou všechny možné kombinace vzdálenosti bodů, ale jen možní kandidáti z oblastí. To se udělá jednou. Zjištění stejně vzdálených bodů už je jen jeden dotaz do tabulky:
SELECT * FROM tabulka WHERE VZDALENOST >= minVzdalenost AND VZDALENOST <= maxVzdalenost
Tohle nestačí?
-
Jak velký bude ten prostor, pokud bych to počítal diskrétně (stačí řádově na počet bodů)?
Prostor je neomezeny. Nejlepe spojity, ale diskretizaci se nebranim, takze pak by to bylo dejme tomu 1Mx1M bunek.
FPU te nebude mit rado az budes chtit znat vzdalenost dvou NaN.
Tak jasne podle toho co pises to neni nic ani z bioinformatiky/chemie, ani z astronomie a vypadla i vetsina Meteorologie. Mozna objevujes kola z pocitacove grafiky.
A pokud je to ciste podukol pro herni pathfinding, tak nevymyslej kolo, a jdi do navmeshe. tisice lemingsu co to pouzilo pred tebou se prece nemuze mylit.
Pokud chces neco robustnejsiho, tak pocitej s tim, ze na to nebudes mit cas ani v mokrym snu, kdy bude mit doma kazdy i7. Leda u tahovky nebo u zobrazeni statistik co se prepocitavaji jednou za cas jako treba doprava simcity a spol.
Ty kd-tree co beres, ze "pro kazdy bod" a o kus dal si pochopil, ze to jde "jen" pro kazdou bunku pak odpovidaji taky predfiltru pro vypocet neuplne matice. Je to jen o tom jak vypadaji data ktery zpracovavas. Podle toho se da nadhodit odpovidajici predfiltrovani, ktery bude mit sanci na solidni uspech a nebude jen pridavat vypocty navic. Asi tak jako, ze do astronomie se hodi neco jinyho nez do geografie a kdyby to byla bio/chemie tak tam muzes diky specificke diskretizaci primo carovat. Jinak je to vareni z vody.
-
Prošel bych celý prostor (rozdělený na N oblastí), range searchem bych vybral možné kandidáty (všechny body v oblasti) a pro všechny body z té oblasti a pro všechny oblasti bych zkostruoval tabulku:
BOD1 BOD2 VZDALENOST
V té tabulkce nebudou všechny možné kombinace vzdálenosti bodů, ale jen možní kandidáti z oblastí. To se udělá jednou. Zjištění stejně vzdálených bodů už je jen jeden dotaz do tabulky:
SELECT * FROM tabulka WHERE VZDALENOST >= minVzdalenost AND VZDALENOST <= maxVzdalenost
Tohle nestačí?
Ono moc nepomuze to mit ve vice tabulkach. Mnozstvi dat bude stejne. Skoncis s tim obrovskym mnozstvim co uz se zminovalo jen ve vice tabulkach.
Dulezite je rozhodnout zda existuje omezeni na dotaz. Napr pouze v rozsahu 10 - 2000 metru. Tim se znacne omezuje velikost indexu. Kdyz by chtel udelat ten brute force tak staci ukladat zapakovane soubory dle vzdalenosti zaokrouhlene na napr. metry (ale i vic, at je mene dat) a sesortovane dle IDcek, aby ulehcil kompresi. Na jeden zaznam je to 8byte (32 bit na IDcko), ale po kompresi to bude mnohem mene. Po nacteni staci uz jen udelat presny test a odfiltrovat chyby. Chtelo by to udelat testovaci vzorek treba 20-50metru. Jak uz tady nekdo zminoval, typicky dotaz bude mozna jen v nejakem rozsahu. Kdyz se toto udela jako cache tak to bude pomale jen na zacatku.
Teoreticky bude index velky (ROZSAH / PRESNOST) * 8Byte * PRUMERNY_POCET_USECEK_V_BINU / KVALITA_KOMPRESE. Docela by me zajimalo kolik by to statisticky delalo :)
-
Ono moc nepomuze to mit ve vice tabulkach. Mnozstvi dat bude stejne. Skoncis s tim obrovskym mnozstvim co uz se zminovalo jen ve vice tabulkach.
Já to pochopil tak, že chce mít co nejrychlejší dotaz na vzdálenost a nic rychlejšího, než mít to předpočítané v jiné tabulce, asi nevymyslí. V té tabulce vzdáleností nebudou všechny kombinace, ale jen omezené na určitý range (může to být omezené zdola i shora), takže extrémně moc dat navíc to nebude. Nevýhoda je, že se musí o tu tabulku starat, když přidá bod - to znamená 1x range search a potom projít výsledky a dosypat to do tabulky vzdáleností, takže přidání bodu bude dražší.
-
Jeste me napadlo, ze delat nejake k-d stromy apod je docela zabijak pro 1G bodu. Ono pri float presnosti to bude 8GB blob v pameti.
Pokud bude nejaka rozumna max. velikost te usecky tak by slo krasne napsat streamovaci algoritmus zalozeny na sweep line. Predstav si ten 1D problem co jsem popisoval. Budes mit bin do ktereho budes sypat body, ktere budes mit serazene dle X. Ten bin bude tudiz take serazeny. Delka bude jeho sirkou (okno). Ten bude urcen v podstate jen dvema poitery, protoze vstup uz je serazen, proto jeho zmena bude velmi rychla (zadne operace).
Nad timto oknem muzes pote provadet vypocet vzdalenosti. Hezka feature je, ze to musis delat pouze pro bod, ktere lezi na leve hranici okna. Pote poskocis na dalsi bod, ktery je za levou hranici a pravou pripadne upravis dle delky (take pouze jednosmerne). A jedes znovu.
Timto algoritmem si muzes vyrobit index pro vsechny vzdalenosti, ktere jsou mensi nez sirka okna na jeden pruchod a navic s malou pametovou narocnosti. Pro omezenou delku to bude fungovat dobre. Asi bych to delal treba po 50ti metrech (50 otevrenych gzip souboru) a proste zapisoval.
-
Prisel jsem trosku pozde, takze muzu jen podporit gamera - kd tree je na tohle velmi dobry. Sam jsem obdobnou ulohu potreboval resit ve sve bakalarce cca 5 let zpatky, tehdy mi takovy dotaz na 1e6 prvcich trval radove vteriny.
Principielne by mela stacit libovolna struktura pro prostorove vyhledavani, ktera obsahuje nejake informace o pozici - tj. quadtree (octree v 3D prostoru), kd-tree (libovolne dimenzionalni prostor), vicerozmerna mrizka (ta by mohla byt skoro nejjednodussi vzhledem, pokud jsem dobre pochopil, k jednotne vzdalenosti, do ktere se vyhledava). Ne zcela vhodny je R-tree (efektivne n-dimenzionalni B-tree). Hodne stesti!
Hmm.. to mne prekvapuje, protoze musis projit vsechny body a u kazdeho zadat range search ... to by znamenalo, ze takovy stihne databaze pod mikrosekundu, coz mi prijde nerealne... jak to ze To bylo tak rychle?
No, tak rychle to bylo proto, ze jsem si na to napsal vlastni upravu bucket KD-tree a co jsem tak pocital, tak v prumeru u nahodne rozmistenych bodu byla maximalni hloubka stromu kolem 50-60. Jinak to bylo zpomalene jeste tim, ze jsem hledal vsechny body do nejake heuristicky dane vzdalenosti a pokud jsem nenasel dostatek bodu, tak bezel jeste k-nearest-neighbor. Jak rikam, uloha trosku jina, ale obsahuje reseni i te, na kterou se ptal kolega.
Podle toho, jak jsem ted cetl predpokladane vzdalenosti se ale zacinam spis priklanet k vicerozmerne mrizce, pripadne upravenemu r-tree, ktery by mel bunky ne hyperkvadrove ale hyperkulove, pripadne nejake kombinaci obou.
-
Nechce se mi nad tím moc přemýšlet, ale jako schůdná cesta se mi jeví nasypat data do k-d tree:
https://en.wikipedia.org/wiki/K-d_tree
pak celý prostor rozdělit na (vzájemně se překrývající) podprostory požadované velikosti, ve který se najdou body pomocí range search, což umí k-d tree efektivně:
www.cs.utah.edu/~lifeifei/cs6931/kdtree.pdf
a potom jen vyfiltrovat duplicity.
Jenze v tu chvili budu muset zase prochazet jeden bod po druhem
Neprocházíš všechny body, range search znamená, že hledáš všechno v určité oblasti (nikoliv vzhledem k existujícímu bodu). Stačí celý prostor rozdělit na oblasti a v těch hledat, nemusíš iterovat po bodech.
Mozna je to offtopic, ale neslo by pouzit v tom k-d tree sesti-uhelniky misto ctvercu?
7 6-ti uhlelnihu by tvorilo dalsi 6-ti uhelnik na vyssi urovni.
Pro kazdou uroven a kazdou vzdalenost by pak slo snadno zjistit ktere 6-ti uhelniky tvori pary kde hledat.
-
Mozna je to offtopic, ale neslo by pouzit v tom k-d tree sesti-uhelniky misto ctvercu?
7 6-ti uhlelnihu by tvorilo dalsi 6-ti uhelnik na vyssi urovni.
Tak je sice patek, ale to jeste neznamena, ze se mas ozrat uz dopoledne :-D
-
Cestou domu jsem nad tim jeste premyslel a myslim, ze jsem prisel na to jak ten sweep udelat v podstate efektivneji nez ten KD, protoze by se automaticky rusily nemozne varianty v nejakem mezikruzi hledane vzdalenosti. Mohlo by to byt tedy takto:
1. Udelat si ten soubor jak jsem rikal, ale serazeny dle BUCKET_X a pote dle PT_Y. BUCKET_X se da delat dvema zpusoby:
a) floor(PT_X / BUCKET_SIZE) (zde muze byt kybl ridky anebo naopak nacpany). Da se to napsat jako SQL dotaz order by ...
b) Variabilni sirka tak, aby se naplnil do nejake velikosti (treba 10000 bodu), to uz asi v SQL nepujdea budes muset sesortovat rucne.
2. Ten sweep by jel uplne stejne, jen s tim rozdilem, ze bys mel pointery i na kyble do kterych jeste zasahuje. V nejhorsi variante, bys kontroloval o N (treba tech 10000) bodu vice.
3. Zde prichazi ta hlavni vyhoda, proc ti ty body navic nevadi. Muzes pouzit binarni hledani mezi, ktere body kontrolovat na ose Y. Napr. vis, ze pro bod ke kteremu prave vyhledavas ma Y=1000. Delka kterou hledas je napr 50. Pote hledas v mezich od 950-1050 (cili najdes binarne 950 a traverzujes do 1050) v kazdem kyblu. Pro velke vzdalenosti naopak muzes vyhodit i prostredek a navic vzdalene kybly omezujes rozsah dle nejhorsi kruznice co opisuje hledany bod (980-1020). Pro nekonecne male buckety timto vlastne kontrolujes pouze spravne body na hrane kruznice. 10000 bodu pres tvuj rozsah, ale bude dostatecne uzke a navic nebudes muset delat tolik hledani pro vetsi vzdalenosti. Pro vzdalenost pres celou plochu pak mas nejhorsi variantu 1G / BUCKET_SIZE hledani pro kazdy bod, ale to je asi hodne extremni hledat takove vzdalenosti. Musis holt spravne urcit tu sirku na zaklade vzdalenosti co budes asi hledat.
Vypada to jako pekna cvicna uloha. mozna si to nekdy zkusim :)