Fuziono stablo

Fuziono stablo predstavlja stablo koje implementira asocijativni niz nad w-bitnim celim brojevima. Коristi O(n) prostora i izvršava pretragu u O(log^w n)) vremenu, koje je asimptotski brže od tradicionalnog binarnog stabla, i u stvari bolje od van Emde Boas stable gde je w veće. To postiže brzinu eksploatacije pojedinih operacija koje imaju konstantno vreme koje je potrebno u mašinskom jeziku. Fuziono stablo su osmislili Michael Fredman and Dan Willard.^[1]

Nekoliko naprednih stvari je urađeno od kad su Fredman i Vilard osmislili algoritam 1990. 1999.^[2] prikazano je kako se može implementirati fuziono stablo preko AC⁰ modela, u čijoj implementaciji više nije potrebno konstantno vreme. Dinamička verzija fuzionog stabla koja koristi heš tabele je predložena 1996^[3] koja je O(log_w n) složenosti. Druga dinamička verzija koja je predložena 2007.^[4] koristi eksponencijalno stablo čija je složenost u najgorem slučaju O(log_w n + log log u) po operaciji, gde je u veličina najvećeg ključa. Ostaje otvoreno pitanje da li će dinamička fuzija moći da postigne složenost od O(log_wn) po operaciji.

Каko radi

Fuziono stablo je u osnovi B-stablo sa izdvajanjem faktora w^1/5 (bilo koji mali eksponent dolzi u obzir), koji daje složenost O(log_w n). Da bismo postigli željenju radnu verziju za ispravke i upite, fuzionim stablom moramo omogućiti da pretrazivanje čvora podrazumeva više od w^1/5 ključeva u konstantnom vremenu. Ovo se može uraditi “sabijanjem” ključeva tako da se svi mogu snaći na mašinskom jeziku, što zauzvrat omogućava da se sabijanje radi paralelno. Ostatak ovog članka će opisati operacije u statičkom Fuzionom stablu, u kom su podržani samo upiti.

Skiciranje

Skiciranje je metod koji podrazumeva da svaki w-bitni ključ u čvoru sadrži k ključeva koji su kompresovani na samo k-1 bita. Svaki ključ x može se posmatrati kao deo binarnog stabla visine w koji počinje korenom i završava se listom koji odgovara x. Da bi se razlikovala dva dela, dovoljno je pogledati u njihove tačke grananja (prvi bit gde se dva ključa razlikuju). Svi k delovi zajedno imaju k-1 tački grananja, zato je potrebno najviše k-1 bita da bi se razlikovali bilo koji od k ključeva.

Važna uloga skiciranja je da čuva red ključeva. To je, sketch(x) < sketch(y) za bilo koja sva ključa gde je x<y.

Približna skica

Ako je zapis kompresovanih bita b₁ < b₂ < ··· < b_r, onda je kompresovanje ključa x_w-1···x₁x₀ r-bitnog celog broja ${\displaystyle x_{b_{r}}x_{b_{r-1}}\cdots x_{b_{1}}}$. Sa standardnim operacijama kakve se koriste u C jeziku, teško je direktno izračunati kompresovanje ključa u konstantnom vremenu. Umseto toga, kompresovani bitovi mogu biti zapakovani u opsegu veličine od najviše r⁴ , koristeći bitovsko AND i množenje. Bitovsko AND služi da ukloni sve nekompresovane bitove iz ključa, dok množenje pomera kompresovane bitove u mali niz. Kao i „savršena“ skica, skica čuva približan raspored ključeva. Za neke reči je potrebno utvrditi tačan broj umnožavanja konstanti. Svaki kompresovani bit na lokaciji b_i će množenjem biti pomeren na b_i + m_i preko m = ${\displaystyle \textstyle \sum _{i=1}^{r}}$. Za približno skiciranje moramo se držati sledećih pravila:

1. b_i + m_j su različiti za svaki par (i, j). To nam garantuje da kompresovani bitovi neće biti oštećeni prilikom množenja.
2. b_i + m_j je strogo rastuća funkcija od i. To znači da je redosled kompresovanih bitova očuvan.
3. (b_r + m_r) - (b₁ - m₁) ≤ r⁴. To znači da su kompresovani bitovi zapakovani u opsegu veličine od r⁴.

Induktivni argument pokazuje kako mi može biti konstruisan. Neka je m₁ = w − b₁. Pretpostavimo da 1 < t ≤ r i da su 'm₁, m₂... m_t već izabrani. Onda se izabere najmanji ceo broj m_t koji zadovoljava osobine (1) i (2). Osobina (1) zahteva da m_t ≠ b_i − b_j + m_l za sve 1 ≤ i, j ≤ r i 1 ≤ l ≤ t-1. Prema tome, postoji manje od tr² ≤ r³ koji m_t mora da zadovoljava. Kad je m_t izabran da bude minimum,(b_t + m_t) ≤ (b_t-1 + m_t-1) + r³. Ovo objašnjava osobinu (3).

Približan zapis se izračunava na sledeći način: 1. Maskiraju se svi kompresovani i bitovi koji su konjugovani . 2. Množenjem ključ će biti predodređen za konstantu m. Ova operacija u stvari zahteva dve mašinske reči , ali ovo i dalje može biti urađeno u konstantnom vremenu. 3. Maskira se sve, osim pomerenih kompresovanih bitova. Oni se sada smeštaju u susedni blok od najviše r⁴ < w^4/5 bita. U nastavku ovog članka, kompresovanje će označavati približno skiciranje.

Paralelno poređenje

Cilj kompresije je da sabijanjem dozvoli da svi ključevi budu smešteni u jednu w-bitnu reč. Onda će sabijanje čvora biti sledeći niz znakova: 1sketch(x₁)1sketch(x₂)...1sketch(x_k) . Možemo videti da sketch funkcija koristi tačno b ≤ r⁴ bita. Zatim, svaki blok koristi 1 + b ≤ w^4/5 bita, a od k ≤ w^1/5 , ukupan broj bitova u čvoru je najviše w. Ukratko: za niz s i ne negativni broj m, s^m označava ulančavanje niza s m puta. Ako je t takođe niz, st označava niz od t do s. Skiciranje čvora omogućava nam da pretrazujemo ključ za bilo koji b-bitni ceo broj y. Neka je z = (0y)^k može biti izračunato i u konstantnom vremenu (množenje u konstantom (0^b1)^k). Napomenimo da je 1sketch(x_i) - 0y uvek pozitivno, ali čuva vodeću skicu 1 iff sketch(x_i) ≥ y. Mi na taj način možemo izračunati najmanji index i tako da sketch(x_i) ≥ y podrazumeva

1. Oduzimanjem z iz čvora
2. Uzeti razlike bitovskog „I“ i konstante (10^b)^k. Ovo briše sve osim vodećeg bita svakog bloka.
3. Naći najvažniji bit rezultata.
4. Izračunati i, koristeći činjenicu da je vodeći bit i-tog bloka imamindex i(b+1).

Dekompresovanje

Za proizvoljan upit, paralelna komparacija izračunava indeks i prema sledećoj formuli

sketch(x_i-1) ≤ sketch(q) ≤ sketch(x_i).

Nažalost, šema funkcije ne čuva kopiju ključeva tako da nije neophodno da x_i-1 ≤ q ≤ x_i. Šta je tačno u tome, od svih ključeva, bilo x_i-1 or x_i imaju najduži zajednički prefiks sa q. To je zato što bilo koji ključ y sa dužim prefiskom istim sa q, takođe ima više zajedničkih kompresovanih bitova sa q, i sketch(q) je mnogo sličniji sketch(x_j). Najduži zajednički prefiks između dva w-bitna cela broja a i b mogu biti izračunati u konstantnom vremenu, tako što se traži najznačajniji bit diskjunkcije od a i b. Ovo se može upotrebiti kao maska za sve bite sem za zajedničke prefiksne bitove. Napomenimo da p tačno definiše gde se q grananje završava.Ako je sledeći bit od q 0, onda se naslednik od q nalazi u p₁ podstablu, i ako je sledeći bit od q 1, onda se predak od q nalazi u p₀ podstablu. Ovo prati sledeći algoritam:

1. Koristi se paralelna komparacija da se nađe sledeći indeks i tako da važi sketchsketch(x_i-1) ≤ sketch(q) ≤ sketch(x_i).
2. Izračunava se najduzi zajednički prefiks od p i q, bilo x_i-1 ili x_i (uzima se duži od ova dva).
3. Neka je l-1 dužina najdužeg zajedničkog prefiksa sa p.
   1. Ako je l-ti bit od q jednak 0, onda je e = p10^w-l. Koristiti paralelnu komaparaciju da se nađe naslednik od sketch(e). To je u stvari predak od q.
   2. Ko je l-ti bit od q jednak 1, onda e = p01^w-l.Koristi se komparacija da se nađe predak od sketch(e). To je u stvari naslednik od q.
4. Kada jednom nađemo pretka ili naslednika od q, tačna pozicija q u grupi ključeva je određena.

Reference

1. M. L. Fredman and D. E. Willard. BLASTING through the information theoretic barrier with FUSION TREES. Proceedings of the twenty-second annual ACM symposium on Theory of Computing, 1-7, 1990.
2. A. Andersson, P. B. Miltersen, and M. Thorup. Fusion trees can be implemented with AC0 instructions only. Theoretical Computer Science, 215:337-344, 1999.
3. R. Raman. Priority queues: Small, monotone, and trans-dichotomous. Algorithms - ESA ’96, 121-137, 1996.
4. A. Andersson and M. Thorup. Dynamic ordered sets with exponential search trees. Journal of the ACM, 54:3:13, 2007.

• MIT CS 6.897: Advanced Data Structures: Lecture 4, Fusion Trees, Prof. Erik Demaine (Spring 2003)
• MIT CS 6.897: Advanced Data Structures: Lecture 5, More fusion trees; self-organizing data structures, move-to-front, static optimality, Prof. Erik Demaine (Spring 2003)
• MIT CS 6.851: Advanced Data Structures: Lecture 13, Fusion Tree notes, Prof. Erik Demaine (Spring 2007)
• MIT CS 6.851: Advanced Data Structures: Lecture 12, Fusion Tree notes, Prof. Erik Demaine (Spring 2012)