R-tree (structură de date)

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 29 septembrie 2015; verificările necesită 23 de modificări .
R-arborele
Tip de Arborele multidimensional Arborele de căutare binar
Anul inventiei 1984
Autor Antonin Guttman
Complexitatea în simbolurile O
In medie În cel mai rău caz
Căutare O( log M n ) O( n )
 Fișiere media la Wikimedia Commons

R-tree ( Eng.  R-trees ) este o structură de date asemănătoare arborelui ( arbore ), propusă în 1984 de Antonin Guttman . Este similar cu un arbore B , dar este folosit pentru a accesa date spațiale, adică pentru a indexa informații multidimensionale , cum ar fi datele geografice cu coordonate bidimensionale ( latitudine și longitudine ). O interogare tipică care utilizează arbori R ar putea fi: „Găsiți toate muzeele pe o rază de 2 kilometri de locația mea actuală”.

Această structură de date descompune un spațiu multidimensional într-un set de dreptunghiuri imbricate ierarhic și, eventual, care se intersectează (pentru un spațiu bidimensional). În cazul spațiului tridimensional sau multidimensional, acestea vor fi paralelipipede dreptunghiulare ( cuboide ) sau paralelotopi .

Algoritmii de inserare și eliminare folosesc aceste casete de delimitare pentru a se asigura că obiectele „închise” sunt plasate pe același vârf de frunză. În special, noul obiect va lovi vârful frunzei care are nevoie de cea mai mică expansiune a casetei sale de delimitare. Fiecare element nod frunză stochează două câmpuri de date: o modalitate de a identifica datele care descriu obiectul (sau datele în sine) și căsuța de delimitare a acestui obiect.

În mod similar, algoritmii de căutare (de exemplu, intersecție, incluziune, vecinătate) folosesc casete de delimitare pentru a decide dacă să caute la un nod copil. Astfel, majoritatea nodurilor nu sunt niciodată atinse în timpul căutării. Ca și în cazul arborilor B, această proprietate a arborilor R îi face potriviti pentru baze de date , unde vârfurile pot fi schimbate pe disc după cum este necesar.

Pentru a împărți vârfurile debordate, pot fi utilizați diverși algoritmi, ceea ce duce la împărțirea arborilor R în subtipuri: pătratice și liniare.

Inițial, arborii R nu garantau performanțe bune în cazul cel mai rău , deși funcționau bine pe date reale. Cu toate acestea, în 2004, a fost publicat un nou algoritm care determină arbori R prioritari . Se susține că acest algoritm este la fel de eficient ca și cele mai eficiente metode moderne și, în același timp, este optim pentru cel mai rău caz [1] .

Structura R-tree

Fiecare vârf al arborelui R are un număr variabil de elemente (nu mai mult de un maxim predeterminat). Fiecare element al unui vârf care nu este frunză stochează două câmpuri de date: o modalitate de a identifica vârful copil și o casetă de delimitare (cuboid) care cuprinde toate elementele acelui vârf copil. Toate tuplurile stocate sunt stocate la același nivel de adâncime, astfel încât arborele este perfect echilibrat. Când proiectați un arbore R, trebuie să setați câteva constante:

Pentru ca algoritmii să funcționeze corect, trebuie îndeplinită condiția MinEntries <= MaxEntries / 2. Nodul rădăcină poate avea descendenți de la 2 la MaxEntries. Adesea se alege MinEntries = 2, atunci sunt îndeplinite aceleași condiții pentru rădăcină ca și pentru restul vârfurilor. De asemenea, uneori este înțelept să puneți deoparte constante separate pentru numărul de puncte din vârfurile frunzelor, deoarece adesea puteți face mai multe din ele.

Algoritmi

Inserați

Construcția unui arbore R are loc, de regulă, prin apelarea în mod repetat a operației de inserare a unui element în arbore. Ideea de inserare este similară cu inserarea într -un arbore B : dacă adăugarea unui element la următorul vârf duce la un debordare, atunci vârful este împărțit. Mai jos este algoritmul clasic de inserare descris de Antonin Guttman .

Funcția de inserare
  • Apelează ChooseLeaf pentru a selecta frunza în care urmează să fie adăugat elementul. Dacă inserarea se face, atunci arborele ar putea fi împărțit, iar despărțirea ar putea merge până la vârf. În acest caz, ChooseLeaf returnează două SplitNodes pentru a le insera în rădăcină
  • Apelează funcția AdjustBounds, care extinde căsuța de delimitare a rădăcinii până la punctul care este inserat
  • Verifică dacă ChooseLeaf a returnat SplitNodes non-zero, apoi arborele crește cu un nivel în sus: din acest moment, rădăcina este vârful ai cărui copii sunt aceiași SplitNodes
Funcția ChooseLeaf
  • dacă intrarea este o frunză (bază de recursivitate), atunci:
    • apelează funcția DoInsert, care inserează direct elementul în arbore și returnează două frunze dacă are loc o scindare
    • modifică dreptunghiul de delimitare al vârfului pentru a se potrivi cu elementul inserat
    • returnează SplitNodes returnate de DoInsert
  • dacă intrarea este un vârf non-frunză:
    • dintre toți copiii, este selectat cel ale cărui margini necesită creșterea minimă pentru a insera elementul dat
    • apelează recursiv ChooseLeaf pe copilul selectat
    • fixează dreptunghiuri de delimitare
    • dacă splittedNodes din apelul recursiv sunt zero, atunci părăsim funcția, în caz contrar:
      • dacă NumEntries < MaxEntries, apoi adăugați un nou vârf la copii, curățați SplitNodes
      • în caz contrar (când nu există loc de inserat), concatenăm matricea de copii cu noul vârf și trecem funcția rezultată funcției LinearSplitNodes sau unei alte funcții de împărțire a nodurilor și returnăm de la ChooseLeaf acele SplitNodes pe care ni le-a returnat funcția de împărțire folosită. .
Funcția LinearSplit

Se pot folosi diferiți algoritmi pentru a separa vârfurile, acesta este unul dintre ei. Are doar complexitate liniară și este ușor de implementat, deși nu produce cea mai optimă separare. Cu toate acestea, practica arată că o astfel de complexitate este de obicei suficientă.

  • pentru fiecare coordonată pentru întregul set de vârfuri partajate, se calculează diferența dintre marginea maximă inferioară a dreptunghiului la această coordonată și limita superioară minimă, apoi această valoare este normalizată prin diferența dintre coordonatele maxime și minime ale punctelor de setul original pentru a construi întregul copac
  • găsiți maximul acestei răspândiri normalizate pe toate coordonatele
  • setați ca primii copii pentru nodurile returnate nod1 și node2 acele vârfuri din lista de intrare pe care a fost atins maximul, eliminați-le din lista de intrare, ajustați limitele pentru nodul1 și nodul2
  • apoi, se efectuează inserarea pentru vârfurile rămase:
    • dacă au rămas atât de puține vârfuri în listă încât dacă toate sunt adăugate la unul dintre nodurile de ieșire, atunci acesta va conține nodurile MinEntries, atunci restul este adăugat la acesta, reveniți din funcție
    • dacă unul dintre vârfuri are deja un maxim de copii, atunci restul se adaugă la opus, returnează
    • pentru următorul vârf din listă, se compară cu cât de mult ar trebui mărită căsuța de delimitare atunci când este introdusă în fiecare dintre cele două vârfuri viitoare, unde este mai mică, este inserată acolo
Funcția de inserare fizică DoInsert
  • dacă există locuri libere la vârf, atunci punctul este introdus acolo
  • dacă nu există locuri, atunci copiii vârfului sunt concatenați cu punctul inserat și se apelează la funcția LinearSplit sau o altă funcție de divizare, returnând două vârfuri împărțite, pe care le întoarcem din doInsert
Partiționare cu algoritmi de clusterizare

Uneori, în loc de un arbore R, se folosește așa-numitul arbore cR (c înseamnă clustered ). Ideea de bază este că algoritmii de grupare , cum ar fi k-means, sunt utilizați pentru a separa vârfuri sau puncte . Complexitatea k-means este, de asemenea, liniară, dar în cele mai multe cazuri oferă un rezultat mai bun decât algoritmul liniar de separare Guttman, în contrast cu care minimizează nu numai suprafața totală a plicurilor cutiilor, ci și distanța. dintre ele și zona de suprapunere. Pentru gruparea punctelor, este utilizată metrica selectată a spațiului original; pentru gruparea vârfurilor, puteți utiliza distanța dintre centrele plicurilor lor de paralelipipedi sau distanța maximă dintre ele.

Algoritmii de grupare nu țin cont de faptul că numărul de descendenți ai unui vârf este limitat de sus și de jos de constantele algoritmului. Dacă împărțirea clusterului produce un rezultat inacceptabil, puteți utiliza algoritmul clasic pentru acest set, deoarece acest lucru nu se întâmplă des în practică.

O idee interesantă este utilizarea grupării în mai multe clustere, unde mai multe pot fi mai mult de două. Cu toate acestea, trebuie luat în considerare faptul că acest lucru impune anumite restricții asupra parametrilor structurii p-tree.

Rețineți că, în plus față de arborele cR, există și arborele clR de variație bazat pe metoda de grupare, în care un algoritm iterativ pentru rezolvarea „problema de plasare” este folosit ca centru. Algoritmul are o complexitate de calcul pătratică, dar oferă construcția unor plicuri mai compacte de paralelipipedi în înregistrările de vârf ale structurii.

Caută

Căutarea într-un copac este destul de banală, trebuie doar să ții cont de faptul că fiecare punct din spațiu poate fi acoperit de mai multe vârfuri.

Eliminare

Acest algoritm [2] elimină o anumită intrare E din arborele R. Algoritmul constă din următorii pași:

  • Căutați nodul care conține intrarea. Apelați funcția de căutare FindLeaf pentru a găsi frunza L care conține intrarea E. Opriți algoritmul dacă intrarea nu este găsită.
  • Ștergerea unei intrări. Ștergeți intrarea E din foaia L.
  • Actualizați modificările. Apelați funcția CondenseTree pentru intrarea L.
  • Verificarea rădăcinii copacului. Dacă rădăcina arborelui nu este un nod frunză cu o singură intrare rămasă, atunci faceți acea intrare rădăcina arborelui.

Funcția FindLeaf

Fie T rădăcina arborelui și E intrarea dorită.

  • Căutare subarbore. Dacă T nu este un nod frunză, atunci verificați fiecare apariție a unei intrări E în fiecare intrare a lui T conform următoarei condiții: dacă intrarea E este inclusă în dreptunghiul unei intrări în T, atunci apelați funcția FindLeaf .
  • Căutați o intrare într-un nod frunză. Dacă T este o frunză, atunci găsiți înregistrarea E în această frunză și, dacă este găsită, returnați-o.

Funcția CondenseTree

Să fie ștearsă înregistrarea E din foaia L. Apoi, este necesar să se elimine nodul care mai are puține înregistrări (mai puțin decât MinEntries) și să-și mute înregistrările. Când vă deplasați în sus în arbore, dacă este necesar, ștergeți intrările (după aceleași criterii). În drum spre rădăcină, recalculați dreptunghiurile, făcându-le cât mai mici. Algoritmul este descris mai jos. Această funcție poate fi implementată și folosind recursiunea.

  • Inițializare. Fie N = L și Q mulțimea de noduri la distanță, inițial goale.
  • Găsiți nodul din amonte. Dacă N este o rădăcină, atunci treceți la ultimul pas al algoritmului (inserând din nou înregistrările). În caz contrar, fie P părintele nodului N.
  • Excluderea nodurilor mici. Dacă nodul N are mai puține intrări MinEntries, atunci eliminați N din P și adăugați-l la Q.
  • Recalcularea dreptunghiurilor. Dacă N nu a fost eliminat, recalculați-i dreptunghiul astfel încât să conțină toate intrările din N.
  • Mișcare în sus în copac. Fie N = P. Repetați al doilea pas de găsire a nodului părinte.
  • Inserarea înregistrărilor „orfane”. Trebuie să reinserați înregistrările din setul Q. Dacă înregistrarea din Q este un nod frunză, atunci introduceți toate înregistrările sale folosind algoritmul Insert . Dacă Q nu este un nod frunză, atunci trebuie inserat astfel încât toate nodurile sale frunze să fie la același nivel de arbore cu nodurile frunzelor arborelui însuși (prin proprietatea arborelui R, conform căreia toate nodurile frunzei sunt stocate la același nivel de adâncime a arborelui) .

Discuție despre R-trees

Avantaje

  • stocarea eficientă a grupurilor de obiecte localizate spațial
  • echilibrat înseamnă căutare rapidă în cel mai rău caz
  • inserarea/ștergerea unui singur punct nu necesită o reconstrucție semnificativă a arborelui (index dinamic)

Dezavantaje

  • sensibil la ordinea datelor adăugate
  • casetele de delimitare a vârfurilor se pot suprapune

Vezi și

  • Lista structurilor de date (arbori)

Note

  1. ↑ Arborele R prioritar: un arbore R optim practic eficient și cel mai rău caz , SIGMOD. Arhivat din original pe 6 martie 2021. Preluat la 12 octombrie 2011.
  2. ↑ Antonin Guttman. [ https://klevas.mif.vu.lt/~algis/DSA/guttman.pdf R-TREES. O STRUCTURĂ INDEXICĂ DINAMICĂ PENTRU CĂUTAREA SPAȚIALĂ]  //  ACM. - 1984. Arhivat la 24 martie 2018.

Link -uri