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

Tomas

Re:Vyhledání bodů v DB podle vzdálenosti
« Odpověď #30 kdy: 01. 08. 2013, 14:49:56 »
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 :)






gamer

Re:Vyhledání bodů v DB podle vzdálenosti
« Odpověď #31 kdy: 01. 08. 2013, 14:57:36 »
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žší.

Tomas

Re:Vyhledání bodů v DB podle vzdálenosti
« Odpověď #32 kdy: 01. 08. 2013, 15:41:37 »
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.


Vasek

Re:Vyhledání bodů v DB podle vzdálenosti
« Odpověď #33 kdy: 01. 08. 2013, 16:18:12 »
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.

Ivan

Re:Vyhledání bodů v DB podle vzdálenosti
« Odpověď #34 kdy: 02. 08. 2013, 10:41:05 »
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.






omg

Re:Vyhledání bodů v DB podle vzdálenosti
« Odpověď #35 kdy: 02. 08. 2013, 10:48:54 »
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

Tomas

Re:Vyhledání bodů v DB podle vzdálenosti
« Odpověď #36 kdy: 02. 08. 2013, 12:12:20 »
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 :)