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

[Randolf]

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

Diky!

[Reklama]

[Oba medvědi]

no PostgreSQL s nějakým prostorovým rozšířením by na to měla být jako dělaná

[Randolf]

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

[Petr Blahos]

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".

[someone]

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.

[Reklama]

[Tomas]

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

[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.

[omg]

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.

[Vasek]

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!

[Vasek]

Jeste dodam k tomu "radove vteriny" - radove vteriny to bylo samozrejme pro dotaz provedeny postupne na vsech bodech.

[Tomas]

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.

[Pavouk106]

Dopr... o čem to tady mluvíte?

[Randolf]

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.

[gamer]

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.

[Randolf]

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