Vyhledání bodů v DB podle vzdálenosti

[Randolf]

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, ...)

[Reklama]

[Randolf]

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

[Randolf]

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

[Randolf]

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?

[gamer]

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.

[Reklama]

[Randolf]

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.

[Randolf]

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.

[gamer]

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.

[omg]

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.

[Randolf]

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?

[Randolf]

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.

[TTTTT]

Jak velký bude ten prostor, pokud bych to počítal diskrétně (stačí řádově na počet bodů)?

[Randolf]

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.

[gamer]

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čí?

[omg]

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.