Fusieboom - Fusion tree

In de informatica is een fusieboom een soort boomgegevensstructuur die een associatieve array implementeert op w -bit gehele getallen. Wanneer het werkt met een verzameling van n sleutel-waardeparen , gebruikt het O ( n ) spatie en voert het zoekopdrachten uit in O (log w n ) tijd, wat asymptotisch sneller is dan een traditionele zelfbalancerende binaire zoekboom , en ook beter dan de van Emde Boasboom voor grote waarden van  w . Het bereikt deze snelheid door gebruik te maken van bepaalde constante-tijdbewerkingen die op een machinewoord kunnen worden uitgevoerd . Fusiebomen zijn in 1990 uitgevonden door Michael Fredman en Dan Willard .

Er zijn verschillende vorderingen gemaakt sinds het oorspronkelijke document van Fredman en Willard uit 1990. In 1999 werd getoond hoe fusiebomen geïmplementeerd konden worden onder een rekenmodel waarin alle onderliggende bewerkingen van het algoritme tot AC 0 behoren , een model van circuitcomplexiteit dat optellen en bitsgewijze Booleaanse bewerkingen toestaat, maar de vermenigvuldigingsbewerkingen die in de origineel fusion tree-algoritme. In 1996 werd een dynamische versie van fusionbomen met hashtabellen voorgesteld, die naar verwachting overeenkwam met de oorspronkelijke O (log w n ) runtime van de structuur . Een andere dynamische versie die een exponentiële boom gebruikt, werd voorgesteld in 2007, die in het slechtste geval een runtimes oplevert van O (log w n + log log n ) per bewerking. Het blijft open of dynamische fusiebomen met grote waarschijnlijkheid O (log w n ) per operatie kunnen bereiken .

Hoe het werkt

Een fusieboom is in wezen een B-boom met een vertakkingsfactor van w 1/5 (elke kleine exponent is ook mogelijk), waardoor deze een hoogte heeft van O (log w n ) . Om de gewenste runtimes voor updates en queries te bereiken, moet de fusion tree een knooppunt kunnen doorzoeken met maximaal w 1/5 sleutels in een constante tijd. Dit wordt gedaan door de toetsen te comprimeren ("schetsen") zodat ze allemaal in één machinewoord passen, waardoor vergelijkingen parallel kunnen worden uitgevoerd.

Schetsen

Schetsen is de methode waarmee elke w -bit-sleutel op een knooppunt dat k- sleutels bevat, wordt gecomprimeerd tot slechts k - 1 bits. Elke sleutel x kan worden gezien als een pad in de volledige binaire boom van hoogte w beginnend bij de wortel en eindigend bij het blad dat overeenkomt met x . Om twee paden te onderscheiden, volstaat het om naar hun vertakkingspunt te kijken (het eerste bit waar de twee sleutels verschillen). Alle k paden samen hebben k - 1 vertakkingspunten, dus er zijn maximaal k - 1 bits nodig om twee van de k sleutels te onderscheiden .

Visualisatie van de schetsfunctie.

Een belangrijke eigenschap van de schetsfunctie is dat deze de volgorde van de toetsen behoudt. Dat wil zeggen sketch ( x ) <sketch ( y ) voor twee willekeurige toetsen x < y .

De schets benaderen

Als de locaties van de schetsbits b 1 < b 2 <··· < b r zijn , dan is de schets van de sleutel x w -1 ··· x 1 x 0 het r -bit gehele getal .

Met alleen standaard woordbewerkingen, zoals die van de programmeertaal C , is het moeilijk om de schets van een sleutel direct in constante tijd te berekenen. In plaats daarvan kunnen de schetsbits worden verpakt in een bereik van maximaal r 4 , met behulp van bitsgewijze EN en vermenigvuldiging. De bitsgewijze AND-bewerking dient om alle niet-schetsbits uit de sleutel te verwijderen, terwijl de vermenigvuldiging de schetsbits naar een klein bereik verschuift. Net als de "perfecte" schets, behoudt de geschatte schets de volgorde van de toetsen.

Enige voorverwerking is nodig om de juiste vermenigvuldigingsconstante te bepalen. Elk schetsbit op locatie b i wordt verschoven naar b i + m i via een vermenigvuldiging met m = 2 m i . Om de geschatte schets te laten werken, moeten de volgende drie eigenschappen gelden:

  1. b i + m j zijn verschillend voor alle paren ( i , j ). Dit zorgt ervoor dat de schetsbits niet worden beschadigd door de vermenigvuldiging.
  2. b i + m i is een strikt toenemende functie van i . Dat wil zeggen, de volgorde van de schetsbits blijft behouden.
  3. ( b r + m r ) - ( b 1 + m 1 ) ≤ r 4 . Dat wil zeggen, de schetsbits zijn verpakt in een bereik van maximaal r 4 .

Een inductief argument laat zien hoe de m i kan worden geconstrueerd. Laat m 1 = w - b 1 . Stel dat 1 < t ≤ r en dat m 1 , m 2 ... m t-1 al is gekozen. Kies vervolgens het kleinste gehele getal m t zodat aan beide eigenschappen (1) en (2) wordt voldaan. Eigenschap (1) vereist dat m t ≠ b i - b j + m l voor alle 1 ≤ i , j ≤ r en 1 ≤ l ≤ t -1. Er zijn dus minder dan tr 2 ≤ r 3 waarden die m t moet vermijden. Aangezien m t minimaal is gekozen, ( b t + m t ) ≤ ( b t -1 + m t -1 ) + r 3 . Dit impliceert eigendom (3).

De geschatte schets wordt dus als volgt berekend:

  1. Maskeer alles behalve de schetsbits met een bitsgewijze EN.
  2. Vermenigvuldig de sleutel met de vooraf bepaalde constante m . Deze bewerking vereist eigenlijk twee machinewoorden, maar dit kan nog steeds in constante tijd worden gedaan.
  3. Maskeer alles behalve de verschoven schetsbits. Deze zitten nu in een aaneengesloten blok van maximaal r 4 < w 4/5 bits.

Parallelle vergelijking

Het doel van de compressie die wordt bereikt door te schetsen, is om alle sleutels in één w -bit-woord op te slaan . Laat de knooppuntschets van een knooppunt de bitreeks zijn

1 sketch ( x 1 ) 1 sketch ( x 2 ) ... 1 sketch ( x k )

We kunnen aannemen dat de schetsfunctie precies b ≤ r 4 bits gebruikt. Vervolgens gebruikt elk blok 1 + b ≤ w 4/5 bits, en aangezien k ≤ w 1/5 , is het totale aantal bits in de knooppuntschets maximaal w .

Een korte notatie terzijde: voor een bitstring s en een niet-negatief integer m , laat s m de aaneenschakeling van s naar zichzelf m keer aangeven. Als t ook een bit is, geeft st de aaneenschakeling van t naar s aan .

De knooppuntschets maakt het mogelijk om de sleutels te doorzoeken op elk b -bit geheel getal y . Laat z = (0 y ) k , dat kan worden berekend constante tijd (vermenigvuldigen y door de constante (0 b 1) k ). Merk op dat 1 sketch ( x i ) - 0 y altijd positief is, maar de eerste 1 iff sketch ( x i ) ≥ y behoudt . We kunnen dus de kleinste index i zo berekenen dat sketch ( x i ) ≥ y als volgt:

  1. Trek z af van de knooppuntschets.
  2. Neem de bitsgewijze EN van het verschil en de constante (10 b ) k . Dit wist alles behalve het voorste bit van elk blok.
  3. Zoek het belangrijkste deel van het resultaat.
  4. Bereken i , gebruikmakend van het feit dat het voorste bit van het i-de blok index i ( b +1) heeft.

Desketchen

Voor een willekeurige vraag q berekent parallelle vergelijking de index i zodanig dat

sketch ( x i -1 ) ≤ sketch ( q ) ≤ sketch ( x i )

Helaas is de schetsfunctie in het algemeen niet buiten de set sleutels om de volgorde te behouden, dus het is niet noodzakelijk het geval dat x i -1 ≤ q ≤ x i . Wat waar is, is dat van alle sleutels x i -1 of x i het langste gemeenschappelijke voorvoegsel met q heeft . Dit komt omdat elke sleutel y met een langer gemeenschappelijk voorvoegsel met q ook meer schetsbits gemeen zou hebben met q , en dus zou sketch ( y ) dichter bij sketch ( q ) zijn dan elke sketch ( x j ).

De lengte langste gemeenschappelijke prefix tussen twee w -bit gehele getallen a en b kan in constante tijd worden berekend door het meest significante bit van de bitsgewijze XOR tussen a en b te vinden . Dit kan vervolgens worden gebruikt om alles behalve het langste gemeenschappelijke voorvoegsel te maskeren.

Merk op dat p precies aangeeft waar q zich vertakt vanaf de set sleutels. Als het volgende bit van q 0 is, dan bevindt de opvolger van q zich in de p 1-substructuur, en als het volgende bit van q 1 is, dan is de voorganger van q opgenomen in de p 0-substructuur. Dit suggereert het volgende algoritme:

  1. Gebruik parallelle vergelijking om de index i zo te vinden dat sketch ( x i -1 ) ≤ sketch ( q ) ≤ sketch ( x i ).
  2. Bereken het langste gemeenschappelijke voorvoegsel p van q en x i -1 of x i (neem de langste van de twee).
  3. Laat l -1 de lengte zijn van het langste gemeenschappelijke voorvoegsel p .
    1. Als het l-de bit van q 0 is, laat e = p 10 w - l . Gebruik parallelle vergelijking om de opvolger van sketch ( e ) te zoeken. Dit is de feitelijke voorganger van q .
    2. Als de l -de bit van q 1 is, laat e = p 01 w - l . Gebruik parallelle vergelijking om te zoeken naar de voorganger van sketch ( e ). Dit is de daadwerkelijke opvolger van q .
  4. Zodra de voorganger of opvolger van q is gevonden, wordt de exacte positie van q in de set toetsen bepaald.

Fusion-hashing

Een toepassing van fusionbomen op hashtabellen werd gegeven door Willard, die een datastructuur voor hashing beschrijft waarin een hashtabel op het buitenste niveau met hash-chaining wordt gecombineerd met een fusionboom die elke hash-keten vertegenwoordigt. Bij hash-chaining, in een hashtabel met een constante belastingsfactor, is de gemiddelde grootte van een ketting constant, maar bovendien hebben alle ketens met grote waarschijnlijkheid de grootte O (log n / log log n ) , waarbij n het aantal gehashte items is . Deze kettingmaat is zo klein dat een fusieboom zoekopdrachten en updates erin kan verwerken in een constante tijd per bewerking. Daarom is de tijd voor alle bewerkingen in de gegevensstructuur constant met grote waarschijnlijkheid. Nauwkeuriger gezegd, deze gegevensstructuur voor elke inverse- quasipolynomial waarschijnlijkheid p ( n ) = exp ((log n ) O (1) ) , is er een constante C zodanig dat de kans dat er een bewerking die bestaat overschrijdt tijd C is hooguit p ( n ) .

Referenties

Externe links