Srodne teme
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Struktura za indeksiranje

[es] :: Art of Programming :: Struktura za indeksiranje

[ Pregleda: 1281 | Odgovora: 6 ]

 Postavi temu Odgovori

Autor
Pretraga teme: Traži
Markiranje Štampanje RSS

rivan
Ivan Radovanović

Član broj: 1901
Poruke: 71
*.dialup.sezampro.yu.

ICQ: 212235650


Profil

icon Struktura za indeksiranje10.09.2006. u 16:55

Da li je neko upoznat sa nekom efikasnom strukturom za indeksiranje po vise kolona?
Precizniji opis bi bio:
Ako je data tabela sa kolonama k_1, k_2, ..., k_n, da li postoji struktura podataka koja bi za formiran indeks nad m kolona (k_1, k_2, ..., k_m) obezbedjivala sledeca svojsta:
1. da je pretraga za zadatu punu m-torku efikasna bar koliko i indeks formiran pomocu B-stabla (manje-vise klasican indeks u bazama podataka)
2. da je za fiskirane vrednosti za SVAKI podskup skupa {k_1, k_2, ..., k_m} struktura podjednako efikasna (konstantan broj puta sporija od pretrage po celoj m-torci)
10.09.2006. u 16:55 

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 185
212.200.10.*



Profil

icon Re: Struktura za indeksiranje10.09.2006. u 20:02
Nisam te bas razumeo najbolje. Ako moze pojasni malo koje funkcije treba da vrsis nad tom matricom
Math is like love. A simple idea but it can get complicated.
10.09.2006. u 20:02 

rivan
Ivan Radovanović

Član broj: 1901
Poruke: 71
*.adsl.static.sezampro.yu.

ICQ: 212235650


Profil

icon Re: Struktura za indeksiranje11.09.2006. u 08:17
Imam tabelu od n kolona (k_1, k_2, ..., k_n), slicno kao u relacionoj bazi. Pitanje je kako napraviti indeksnu strukturu sa gore nabrojanim svojstvima - dakle pitanje je blisko implementaciji baze podataka.
Baze obicno za indeksiranje koriste B-stabla, ili neku varijaciju te strukture, a ona ima nezgodno svojstvo da ako je recimo formiran indeks nad kolonama k_1, k_2, k_3 u ovom redosledu onda se taj indeks moze efikasno koristiti za uslove gde su fiksirani redom (k_1, k_2, k_3), (k_1, k_2), (k_1) i samo za to.
Funkcije koje struktura treba da podrzava su standardne nad pretrazivackim strukturama - umetanje, pretrazivanje, izbacivanje.
11.09.2006. u 08:17 

NM 156
Ljubomir Karanovic

Član broj: 75801
Poruke: 10
*.PPPoE-2937.sa.bih.net.ba.



Profil

icon Re: Struktura za indeksiranje11.09.2006. u 17:11
Problem je u tome sto medju takvim n-torkama ne vaze klasicne relacije poretka.
Drugim rjecima, one nisu direktno uporedive, a to je koncept na kom se bazira izgradnja klasicnih struktura podataka koje se koriste za indeksiranje, kao sto su razni tipovi B stabala koja si spomenuo.

Uglavnom, vjerovatno postoji nacin na koji bi se i ovo moglo izvesti, ali cisto sumnjam da bi po efikasnosti mogao biti na nivou B stabla.
11.09.2006. u 17:11 

rivan
Ivan Radovanović

Član broj: 1901
Poruke: 71
*.adsl.static.sezampro.yu.

ICQ: 212235650


Profil

icon Re: Struktura za indeksiranje15.09.2006. u 08:44
Svestan sam da tu ne vazi klasican poredak, ali me zanima da li mozda postoji neki standardan nacin kako se takvi problemi resavaju na efikasan nacin
15.09.2006. u 08:44 

FuzzyCreation

Član broj: 112586
Poruke: 33
*.eunet.yu.



Profil

icon Re: Struktura za indeksiranje18.09.2006. u 18:25
pogledaj kako radi lucene invertovani index... nisam siguran, ali mislim da se tu krije odgovor na tvoje probleme
18.09.2006. u 18:25 

FuzzyCreation

Član broj: 112586
Poruke: 33
*.eunet.yu.



Profil

icon Re: Struktura za indeksiranje18.09.2006. u 18:30

mozes da indeksiras po vise kolona, za svaki token on ce ti dati skup dokumenata gde se nalazi tvoj token, znaci indeks vrste tvoje matrice. Kasnije samo nadjes uniju (ako ti trebaju svi predlozi, a kasnije propustas kroz filtere prema onome sto ti zaista treba) sto takodje efikasno moze da se odradi bit vector operacijama... Mislim da ono sto ti trazis postoji i da se zove Invertovani indeks, struktura koja ce za neki token da ti kaze u kojim se sve dokumentima nalazi dati token....
18.09.2006. u 18:30 

[es] :: Art of Programming :: Struktura za indeksiranje

[ Pregleda: 1281 | Odgovora: 6 ]

 Postavi temu Odgovori

Srodne teme
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.