R*-copac

Arborii R* sunt o variantă a arborilor R utilizate pentru indexarea informațiilor spațiale. Arborii R* au un cost puțin mai mare de a crea decât arborii R standard, deoarece poate fi necesar ca datele să fie rearanjate (șterge + inserare), dar arborele rezultat are, de obicei, performanțe de interogare mai bune. Ca un arbore R standard, poate stoca atât puncte, cât și date spațiale. Arborele a fost propus de Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider și Bernhard Seeger în 1990 [1] .

Diferența dintre arbori R* și arbori R

Minimizarea atât a acoperirii, cât și a suprapunerii este importantă pentru performanța arborilor R. Suprapunerea înseamnă că atunci când se interogează sau se inserează date, mai mult de o ramură a arborelui trebuie extinsă (din cauza metodei de împărțire a datelor în zone care se pot suprapune). Acoperirea minimă îmbunătățește ștergerea, permițând excluderea mai frecventă a paginilor întregi din căutări, în special pentru interogările cu intervale negative. Arborele R* încearcă să reducă ambele valori utilizând o combinație a algoritmului de împărțire a nodurilor scanate și a conceptului de reinstalare forțată la depășirea nodului. Abordarea se bazează pe observația că structurile R-tree sunt foarte sensibile la ordinea în care au fost inserate elementele arborelui, astfel încât structurile bazate pe inserție (mai degrabă decât încărcarea în vrac) sunt mai probabil să fie suboptime. Ștergerea și reinserarea elementelor arborelui le permite să „găsească” un loc în arbore care este mai potrivit decât locația lor inițială.

Când un nod depășește, unele dintre elementele sale sunt îndepărtate din nod și reinstalate în arbore. (Pentru a evita o resetare în cascadă nesfârșită cauzată de un alt nod care se depășește la această operație, procedura de resetare poate fi apelată o singură dată la fiecare nivel al arborelui atunci când este inserat orice element nou.) Acest lucru are ca rezultat grupuri mai bine grupate de elemente la nivelul noduri, reducând acoperirea nodurilor. Mai mult decât atât, adesea divizarea nodului este adesea întârziată, ceea ce duce la o creștere a umplerii medii a nodului. Reinserția poate fi considerată ca o tehnică de optimizare a unui arbore în creștere atunci când un nod se debordează.

Performanță

• Euristica de partiționare îmbunătățită generează pagini care sunt mai dreptunghiulare și, prin urmare, mai potrivite pentru mulți algoritmi.
• Metoda de reinserție optimizează arborele existent, dar crește complexitatea.
• Menține eficient punctele și datele spațiale.

• Rezultatele diferitelor abordări de împărțire pe o bază de date a oficiilor poștale germane

• R-arbore cu partiție pătrată Gutman [2] .
  Există multe pagini care se răspândesc de la stânga la dreapta în Germania și paginile se suprapun foarte mult. Aceasta nu este o proprietate foarte favorabilă pentru majoritatea aplicațiilor, care adesea au nevoie doar de zone dreptunghiulare mici care se intersectează cu multe dungi.

• R-arbore cu partiție liniară Anga-Tan [3] .
  Deși dreptunghiurile nu sunt la fel de lungi ca în tiling-ul lui Gutmann, problema bandării afectează aproape fiecare foaie de pe pagină. Paginile de foaie se suprapun puțin, dar paginile de manual se suprapun foarte mult.

• Partiția topologică R* a unui arbore [1] .
  Paginile se suprapun foarte puțin, deoarece arborele R* încearcă să minimizeze paginile suprapuse, iar reinserarea optimizează și mai mult arborele. Nici strategia de partiționare nu favorizează benzile, așa că paginile rezultate sunt mai potrivite pentru aplicațiile de cartografiere.

Algoritm și complexitate

• Arborele R* folosește același algoritm pentru interogări și ștergeri ca și arborele R obișnuit .
• Pentru inserare, arborele R* folosește o strategie combinată. Pentru nodurile frunze, suprapunerea este minimizată, în timp ce pentru nodurile interne, dimensiunile liniare și aria sunt minimizate.
• Pentru partiţionare, arborele R* utilizează o partiţionare topologică, care selectează o partiţionare a axelor de-a lungul perimetrului, apoi suprapunerea este minimizată.
• Pe lângă o strategie de împărțire îmbunătățită, arborele R* încearcă să evite scindarea atunci când obiectele și subarborele sunt reintroduse în arbore, în spiritul conceptului de arbore B echilibrat .

Interogările în cel mai rău caz și complexitatea eliminării sunt identice cu cele dintr-un arbore R. Strategia de inserare a arborelui R* are complexitate și este mai complexă decât strategia de împărțire liniară ( ) a arborelui R, dar este mai puțin complexă decât strategia de împărțire în pătrat ( ) pentru dimensiunea paginii obiectelor și are o contribuție mică la complexitatea generală. Complexitatea generală a inserției rămâne comparabilă cu cea a unui arbore R: o reinserție afectează cel mult o ramură a arborelui și, prin urmare, oferă inserții repetate, care sunt comparabile ca performanță cu un arbore R obișnuit. Deci complexitatea generală a unui arbore R* este aceeași cu cea a unui arbore R normal.

Implementarea algoritmului complet trebuie să gestioneze multe cazuri de colț și situații dependente, care nu sunt discutate aici.

Note

1. ↑ 1 2 Beckmann, Kriegel, Schneider, Seeger, 1990 , p. 322.
2. ↑ Guttman, 1984 , p. 47.
3. ↑ Ang, Tan, 1997 , p. 337–349.

Literatură

• Beckmann N., Kriegel HP, Schneider R., Seeger B. The R*-tree: an efficient and robust access method for points and rectangles // Proceedings of the 1990 ACM SIGMOD international Conference on Management of data - SIGMOD '90 . - 1990. - ISBN 0897913655 . doi : 10.1145 / 93597.98741 .
• Guttman A. R-Trees: A Dynamic Index Structure for Spatial Searching // Proceedings of the 1984 ACM SIGMOD international Conference on Management of data - SIGMOD '84 . - 1984. - ISBN 0897911288 . - doi : 10.1145/602259.602266 .
• Ang CH, Tan TC New linear node splitting algorithm for R-trees // Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997 / Michel Scholl, Agnès Voisard. - Springer, 1997. - T. 1262. - (Lecture Notes in Computer Science). - doi : 10.1007/3-540-63238-7_38 .