PH-träd

PH-träd
Typ	träd, karta
Uppfunnet	2014
Tidskomplexitet i stor O-notation
Algoritm Genomsnitt Värsta fall Plats O( n ) O( n ) Sök O( log n ) O( log n ) Föra in O( log n ) O( log n ) Radera O( log n ) O( log n )

PH -trädet är en träddatastruktur som används för rumslig indexering av flerdimensionella data (nycklar) såsom geografiska koordinater, punkter, funktionsvektorer , rektanglar eller begränsningsrutor . PH-trädet är ett rymdpartitioneringsindex med en struktur som liknar den för ett quadtree eller okträd . Men till skillnad från quadtrees använder den en uppdelningspolicy baserad på försök och liknande Crit-bitträd som är baserad på bitrepresentationen av nycklarna. Den bitbaserade uppdelningspolicyn, i kombination med användningen av olika interna representationer för noder, ger skalbarhet med högdimensionell data. Bit-representationsdelningspolicyn kräver också ett maximalt djup och undviker på så sätt degenererade träd och behovet av ombalansering.

Översikt

Det grundläggande PH-trädet är ett rumsligt index som mappar nycklar, som är d -dimensionella vektorer med heltal, till användardefinierade värden. PH-trädet är en multidimensionell generalisering av ett Crit-bitträd i den meningen att ett Crit-bitträd är ekvivalent med ett PH-träd med $1$ -dimensionella nycklar. Liksom Crit-bitträdet, och till skillnad från de flesta andra rumsliga index, är PH-trädet en karta snarare än en multimap .

Ett d- dimensionellt PH-träd är ett träd av noder där varje nod delar upp utrymmet genom att dela upp det i $2^{d}$ kvadranter (se nedan för hur potentiellt stora noder skalas med högdimensionell data). Varje kvadrant innehåller högst en post , antingen ett nyckel-värdepar (lövkvadrant) eller ett nyckel-undernodspar. För ett nyckel-undernodpar representerar nyckeln mitten av undernoden. Nyckeln är också det gemensamma prefixet (bitrepresentation) för alla nycklar i subnoden och dess undernoder. Varje nod har minst två poster, annars slås den samman med den överordnade noden.

Några andra strukturella egenskaper hos PH-träd är:

• De är $2^{n}$ -ära träd.
• De är i sig obalanserade men obalansen är begränsad på grund av att deras djup är begränsat till bitbredden på nycklarna, t.ex. till 32 för en $d$ -dimensionell nyckel med 32 bitars heltal.
• Insättnings- eller borttagningsåtgärder gör att exakt en nod ändras och eventuellt en andra nod läggs till eller tas bort. Detta kan vara användbart för samtidiga implementeringar. Detta innebär också liten variation i modifieringskostnad.
• Deras struktur är oberoende av insättnings-/borttagningsordern.

Uppdelningsstrategi

I likhet med de flesta quadtrees är PH-trädet en hierarki av noder där varje nod delar upp utrymmet i alla d dimensioner. Således kan en nod ha upp till $2^{d}$ subnoder, en för varje kvadrant.

Hyperkubadressering med bitsträngar

Kvadrantnumrering

PH-trädet använder bitarna av de flerdimensionella nycklarna för att bestämma deras position i trädet. Alla nycklar som har samma inledande bitar lagras i samma gren av trädet.

Till exempel, i en nod på nivå L , för att bestämma kvadranten där en nyckel ska infogas (eller tas bort eller slås upp), tittar den på L: s bit för varje dimension av nyckeln. För en 3D-nod med 8 kvadranter (som bildar en kub) L :s bit av nyckelns första dimension om målkvadranten är till vänster eller höger om kuben, L:s bit av den andra dimensionen avgör om det är framtill eller baktill, och L :s bit i den tredje dimensionen avgör botten mot toppen, se bild.

Exempel på ett PH-träd med tre nycklar tillagda, vilket resulterar i två noder. En rotnod (röd) och en subnod (blå).

1D exempel

Exempel med tre 1D-nycklar med 8-bitars värden: $k_{0}=\{1\}_{base\ 10}=\{ 00000001\}_{bas\ 2}$ , $k_{1}=\{4\}_{10}=\{00000100\}_{2}$ och $k_{2}=\{35\}_{10}=\{00100011\}_{2}$ . Att lägga till $k_{0}$ och $k_{1}$ till ett tomt träd resulterar i en enda nod. De två nycklarna skiljer sig först i sin 6:e bit så noden har en nivå $L=5$ (börjar med 0). Noden har ett 5-bitars prefix som representerar de gemensamma 5 bitarna för båda nycklarna. Noden har två kvadranter, varje nyckel lagras i en kvadrant. Att lägga till en tredje nyckel $k_{3}$ resulterar i ytterligare en nod vid $L=2$ med en kvadrant som innehåller den ursprungliga noden som subnod och den andra kvadranten innehåller den nya nyckeln ${ \displaystyle k_{2}}$ .

Exempel på ett PH-träd med två 2D-nycklar i en nod

2D exempel

Med 2D-nycklar har varje nod $2^{d}=4$ kvadranter. Placeringen av kvadranten där en nyckel är lagrad extraheras från respektive bitar av nycklarna, en bit från varje dimension. Nodens fyra kvadranter bildar en 2D hyperkub (kvadranter kan vara tomma). Bitarna som extraheras från nycklarna bildar hyperkubadressen $h$ , för $k_{0}\rightarrow h=\{00\}_{2}$ och för $k_{1}\rightarrow h=\{01\}_{2}$ . $h$ är faktiskt positionen för kvadranten i nodens hyperkub.

Nodstruktur

Ordningen av posterna i en nod följer alltid Z-ordning . Poster i en nod kan till exempel lagras i arrayer med fast storlek av storlek $2^{d}$ . h är då i praktiken arrayindex för en kvadrant. Detta tillåter att slå upp, infoga och ta bort med $O(1)$ och det finns inget behov av att lagra h . Utrymmeskomplexiteten är dock $O(2^{d})$ per nod, så den är mindre lämplig för högdimensionella data.

En annan lösning är att lagra poster i en sorterad samling, såsom dynamiska arrayer och/eller B-träd . Detta saktar ner uppslagsoperationerna till $O(\log {n_{node\_entries}})$ men minskar minnesförbrukningen till $O(n_{nod\_entries})$ .

Den ursprungliga implementeringen syftade till minimal minnesförbrukning genom att växla mellan fast och dynamisk array-representation beroende på vilken som använder mindre minne. Andra implementeringar [1] [2] växlar inte dynamiskt utan använder fasta arrayer för ${\displaystyle d\lesssim 4} ,$ dynamiska arrayer för $d\lesssim 8$ och B-träd för högdimensionella data.

Operationer

Uppslags- , infognings- och borttagningsoperationer fungerar alla väldigt lika: hitta rätt nod och utför sedan operationen på noden. Fönsterfrågor och k -närmaste-granne- sökningar är mer komplexa.

Slå upp

Uppslagsoperationen avgör om det finns en nyckel i trädet. Den går ner i trädet och kontrollerar varje nod om den innehåller en kandidatundernod eller ett användarvärde som matchar nyckeln.

 funktion  lookup(nyckel)  är  ingång ← get_root_entry() // om trädet inte är tomt innehåller rotposten en rotnod  medan  entry != NIL && entry.is_subnode()  do  node ← entry.get_node() entry ← node.get_entry (nyckel)  upprepa  returinmatning  // inmatning kan vara NIL 

 -funktion  get_entry(nyckel)  är  nod ← aktuell nod h ← extrahera_bitar_vid_djup(nyckel, nod.get_djup()} ingång ← nod.get_entry_at(h)  returpost  // ingång kan vara NIL 

Föra in

Operationen Infoga infogar ett nytt nyckel-värdepar i trädet om inte nyckeln redan finns. Operationen korsar trädet som Lookup -funktionen och infogar sedan nyckeln i noden. Det finns flera fall att ta hänsyn till:

1. Kvadranten är tom och vi kan helt enkelt infoga en ny post i kvadranten och återvända.
2. Kvadranten innehåller en användarpost med en nyckel som är identisk med den nya posten. Ett sätt att hantera en sådan kollision är att returnera en flagga som indikerar misslyckad infogning. Om trädet är implementerat som multi-map med en samling som nodens post, läggs det nya värdet till den samlingen.
3. Kvadranten innehåller en post (användarpost eller subnodpost) med en annan nyckel. Det här fallet kräver att den befintliga posten ersätts med en ny subnod som innehåller den gamla och den nya posten.

 function  insert(nod, nyckel, värde) nivå ← node.get_level() // Nivå är 0 för rot h ← extrahera_bitar_på_nivå(nyckel, nivå) ingång ← node.get_entry(h)  om  ingång == NIL  då  // Fall 1. entry_new ← create_entry   (  key, value) node.set_entry(h, entry_new)  else if  !entry.is_subnode() && entry.get_key() == nyckel  sedan  // Fall 2. Kollision, det finns redan en entry  return  ← failed_insertion  // Fall 3. level_diff ← get_level_of_difference(nyckel, entry.get_key()) entry_new ← create_entry(nyckel, värde) // ny subnod med befintlig ingång och ny post subnod_new ← create_node(level_diff._ny)(nivå_diff._ny)(nivå_diff._ny) , subnode_new)  end if  return 

Avlägsna

Borttagning fungerar omvänt mot infogning, med den ytterligare begränsningen att varje subnod måste tas bort om mindre än två poster återstår. Den återstående posten flyttas till den överordnade noden.

Fönsterfrågor

Windows-frågor är frågor som returnerar alla nycklar som ligger inuti en hyperbox med rektangulär axel. De kan definieras som två d -dimensionella punkter $min$ och $max$ som representerar de "nedre vänstra" och "övre högra" hörnen av frågerutan. En trivial implementering går igenom alla poster i en nod (som börjar med rotnoden) och om en post matchar läggs den antingen till resultatlistan (om det är en användarpost) eller går den rekursivt (om det är en subnod).

    
        
            
        
            
        
    
 funktion  query(nod, min, max, resultatlista)  är  för varje  post ← node.get_entries()  gör  om  entry.is_subnode()  sedan  om  entry.get_prefix() >= min och entry.get_prefix() <= max  sedan  query(entry) .get_subnode(), min, max, result_list)  end if  else  if  entry.get_key() >= min och entry.get_key() <= max  sedan  result_list.add(entry)  end if  end if  repeat  returnera 

För att exakt uppskatta frågetidskomplexiteten måste analysen inkludera dimensionaliteten $d$ . Att korsa och jämföra alla $n_{nod\_entries}$ poster i en nod har en tidskomplexitet på $O(d*n_{node\_entries})$ eftersom varje jämförelse av $d$ -dimensionell nyckel med $min/max$ tar $O(d)$ tid. Eftersom noder kan ha upp till $2^{d}$ poster, skalas detta inte bra med ökande dimensionalitet $d$ . Det finns olika sätt hur detta tillvägagångssätt kan förbättras genom att använda hyperkubadressen h .

Min h & max h

Tanken är att hitta minimi- och maxvärden för kvadrantens adresser $h$ så att sökningen kan undvika vissa kvadranter som inte överlappar frågerutan. Låt $C$ vara mitten av en nod (detta är lika med nodens prefix) och $h_{min}$ och $h_{max}$ vara två bitsträngar med $d$ bitar vardera. Låt också subscript $i$ med $0\leq i<d$ indikera $i$ :s bit av $h_{min}$ och $h_{max}$ och $i$ ':te dimensionen av $min$ , $max$ och $C$ .

Låt $h_{min,i}=(min_{i}\leq C_{i})$ och $h_{max,i}=(max_{i}\geq C_{i})$ . $h_{min}$ har sedan en ` $1$ ` för varje dimension där den "nedre" halvan av noden och alla kvadranter i den inte överlappar med frågerutan. På liknande sätt $h_{min}$ en ` $0$ ` för varje dimension där den "övre" halvan inte överlappar frågerutan.

$h_{min}$ och $h_{max}$ presenterar sedan den lägsta och högsta $h$ i en nod som måste passeras. Kvadranter med $h<h_{min}$ eller $h>h_{max}$ skärs inte med frågerutan. Ett bevis är tillgängligt i. Med detta kan ovanstående frågefunktion förbättras till:

 funktionsfråga  (nod, min, max, resultatlista)  är  h_min ← beräkna h_min h_max ← beräkna h_max  för varje  post ← node.get_entries_range(h_min, h_max)  gör  [ ... ]  upprepa  retur 

Att beräkna $h_{min}$ och $h_{max}$ är $O(2*d)=O( d)$ . Beroende på fördelningen av de ockuperade kvadranterna i en nod kommer detta tillvägagångssätt att göra det möjligt att undvika allt från nej till nästan alla nyckeljämförelser. Detta minskar den genomsnittliga genomgångstiden men den resulterande komplexiteten är fortfarande $O(d+d*n_{node\_entries})$ .

Kontrollera kvadranter för överlappning med frågerutan

Mellan $h_{min}$ och $h_{max}$ kan det fortfarande finnas kvadranter som inte överlappar med frågerutan. Idé: $h_{min}$ och $h_{max}$ har vardera en bit för varje dimension som indikerar om frågerutan överlappar den nedre/övre halvan av en nod i den dimensionen. Detta kan användas för att snabbt kontrollera om en kvadrant $h$ överlappar frågerutan utan att behöva jämföra $d$ -dimensionella nycklar: en kvadrant $h$ överlappar frågerutan om för varje ` $0$ ` bit i $h$ finns det en motsvarande ` $0$ ` bit i $h_{min}$ och för varje ` $1$ ` bit i $h$ det finns en motsvarande ` $1$ ` bit i $h_{max}$ . På en CPU med 64-bitars register är det alltså möjligt att kontrollera överlappning av upp till $64$ -dimensionella nycklar i $O(1)$ .

 funktionen  is_overlap(h, h_min, h_max)  är  retur  (h | h_min) & h_max == h // utvärderas till "true" om kvadrant och fråga överlappar varandra. 

    
 funktionsfråga  (nod, min, max, resultatlista)  är  h_min ← beräkna h_min h_max ← beräkna h_max  för varje  post ← node.get_entries_range(h_min, h_max)  do  h ← entry.get_h();  if  (h | h_min) & h_max == h  då  // utvärderas till "true" om kvadrant och fråga överlappar varandra. [ ... ]   avslutas om  upprepa  retur 

Den resulterande tidskomplexiteten är $O(d+n_{nod\_entries})$ jämfört med $O(d*n_{node\_entries})$ av den fullständiga iterationen.

Traversera kvadranter som överlappar med frågerutan

För högre dimensioner med större noder är det också möjligt att undvika att iterera genom alla $h$ och istället direkt beräkna nästa högre $h$ som överlappar frågerutan. Det första steget lägger ` $1$ `-bitar i en given $h_{input}$ för alla kvadranter som inte har någon överlappning med frågerutan. Det andra steget ökar de anpassade $h$ och de tillagda ` $1$ `-bitarna utlöser ett spill så att de icke-överlappande kvadranterna hoppas över. Det sista steget tar bort alla oönskade bitar som används för att utlösa överflödet. Logiken beskrivs i detalj i. Beräkningen fungerar enligt följande:

 funktion  increment_h(h_input, h_min, h_max)  är  h_out = h_input | (~ h_max ) // förmask h_out += 1 // inkrement h_out = ( h_out & h_max ) |  h_min // post - mask   returnera  h_out 

Återigen, för $d\leq 64$ kan detta göras på de flesta CPU:er i $O(1)$ . Den resulterande tidskomplexiteten för att korsa en nod är $O(d+n_{överlappande\_kvadranter})$ . Detta fungerar bäst om de flesta kvadranter som överlappar med frågerutan är upptagna med en post.

k -närmaste grannar

k närmaste grannsökningar kan implementeras med hjälp av standardalgoritmer.

Flyttalsnycklar

PH-trädet kan bara lagra heltalsvärden. Flyttalsvärden kan trivialt lagras som heltal och ger dem ett heltal. Men författarna till föreslår också ett tillvägagångssätt utan förlust av precision.

Förlustfri konvertering

Förlustfri omvandling av ett flyttalsvärde till ett heltalsvärde (och tillbaka) utan förlust om precision kan uppnås genom att helt enkelt tolka de 32 eller 64 bitarna av flyttalsvärdet som ett heltal (med 32 eller 64 bitar). På grund av hur IEEE 754 kodar flyttalsvärden har de resulterande heltalsvärdena samma ordning som de ursprungliga flyttalsvärdena, åtminstone för positiva värden. Beställning för negativa värden kan uppnås genom att invertera icke-teckenbitarna.

Exempel på implementeringar i Java :

   
       
       0      
 long  encode  (  dubbelt  värde  )  {  long  r  =  Double  .  doubleToRawLongBits  (  värde  );  returnera  (  r  >=  )  ?  r  :  r  ^  0x7FFFFFFFFFFFFFFFL  ;  } 

Exempel på implementeringar i C++ :

   
     
      
       0      
 std  ::  int64_t  kodning  (  dubbelt  värde  )  {  std  ::  int64_t  r  ;  memcpy  (  &  r  ,  &  värde  ,  storlek på  (  r  ));  returnera  r  >=  ?  r  :  r  ^  0x7FFFFFFFFFFFFFFFL  ;  } 

Kodning (och den omvända avkodningen) är förlustfri för alla flyttalsvärden. Beställningen fungerar bra i praktiken, inklusive $\pm \infty$ och $-0.0$ . Heltalsrepresentationen gör emellertid också $NaN$ till ett normalt jämförbart värde (mindre än oändlighet), oändligheter är jämförbara med varandra och $0.0$ är större än $-0.0$ . Det betyder att till exempel ett frågeintervall $[0.0,10.0]$ inte kommer att matcha värdet $-0.0$ . För att matcha $-0.0$ måste frågeintervallet vara $[-0.0,10.0]$ .

Hyperbox nycklar

För att lagra volymer (axeljusterade hyperboxar) som nycklar använder implementeringar vanligtvis hörnrepresentation som omvandlar de två $d$ -dimensionella minimum- och maximihörnen av en ruta till en enda nyckel med ${\ displaystyle 2*d}$ dimensioner, till exempel genom att interfoliera dem: $k=\{min_{0},max_{0},min_{1},max_{1},...,min_{d- 1},max_{d-1}\}$ .

Detta fungerar trivialt för att slå upp, infoga och ta bort operationer. Fönsterfrågor måste konverteras från $d$ -dimensionella vektorer till $2*d$ -dimensionella vektorer. Till exempel, för en fönsterfråga som matchar alla rutor som är helt inuti frågerutan, är frågenycklarna:

$k_{min}=\{min_{0},min_{0},min_{1},min_{1},...,min_ {d-1},min_{d-1}\}$

$k_{max}=\{max_{0},max_{0},max_{1},max_{1},...,max_ {d-1},max_{d-1}\}$

För en fönsterfrågeoperation som matchar alla rutor som skär en frågeruta, är frågenycklarna:

$k_{min}=\{-\infty ,min_{0},-\infty ,min_{1},...,-\infty ,min_{d -1}\}$

$k_{max}=\{max_{0},+\infty ,max_{1},+\infty ,...,max_{d-1}, +\infty \}$

Skalbarhet

I höga dimensioner med mindre än ${\displaystyle 2^{d}}-$ poster kan ett PH-träd bara ha en enda nod, som i praktiken "degenererar" till ett B-träd med Z-ordningskurva . Åtgärderna lägg till/ta bort/slå upp förblir $O(\log {n})$ och fönsterfrågor kan använda kvadrantfiltren . Detta kan dock inte undvika dimensionalitetens förbannelse , för högdimensionella data med $d=50$ eller $d=100$ är ett PH-träd endast marginellt bättre än en full scan.

Används

Forskning har rapporterat snabba lägg till/ta bort/exakt matcha operationer med stora och snabbt föränderliga datauppsättningar. Fönsterfrågor har visat sig fungera bra, särskilt för små fönster eller stora datauppsättningar

PH-trädet är främst lämpat för användning i minnet. Storleken på noderna (antal poster) är fast medan beständig lagring tenderar att dra nytta av index med konfigurerbar nodstorlek för att anpassa nodstorleken med sidstorleken på disken. Detta är lättare med andra rumsliga index, som R-Trees .

Genomföranden

• Java: GitHub-förråd av den ursprungliga uppfinnaren
• C++: GitHub-förråd av den ursprungliga uppfinnaren
• C++: GitHub-förråd
• C++: GitHub-förråd

Se även

• Binär rymduppdelning
• Binär plattsättning
• k -d träd
• Octree
• Quadtree
• R-träd
• UB-träd
• Rumslig databas

externa länkar

• PH-tree hemsida med detaljerad beskrivning, exempel och prestandajämförelse