orthogonal range search

 ( apal | 2007. február 11., vasárnap - 23:26 )

A cimbeli problema a kovetkezo"t takarja: adott N pont, D dimenzioban, x1 ... xD koordinatakkal e's keressuk, hogy egy adott, [a1..b1]x[a2..b2]x...x[aD..bD] koordinataknak megfelelo" te'glatestben mely pontok esnek bele. Kerdes az, hogy erre a problemara letezik-e valami hatekony implementacio? N nagy (~500millio, 1.1milliard, ...), az asszocialt adatbazis is nagy (~100 giga...). Gyakorlatban D=2, 3 vagy 4 lenne.

Mysql-lel probalkoztam, az hatarozottan nem jo erre a problemara. Az oracle-t mondja'k me'g, csak annak az ingyenes verzioja 4giga's limittel rendelkezik. A mysql-ben ez az ege'sz csak kozvetetten van implementalva e's csak D=2-re (spatial extensions), mindez openGIS alapokon. A pgsql-be is ezt (opengis) implementalta'k, de azt nem probaltam me'g (erdemes-e?).

Mindezen problemak miatt egy sajat implementaciot is elkezdtem, egyelore hatarozottan alfa statuszban van, bar mar D=tetszolegesre jol mukodik, inkabb csak UI gondok vannak (de az nagyon), illetve par optimalizalasbe'li problema. Majd lesz itt is, reszletesebben, ha olyan allapotban lesz.

Ha valaki tud effele problemara hatekony megolda'st, ne tartsa vissza ;)

Hozzászólás megjelenítési lehetőségek

A választott hozzászólás megjelenítési mód a „Beállítás” gombbal rögzíthető.

Hmm. Mi lenne az eredeti problema? Illetve milyen tovabbi kovetelmenyek vannak a keresessel kapcsolatban (valaszido, parhuzamos keresesek szama, stb)? Egyebkent a mysql mit (illetve mit nem) produkalt? ;-)

Az eredeti problema egy csillagkatalogus implementalasa lenne... ez igazabol mar meg is mondja hogy mik a "nehezitesek", nem is igazan az a kritikus mennyi a valaszido (minel rovidebb, annal jobb;), hanem hoy:
- a pontok nem sikban hanem egy gombfeluleten helyezkednek el homogen modon (tehat kiteritve, mondjuk hosszusag/szelesseg szerinti koordinatazasban nem kapunk kozel sem homogen eloszlast)
- kritikus a "fe'nyesse'g" szerinti szelekcio is (lenyegeben gyakorlatilag ez +1 dimenzio), tehat az ember vagy nagy teruletrol valogat ki fe'nyes valamiket, vagy kis teruletrol, halvanyakat; legalabbis ez az ami gyakori (lenne)

Egyebkent a mysql mit (illetve mit nem) produkalt?
~500 millio rekordot tisztan 2D-ben ~2 he'tig indexelt (2x dual opteron, 4giga rammal), majd utana egy szelekcio is orakig tartott. A jelenlegi (alfa) verzio ma'r nehany nap alatt beindexeli, es perces nagysagrendben van a query, de ez javithato' (a randomseek-ek limitalnak; a belso cache sokat szamit, illetve most probalkozom pa'r specifikus vegyes rendeze'ssel, hatha segit az is, hogy a nyers tabla mar valamilyen szinten rendezett legyen).

Aztakurva. Ha az én nyakamba sóznának ilyen feladatot, inkább önként elmennék kapálni.

-- pgergely --

Hmm. Nem lesz egyszeru feladat a hatekony mukodes foleg ha sok dimenzio szerint kell egyszerre szelektalni (kulonosen, ha nem is elemi adatok szerint). Ez valamilyen egyetemi project lenne? Milyen adathalmazt hasznaltok, esetleg elerheto valahonnan?

Hmm. Nem lesz egyszeru feladat a hatekony mukodes foleg ha sok dimenzio szerint kell egyszerre szelektalni (kulonosen, ha nem is elemi adatok szerint).
Azert van sok-sok konnyites is ;) Pl:
- a katalogus (adatbazis) eleve adott, tehat nincsen semmifele beszura's. Azaz az indexele'shez statikus struktura is hasznalhato, pl. binary tree alapokon, nem kell durvabb algoritmusokat (balanced tree, hash tree) hasznalni...
- a problema atfogalmazhato' ugy is, hogy minden igeny szeritni koordinata szerint 1x sorbarendezzuk az adathalmazt (raadasul minden koordinata egy ve'ges intervallumbol jon) es az adott koordinatakat a megfelelo" sorbarendezes szerinti indexszel helyettesitjuk, a query-k elott pedig a val'os intervallum-hata'rokat lecsere'lju"k indexekre (ez D*lb(N) muveletbol megteheto, sima binaris kerese'ssel, ez gyors); igy az alapproblema ege'sz tipusokra van visszavezetve, raadasul a degeneraciot is meg lehet szuntetni: nem szerepelhet ke't pont ugyanazzal az index-koordinataval...
- a fenyesse'g szerinti szelekcio is atfogalmazhato ugy hogy egy 3dimenzios teglatestben levo pontok kozul kivalasztani egy keskeny de magas vagy sze'les de alacsony teglaban levo" pontokat (azaz kis teruletrol sok halvany csillag, vagy nagy e'gteruletrol csak a fe'nyesebb csillagokat).

Ez valamilyen egyetemi project lenne? Milyen adathalmazt hasznaltok, esetleg elerheto valahonnan?
Jaja, egyetemi, de nem lenne rossz, ha ma'sra is fel lehetne hasznalni, vegulis. Az adatbazisok (USNO, 2MASS) elerheto"ek, pl kozvetve innen, de itt vannak linkek az eredeti
nyers adatbazisokhoz is. A 2mass az eredetiben 160giga, az usno-t me'g nem mertem megne'zni, abban van az 1.1milliard rekord.

A 2MASS adatait kozvetlen letoltheto formaban megtalaltam (ftp), de az USNO adatait nem :/ Esetleg tudsz valahonnan direkt linket? ;-)

Huh, passz, egyelore nekem se sikerult elerni... majd utanajarok. Nya'ron me'g megvolt ;]

Hm, ugy nez ki, hogy most epp megsem erheto" el az eredeti katalogus, legalabbis az USNO saja't terulete'ro"l...:/

Ha szétszednéd a tégládat sok kis téglára,
ezeket besorszámozva,kereséskor csak néhány
"kis téglát" kéne átnézni.

A sorszámokhoz nem kellene
index,elég hash-elni.(vagy esetleg fa struktúrájú könyvtár szerkezetbe rakni)
ha SQL helyett meg valamely script nyelvvel oldanád meg,
akkor megúsznád az sql konfig-hangolást.

A gyakorlatban igy is szokta'k implementalni, valoban, teglakra feloszt e's kulon-kulon fileokba ta'rol, oszt hatha.

Szvsz szebb lenne, ha az egesz db egyetlen file-ban lenne. Az, hogy eloszor x iranyba, majd ketreszre osztve y iranyba, majd 4reszre osztva x iranyba, majd 8reszre osztva y iranyba, stbstb rendezzuk az eredeti file-t, lenyegeben ezt valositja meg. Ha ehhez hozzacsapunk valami lookup-tablat, akkor talan ugyanennyire hatekony lesz. Ezt majd kiprobalom...