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

Struktura za indeksiranje

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

[ Pregleda: 4032 | Odgovora: 6 ] > FB > Twit

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 - pre 213 meseci
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)
 
Odgovor na temu

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*



+1 Profil

icon Re: Struktura za indeksiranje10.09.2006. u 20:02 - pre 213 meseci
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.
 
Odgovor na temu

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 - pre 213 meseci
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.
 
Odgovor na temu

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 - pre 213 meseci
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.
 
Odgovor na temu

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 - pre 213 meseci
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
 
Odgovor na temu

FuzzyCreation

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



Profil

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

FuzzyCreation

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



Profil

icon Re: Struktura za indeksiranje18.09.2006. u 18:30 - pre 213 meseci

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....
 
Odgovor na temu

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

[ Pregleda: 4032 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

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