Arborele R Hilbert

Un arbore R Hilbert , o variantă a arborelui R , este o indexare a obiectelor multidimensionale, cum ar fi linii, regiuni bidimensionale, obiecte tridimensionale sau obiecte parametrizate de dimensiuni mai mari. Ele pot fi înțelese ca o extensie a arborilor B+ la obiecte multidimensionale.

Performanța arborilor R depinde de calitatea algoritmului care grupează datele în dreptunghiuri. Arborii R folosesc curbe de umplere a spațiului , mai precis curbele Hilbert , pentru a aranja obiectele liniar în dreptunghiuri.

Există două tipuri de arbori R Hilbert, unul pentru date statice și unul pentru date dinamice. În ambele cazuri, curbele Hilbert de umplere a spațiului sunt utilizate pentru a obține o ordonare mai bună a obiectelor multidimensionale. Această ordonare este „bună” în sensul că ar trebui să grupeze datele „similare” în dreptunghiuri, minimizând aria și perimetrul acestor dreptunghiuri de limite minime (MBR) Arborele Hilbert R împachetat sunt potriviți pentru datele statice care sunt actualizate foarte rar sau deloc.

Dynamic Hilbert R-Trees sunt potrivite pentru date mutabile în care inserările, ștergerile sau actualizările au loc în timp real. În plus, arborii dinamici Hilbert R folosesc un mecanism flexibil de împărțire amânată, care îmbunătățește gestionarea spațiului. Fiecare nod are un set bine definit de noduri frați (monoparentale). Prin ajustarea politicii de divizare, cu ajutorul arborilor Hilbert R, puteți obține gradul de prelucrare a spațiului la nivelul dorit. Arborii R Hilbert sortează dreptunghiurile în funcție de distanțele Hilbert ale centrelor dreptunghiurilor (MBR). (Distanța Hilbert a unui punct este egală cu lungimea curbei Hilbert de la începutul curbei până la punct.). În schimb, alte variante de arbori R nu au mecanisme de control al manipulării spațiului.

Ideea principală

Deși următorul exemplu se referă la un mediu static, explică principiile intuitive din spatele construirii arborilor R buni. Aceste principii sunt valabile atât pentru datele statice, cât și pentru cele dinamice. Roussopoulos și Leifker au propus o metodă pentru construirea unui arbore R împachetat care realizează o prelucrare de aproape 100%. Ideea este să sortați datele după coordonatele x sau y dintr-un colț al dreptunghiului. Sortarea după oricare dintre cele patru colțuri produce rezultate similare. În acest articol, punctele și dreptunghiurile sunt sortate în raport cu coordonatele x a colțului din stânga jos al dreptunghiului, iar metoda lui Roussopoulos și Leifker va fi numită „arborele R împachetat în x”. Metoda parcurge o listă sortată de dreptunghiuri. Dreptunghiuri succesive sunt atribuite aceleiași frunze a arborelui R până când nodul este plin. Apoi o nouă foaie este creată și parcurgerea listei sortate continuă. Astfel, nodurile arborelui R rezultat vor fi complet împachetate, cu posibila excepție a ultimului nod de la fiecare nivel. Astfel, procesarea spațiului este aproape de 100%. Nivelurile superioare ale arborelui sunt create în mod similar.

Figura 1 prezintă problemele arborilor R împachetate în x. Figura (dreapta) prezintă nodurile R-tree obținute prin această metodă pentru punctele din stânga. Faptul că nodurile părinte rezultate acoperă o zonă mică explică degradarea rapidă a cererilor de puncte. Perimetrul mare al dreptunghiurilor explică însă de ce interogările pentru zone se degradează rapid. Acest lucru este în concordanță cu formulele analitice pentru performanța arborilor R [1] . Este intuitiv clar că algoritmul de împachetare ar trebui să atribuie puncte apropiate aceluiași nod. Ignorarea coordonatei y de către un „arbore R plin de x” încalcă această regulă generală.

Figura 1: [Stânga] 200 de puncte uniform distanțate. [Dreapta] MBR de noduri generate de algoritmul „ R-tree x-packing ”.

curba Hilbert

Curba Hilbert inițială pe o rețea 2x2, notată H 1 , este prezentată în Figura 2. Pentru a obține o curbă de ordinul i, fiecare vârf al curbei principale este înlocuit cu o curbă de ordinul i - 1, rotită și/sau reflectată ca necesar. Figura 2 prezintă, de asemenea, curbele Hilbert de ordinul doi și trei. Deoarece ordinea curbei tinde spre infinit, ca și alte curbe de umplere a spațiului, curba se transformă într-un fractal cu o dimensiune fractală de două [1] [2] . Curba Hilbert poate fi generalizată la dimensiuni mai mari. Un algoritm pentru desenarea unei curbe bidimensionale de un ordin dat poate fi găsit în Griffiths [3] și Jagadish [2] . Un algoritm pentru dimensiuni mai mari a fost dat de Bialli [4] .

Curba de umplere a spațiului creează o ordonare liniară a punctelor rețelei. Această cale poate fi construită pornind de la un capăt la celălalt al curbei, trecând toate punctele până la capătul curbei. Figura 2 prezintă o astfel de ordonare pentru o rețea 4x4 (vezi curba H2 ) . De exemplu, punctul (0,0) de pe curba H 2 are distanța 0, iar punctul (1,1) are distanța 2. Distanța Hilbert a unui dreptunghi este, prin definiție, distanța Hilbert a centrului său.

Figura 2: curbele Hilbert de ordinul 1, 2 și 3

Arborii Hilbert R-ambalați

Curba Hilbert definește o ordonare liniară pe dreptunghiurile de date. Parcurgând lista ordonată, atribuim fiecărui set de dreptunghiuri unui nod din arborele R. Ca rezultat, multe dreptunghiuri de date de pe același nod vor fi aproape unul de celălalt în ordine liniară și, cel mai probabil, se vor apropia în spațiul natural. Astfel, nodurile rezultate ale arborelui R vor avea o zonă mică. Figura 2 prezintă motivele pentru care metodele bazate pe curbele Hilbert conduc la o performanță bună. Datele constau din puncte (la fel ca în Figura 1). Prin gruparea punctelor în funcție de distanța lor Hilbert, MBR-urile nodurilor R-tree rezultate sunt de obicei dreptunghiuri mici, aproape pătrate. Aceasta înseamnă că nodurile pot avea zone și perimetre mici. Valorile de suprafață mici au ca rezultat o performanță bună de interogare pentru puncte. Zonele mici și perimetrele mici au ca rezultat o performanță bună pentru interogări mari.

Algoritmul de ambalare Hilbert-Pack

(Algoritmul de împachetare dreptunghi R-tree)
Pasul 1. Calculați distanța Hilbert pentru fiecare dreptunghi de date
Pasul 2. Sortați dreptunghiurile crescând distanța Hilbert
Pasul 3. /* Creați frunze (nivel l = 0) */

Pasul 4. /* Creați noduri la nivel ( l + 1) */

Aceasta presupune că datele sunt statice sau se modifică rar. Algoritmul este un algoritm euristic simplu pentru construirea unui arbore R cu manipulare 100% spațiu și are, de asemenea, un timp de răspuns bun.

Arborii R dinamici Hilbert

Performanța arborilor R depinde de calitatea algoritmului de grupare a datelor în dreptunghiuri la un nod. Arborii Hilbert R folosesc curbe de umplere a spațiului cu ordonarea liniară a dreptunghiurilor. Distanța Hilbert a unui dreptunghi este prin definiție egală cu distanța centrului său.

Structura arborelui

Arborele R Hilbert are următoarea structură. Frunza conține maximum C l elemente, fiecare de forma (R, obj _id), unde C l este capacitatea frunzei, R este MBR-ul obiectului real (x low , x high , y low , y high ), iar obj-id este indicatorul către intrarea de descriere a obiectului. Principala diferență dintre un arbore R Hilbert și un arbore R* [5] este că nodurile care nu sunt frunze conțin informații LHV (cea mai mare valoare Hilbert). Astfel, nodurile non-frunze din arborele R conțin cel mult C n elemente de formă (R, ptr, LHV), unde C n este capacitatea nodului non-frunză, R este MBR-ul care include toți descendenții lui acest nod, ptr este indicatorul pentru fiecare copil, iar LHV este cea mai mare distanță Hilbert a datelor din caseta de delimitare R. Rețineți că, deoarece un nod fără frunză are ca LHV distanța Hilbert a unuia dintre copiii săi, nu există un plus. cost pentru calcularea distanțelor Hilbert MBR ale nodurilor fără frunze. Figura 3 ilustrează câteva casete organizate într-un arbore R Hilbert. Distanțele Hilbert ale centrelor sunt numerele din jurul simbolurilor „x” (afișate numai pentru nodul părinte „II”). Valorile LHV sunt date între [paranteze]. Figura 4 arată cum arborele din Figura 3 este stocat pe disc. Conținutul nodului părinte „II” este afișat mai detaliat. Orice dreptunghi de date al nodului „I” are o valoare v ≤33. La fel, orice dreptunghi de nod „II” are o distanță Hilbert mai mare de 33 și mai mică de 107 și așa mai departe.

Figura 3: Casete de date organizate într-un arbore Hilbert R (distanțele Hilbert și valorile LHV sunt între paranteze)

Un simplu R-tree sparge un nod la depășire, creând două noduri. Această politică se numește politică de împărțire 1 la 2. Puteți amâna împărțirea și puteți converti două noduri în trei. Rețineți că această politică este similară cu politica de partiționare a arborelui B*. Această metodă se numește politica de împărțire 2-la-3. În cazul general, putem vorbi despre politica de divizare s-in-(s+1), unde s este ordinea politicii de divizare. Pentru a implementa politica de împărțire a ordinelor s, un nod aglomerat încearcă să pună unele noduri într-una dintre rudele sale s - 1 (noduri la același nivel). Dacă toate sunt umplute, atunci trebuie să împărțiți s-în-(s+1). Aceste rude s -1 sunt numite noduri cooperante. Algoritmii de căutare, inserare și depășire sunt descriși în detaliu mai jos.

Caută

Algoritmul de căutare este similar cu algoritmii din alte variante de arbori R. Pornind de la rădăcină, algoritmul coboară arborele și verifică toate arcele care intersectează dreptunghiul de căutare. Pe foaie, algoritmul include toate elementele din fereastra de interogare așa cum a fost găsită.

Procedura Găsiți (nodul Root, dreptunghi w):
S1. Căutând noduri care nu sunt frunze:

Începem căutarea fiecărui element al cărui MBR se încadrează în fereastra de interogare w.

S2. Căutare frunze:

Listăm toate elementele care intră în fereastra de interogare ca candidați.

Figura 4: Structura fișierului Hilbert R-tree

Inserați

Pentru a introduce un nou dreptunghi r în arborele R Hilbert, distanța Hilbert h a centrului noului dreptunghi este folosită ca cheie. La fiecare nivel, dintre toate elementele nivelului, este selectat un nod cu o valoare LHV minimă mai mare decât h. Dacă se ajunge la frunză, în ea se introduce dreptunghiul r în ordinea corectă în funcție de valoarea lui h. După ce noul dreptunghi este inserat în frunza N, se rulează procedura de reconciliere a arborelui pentru a modifica valorile MBR și LHV la nodurile de nivel superior.

Procedura Insert(Root node, dreptunghi r) : /* Inserează un nou dreptunghi r în arborele R Hilbert.
h este distanța Hilbert a dreptunghiului*/
I1. Găsirea foii potrivite:

CallSearchList (r, h) pentru a selecta foaia L în care să includeți r.

I2. Introdu r în foaia L:

Dacă L are un slot gol, introduceți r în L la un loc potrivit în ordinea distanțelor Hilbert și întoarcere. Dacă L este plin, apelați procedura Handle Overflow (L,r), care returnează o nouă frunză dacă este nevoie de despicare,

I3. Propagarea modificărilor:

Formăm o mulțime S care conține L, noduri cooperative și o foaie nouă (dacă există) Începem procedura Potrivirea arborelui (S).

I4. Creșterea înălțimii copacului:

Dacă propagarea modificărilor cauzează divizarea rădăcinilor, creați o nouă rădăcină ai cărei copii sunt cele două noduri rezultate din scindarea rădăcinii.

Procedură FindSheet(dreptunghi r, întreg h) :
/* Returnează foaia în care se plasează noul dreptunghi r. */
C1. Inițializare:

Setați N ca rădăcină.

C2. Verificarea foii:

Dacă N este o frunză, returnează N.

C3. Selectarea unui subarboresc:

Dacă N nu este o frunză, selectați elementul (R, ptr, LHV) cu un LHV minim mai mare de h.

C4. Coborâm până ajungem la frunză:

Setați N la nodul indicat de ptr și repetați procesul din punctul C2.

Reconcilierea arborelui de procedură (setul S) :
/* S este setul de noduri care conțin nodurile care urmează să fie modificate,
nodurile lor cooperante (dacă a avut loc o depășire)
și nodul NN creat (dacă a fost efectuată o divizare a nodurilor).
Procedura urcă de la frunză la rădăcină, schimbând MBR și LHV ale nodurilor care acoperă nodurile din S.
Procedura se ocupă de divizarea nodurilor (dacă există) */
A1. Dacă ajungem la rădăcină, ne oprim.
A2. Separări nod de procesare:

Fie Np părintele nodului N. Dacă nodul N a fost divizat, să fie NN noul nod. Introduceți NN în Np în ordinea corectă în funcție de distanța lui Hilbert, dacă este loc. În caz contrar, numim procedura Overflow Handling (Np , NN ). Dacă nodul Np a fost divizat, să fie PP noul nod.

A3. Modificați valorile MBR și LHV la nivel de părinte:

Fie P mulțimea nodurilor părinte pentru nodurile din S. Schimbăm valorile MBR și LHV corespunzătoare în nodurile P.

A4. Trecerea la nivelul următor:

S devine mulțimea nodurilor părinte P, NN = PP dacă Np a fost împărțit. mergi la A1.

Eliminare

Într-un arbore Hilbert R, nu este nevoie să reinserați nodurile suspendate până când nodul părinte dispare. În schimb, cheile care pot fi preluate din nodurile subiacente sunt îmbinate cu elemente de același nivel. Acest lucru este posibil deoarece nodurile au o ordonare clară (conform LHV). În schimb, nu există un astfel de concept pentru arbori R. Rețineți că operația de ștergere necesită s noduri cooperante, în timp ce operația de inserare necesită s - 1 elemente.

Procedura Delete(r) :
D1. Găsirea unei foi:

Căutăm apariția exactă a foii L, care contine r.

D2. Eliminați r:

Eliminați r din nodul L.

D3. Dacă L este gol

luăm câteva elemente din nodurile cooperante. dacă nu există astfel de elemente, aduce s + 1 noduri la s noduri, recalculați nodurile primite.

D4. Schimbăm valorile MBR și LHV la nivelurile părinte.

formați o mulțime S care conține L și cooperativa ei noduri (dacă are loc un debordare). apelați MatchTree(S).

Gestionarea depășirii

Procedura de gestionare a depășirii într-un arbore R Hilbert gestionează nodurile de depășire fie prin mutarea unor elemente la unul dintre cele s - 1 noduri cooperative, fie prin împărțirea nodurilor în s + 1 noduri.

Procedura Overflow Handling (nodul N, dreptunghi r) :
/* returnează un nou nod dacă a avut loc o scindare. */
H1. Fie ε o mulțime care conține toate elementele din N

și s - 1 nodurile sale cooperante.

H2. Adăugăm r la ε.
H3. Dacă cel puțin unul dintre nodurile cooperante s - 1 nu este umplut,

distribuiți ε uniform pe s conform distanțelor Hilbert.

H4. Dacă toate nodurile cooperante sunt umplute,

creați nodul NN și distribuiți ε uniform peste s + 1 noduri conform distantelor Hilbert întoarcere N.N.

Note

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

Literatură