Hilbert R-træ

Et Hilbert R-træ , en variant af et R-træ , er en indeksering af multidimensionelle objekter såsom linjer, todimensionelle områder, tredimensionelle objekter eller parameteriserede objekter af højere dimensioner. De kan forstås som en udvidelse af B+-træer til multidimensionelle objekter.

Ydeevnen af ​​R-træer afhænger af kvaliteten af ​​den algoritme, der grupperer dataene i rektangler. R-træer bruger rumudfyldende kurver , mere specifikt Hilbert-kurver , til at arrangere objekter lineært i rektangler.

Der er to typer Hilbert R-træer, en til statiske data og en til dynamiske data. I begge tilfælde bruges rumfyldende Hilbert-kurver for at opnå bedre rækkefølge af flerdimensionelle objekter. Denne rækkefølge er "god" i den forstand, at den bør gruppere "lignende" data i rektangler, hvilket minimerer arealet og omkredsen af ​​disse Minimum Bounding Rectangles (MBR) Pakkede Hilbert R-træer er velegnede til statiske data, der opdateres meget sjældent eller slet ikke.

Dynamiske Hilbert R-Trees er velegnede til mutable data, hvor indsættelser, sletninger eller opdateringer sker i realtid. Ydermere bruger dynamiske Hilbert R-træer en fleksibel udskudt flækkemekanisme, som forbedrer pladshåndteringen. Hver node har et veldefineret sæt af søskende (enlige forælder) noder. Ved at justere spaltningspolitikken, ved hjælp af Hilbert R-træer, kan man få graden af ​​rumbehandling på det ønskede niveau. Hilbert R-træer sorterer rektanglerne efter Hilbert-afstandene for rektanglernes centre (MBR). (Hilbert-afstanden af ​​et punkt er lig med længden af ​​Hilbert-kurven fra begyndelsen af ​​kurven til punktet.). I modsætning hertil har andre varianter af R-træer ingen mekanismer til styring af pladshåndtering.

Hovedidé

Selvom det følgende eksempel refererer til et statisk miljø, forklarer det de intuitive principper bag at bygge gode R-træer. Disse principper gælder for både statiske og dynamiske data. Roussopoulos og Leifker foreslog en metode til at konstruere et pakket R-træ, der opnår næsten 100% forarbejdning. Ideen er at sortere dataene efter x- eller y-koordinater fra det ene hjørne af rektanglet. Sortering efter et af de fire hjørner giver lignende resultater. I denne artikel er punkter og rektangler sorteret i forhold til x-koordinaten for det nederste venstre hjørne af rektanglet, og metoden fra Roussopoulos og Leifker vil blive kaldt det "x-pakkede R-træ". Metoden går gennem en sorteret liste af rektangler. Successive rektangler tildeles det samme blad i R-træet, indtil noden er fuld. Derefter oprettes et nyt ark, og gennemsyn af den sorterede liste fortsætter. Således vil knudepunkterne i det resulterende R-træ være fuldstændig pakket, med mulig undtagelse af den sidste knude på hvert niveau. Rumbehandlingen er således tæt på 100 %. Højere niveauer af træet skabes på samme måde.

Figur 1 viser problemerne med x-pakkede R-træer. Figuren (højre) viser R-træknuderne opnået ved denne metode for punkterne vist til venstre. Det faktum, at de resulterende overordnede noder dækker et lille område, forklarer den hurtige nedbrydning af anmodninger om point. Den store omkreds af rektanglerne forklarer imidlertid, hvorfor forespørgsler om områder hurtigt forringes. Dette er i overensstemmelse med de analytiske formler for ydeevnen af ​​R-træer [1] . Det er intuitivt klart, at pakningsalgoritmen skal tildele tætte punkter til den samme node. At ignorere y-koordinaten ved et "x-pakket R-træ" overtræder denne tommelfingerregel.

Figur 1: [Venstre] 200 jævnt fordelte prikker. [Højre] MBR af noder genereret af " R-tree x-packing " -algoritmen

Hilbert-kurve

Den indledende Hilbert-kurve på et 2x2 gitter, betegnet H 1 , er vist i figur 2. For at opnå en kurve af orden i erstattes hvert hjørne af hovedkurven af ​​en kurve af orden i - 1, roteret og/eller reflekteret som nødvendig. Figur 2 viser også Hilbert-kurverne af orden to og tre. Da kurvens rækkefølge har en tendens til uendelig, som andre rumudfyldende kurver, bliver kurven til en fraktal med en fraktal dimension på to [1] [2] . Hilbert-kurven kan generaliseres til højere dimensioner. En algoritme til at tegne en todimensionel kurve af en given rækkefølge kan findes i Griffiths [3] og Jagadish [2] . En algoritme for højere dimensioner blev givet af Bialli [4] .

Den rumfyldende kurve skaber en lineær rækkefølge af gitterpunkterne. Denne sti kan bygges ved at starte fra den ene ende af kurven til den anden og passere alle punkter til enden af ​​kurven. Figur 2 viser en sådan rækkefølge for et 4x4 gitter (se kurve H 2 ). For eksempel har punkt (0,0) på kurve H 2 afstand 0, og punkt (1,1) har afstand 2. Hilbert-afstanden af ​​et rektangel er per definition Hilbert-afstanden af ​​dets centrum.

Figur 2: Hilbert-kurver af orden 1, 2 og 3

Pakkede Hilbert R-træer

Hilbert-kurven definerer en lineær rækkefølge på datarektanglerne. Når vi går gennem den ordnede liste, tildeler vi hvert sæt rektangler til en node i R-træet. Som et resultat vil mange datarektangler på den samme node være tæt på hinanden i lineær rækkefølge og højst sandsynligt tæt på det naturlige rum. Således vil de resulterende knudepunkter i R-træet have et lille område. Figur 2 viser årsagerne til, at metoder baseret på Hilbert-kurver fører til god ydeevne. Dataene består af punkter (samme som i figur 1). Ved at gruppere punkterne efter deres Hilbert-afstande er MBR'erne for de resulterende R-træknuder normalt små, næsten kvadratiske rektangler. Dette betyder, at noder sandsynligvis har små områder og omkredse. Små områdeværdier resulterer i god forespørgselsydeevne for point. Små områder og små omkredse resulterer i god ydeevne til store forespørgsler.

Hilbert-Pack Packing Algorithm

(R-tree rektangel pakningsalgoritme)
Trin 1. Beregn Hilbert-afstanden for hvert datarektangel
Trin 2. Sorter rektanglerne ved at stigende Hilbert-afstand
Trin 3. /* Opret blade (niveau l = 0) */

Trin 4. /* Opret noder på niveau ( l + 1) */

Dette forudsætter, at dataene er statiske eller ændres sjældent. Algoritmen er en simpel heuristisk algoritme til at konstruere et R-træ med 100% pladshåndtering og har desuden en god responstid.

Hilbert dynamiske R-træer

Ydeevnen af ​​R-træer afhænger af kvaliteten af ​​algoritmen til at klynge data i rektangler ved en knude. Hilbert R-træer bruger rumudfyldende kurver med lineær rækkefølge af rektangler. Hilbert-afstanden af ​​et rektangel er per definition lig med afstanden til dets centrum.

Træstruktur

Hilbert R-træet har følgende struktur. Bladet indeholder et maksimum af C l -elementer, hver af formen (R, obj _id), hvor C l er bladets kapacitet, R er MBR for det virkelige objekt (x lav , x høj , y lav , y high ), og obj-id er pointer til objektbeskrivelsesindgangen. Den største forskel mellem et Hilbert R-træ og et R*-træ [5] er, at ikke-bladknuder indeholder LHV (Largest Hilbert Value) information. Således indeholder ikke-bladknuder i R-træet højst C n elementer af formen (R, ptr, LHV), hvor C n er kapaciteten af ​​ikke-bladsknuden, R er den MBR, der omfatter alle efterkommere af denne node, ptr er pointeren pr. barn, og LHV er den største Hilbert-afstand af dataene i afgrænsningsramme R. Bemærk, at da en ikke-bladsknude har Hilbert-afstanden for et af sine børn som LHV, er der ingen ekstra omkostninger til at beregne Hilbert-afstandene MBR for ikke-bladsknuder. Figur 3 illustrerer nogle kasser organiseret i et Hilbert R-træ. Hilbert-afstandene for centrene er tallene omkring "x"-symbolerne (vist kun for "II"-overordnet node). LHV-værdier er angivet i [parentes]. Figur 4 viser, hvordan træet i figur 3 er lagret på disk. Indholdet af den overordnede node "II" er vist mere detaljeret. Ethvert "I"-knudedatarektangel har en værdi på v ≤33. Ligeledes har ethvert knuderektangel "II" en Hilbert-afstand større end 33 og mindre end 107, og så videre.

Figur 3: Databokse organiseret i et Hilbert R-træ (Hilbert-afstande og LHV-værdier er i parentes)

Et simpelt R-træ bryder en node ved overløb og skaber to noder. Denne politik kaldes 1-til-2-delingspolitikken. Du kan udskyde opdeling og konvertere to noder til tre. Bemærk, at denne politik ligner B*-træets partitioneringspolitik. Denne metode kaldes 2-til-3-delingspolitikken. I det generelle tilfælde kan vi tale om spaltningspolitikken s-in-(s+1), hvor s er rækkefølgen af ​​spaltningspolitikken. For at implementere opdelingspolitikken for ordre s, forsøger en overfyldt node at sætte nogle noder ind i en af ​​sine s - 1 slægtninge (knuder på samme niveau). Hvis de alle er udfyldt, skal du opdele s-i-(s+1). Disse s -1 slægtninge kaldes samarbejdsknuder. Søge-, indsættelses- og overløbshåndteringsalgoritmerne er beskrevet detaljeret nedenfor.

Søg

Søgealgoritmen ligner algoritmer i andre varianter af R-træer. Startende fra roden går algoritmen ned i træet og kontrollerer alle buer, der skærer søgerektanglet. På arket inkluderer algoritmen alle elementer i forespørgselsvinduet, der blev fundet.

Procedure Find (node ​​rod, rektangel w):
S1. Leder du efter noder, der ikke er blade:

Vi starter søgningen efter hvert element, hvis MBR falder ind i forespørgselsvinduet w.

S2. Bladsøgning:

Vi lister alle de elementer, der falder ind i forespørgselsvinduet, som kandidater.

Figur 4: Struktur af Hilbert R-tree filen

Indsæt

For at indsætte et nyt rektangel r i Hilbert R-træet, bruges Hilbert-afstanden h for midten af ​​det nye rektangel som en nøgle. På hvert niveau, blandt alle niveauets elementer, vælges en node med en minimum LHV-værdi større end h. Hvis bladet nås, indsættes rektanglet r i det i den rigtige rækkefølge efter værdien af ​​h. Efter at det nye rektangel er indsat i blad N, køres træafstemningsproceduren for at ændre MBR- og LHV-værdierne ved noder på højere niveau.

Procedure Insert(Rod node, rektangel r) : /* Indsætter et nyt rektangel r i Hilbert R-træet.
h er Hilbert-afstanden af ​​rektanglet*/
I1. Sådan finder du det rigtige ark:

CallSearchList (r, h) for at vælge det ark L, hvori r skal inkluderes.

I2. Indsæt r i ark L:

Hvis L har en tom spalte, skal du indsætte r i L til et passende sted i henhold til rækkefølgen af ​​Hilbert-afstande og retur. Hvis L er fuld, skal du kalde proceduren Håndter overløb (L,r), som returnerer et nyt blad, hvis der er behov for opdeling,

I3. Udbredelse af ændringerne:

Vi danner et sæt S indeholdende L, kooperative noder og et nyt ark (hvis der er et) Vi starter proceduren Matching the Tree (S).

I4. Forøgelse af træets højde:

Hvis udbredelse af ændringer forårsager rodsplit, skal du oprette en ny rod, hvis børn er de to noder, der er et resultat af opsplitning af roden.

Fremgangsmåde FindSheet(rektangel r, heltal h) :
/* Returnerer det ark, hvor det nye rektangel r skal placeres. */
C1. Initialisering:

Sæt N som rod.

C2. Arkkontrol:

Hvis N er et blad, returneres N.

C3. Valg af et undertræ:

Hvis N ikke er et blad, skal du vælge element (R, ptr, LHV) med en minimum LHV større end h.

C4. Vi går ned, indtil vi når bladet:

Indstil N til den node, der peges på af ptr, og gentag processen fra punkt C2.

Procedure Træafstemning (sæt S) :
/* S er det sæt af noder, der indeholder de noder, der skal ændres,
deres samarbejdende noder (hvis et overløb opstod)
og den oprettede NN-node (hvis en nodeopdeling blev udført).
Proceduren stiger fra bladet til roden, og ændrer MBR og LHV for de noder, der dækker noderne i S.
Proceduren håndterer nodeopdelinger (hvis nogen) */
A1. Hvis vi når roden, stopper vi.
A2. Behandler nodeopdelinger:

Lad Np være forælderen til node N. Hvis node N er blevet opdelt, lad NN være den nye node. Indsæt NN i Np i den rigtige rækkefølge i henhold til dens Hilbert-afstand, hvis der er plads. Ellers kalder vi proceduren Overløbshåndtering (Np , NN ). Hvis node Np er blevet opdelt, lad PP være den nye node.

A3. Skift MBR- og LHV-værdierne på overordnet niveau:

Lad P være sættet af overordnede noder for noder i S. Vi ændrer de tilsvarende MBR- og LHV-værdier i P-knuderne.

A4. Gå videre til næste niveau:

S bliver sættet af forældreknuder P, NN = PP hvis Np blev delt. gå til A1.

Fjernelse

I et Hilbert R-træ er der ingen grund til at genindsætte dinglende knudepunkter, før den overordnede knude forsvinder. I stedet bliver nøgler, der kan tages fra underliggende noder, slået sammen med elementer på samme niveau. Dette er muligt, fordi noderne har en klar rækkefølge (ifølge LHV). Derimod findes der ikke et sådant koncept for R-træer. Bemærk, at sletningsoperationen kræver s samarbejdende noder, mens indsættelsesoperationen kræver s - 1 elementer.

Procedure Slet(r) :
D1. Find et ark:

Vi søger efter den nøjagtige forekomst af arket L, som indeholder r.

D2. Fjern r:

Fjern r fra node L.

D3. Hvis L er tom

vi tager nogle elementer fra de samarbejdende noder. hvis der ikke er sådanne elementer, bring s + 1 noder til s noder, genberegne de modtagne noder.

D4. Vi ændrer værdierne for MBR og LHV på overordnede niveauer.

danne et sæt S indeholdende L og dets kooperativ noder (hvis der opstår et overløb). ring til MatchTree(S).

Overløbshåndtering

Overløbshåndteringsproceduren i et Hilbert R-træ håndterer overløbsknuder enten ved at flytte nogle elementer til en af ​​s - 1 co-op noderne eller ved at opdele s noder i s + 1 noder.

Procedure Overløbshåndtering(node ​​N, rektangel r) :
/* returnerer en ny node, hvis der er sket en opdeling. */
H1. Lad ε være en mængde, der indeholder alle elementer fra N

og dens s - 1 samvirkende knudepunkter.

H2. Vi tilføjer r til ε.
H3. Hvis mindst en af ​​de s - 1 samvirkende knudepunkter ikke er udfyldt,

fordel ε ensartet over s i henhold til Hilbert-afstandene.

H4. Hvis alle s samarbejdsknudepunkter er fyldt,

opret node NN og fordel ε jævnt over s + 1 noder i henhold til Hilbert-afstande retur N.N.

Noter

  1. ↑ 1 2 Kamel, Faloutsos, 1993 , s. 490-499.
  2. ↑ 1 2 Jagadish, 1990 , s. 332-342.
  3. ↑ Griffiths, 1986 , s. 403-411.
  4. ↑ Bially, 1969 , s. 658-664.
  5. ↑ Beckmann, Kriegel, Schneider, Seeger 1990 , s. 322.

Litteratur