R*-træ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. december 2019; verifikation kræver 1 redigering .

R* træ

Type

datastruktur

Opfindelsens år

1990

Forfatter

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider og Bernhard Seeger

Kompleksitet i O-symboler

	Gennemsnit	I værste fald
Hukommelsesforbrug	O( n )	O( n )
Søg	O( logn )
Indsæt	O( logn )

Mediefiler på Wikimedia Commons

R*-træer er en variant af R-træer, der bruges til at indeksere rumlig information. R*-træer har lidt højere omkostninger at oprette end standard R-træer, da dataene muligvis skal omarrangeres (slet + indsæt), men det resulterende træ har normalt bedre forespørgselsydeevne. Som et standard R-træ kan det lagre både punkter og rumlige data. Træet blev foreslået af Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider og Bernhard Seeger i 1990 [1] .

Forskellen mellem R*-træer og R-træer

Det er vigtigt at minimere både dækning og overlapning for R-træers ydeevne. Overlap betyder, at når du forespørger data eller indsætter, skal mere end én gren af træet udvides (på grund af metoden til at opdele data i områder, der kan overlappe). Minimeret dækning forbedrer sletning ved at tillade, at hele sider udelukkes fra søgninger oftere, især for forespørgsler med negative intervaller. R*-træet forsøger at reducere begge værdier ved at bruge en kombination af den scannede nodeopdelingsalgoritme og konceptet med tvungen geninstallation ved nodeoverløb. Fremgangsmåden er baseret på den observation, at R-træstrukturer er meget følsomme over for rækkefølgen, hvori træelementer blev indsat, så indsættelsesbaserede (i stedet for bulk-belastning) strukturer er mere tilbøjelige til at være suboptimale. Sletning og genindsættelse af træelementer giver dem mulighed for at "finde" et sted i træet, der er mere egnet end deres oprindelige placering.

Når en node løber over, fjernes nogle af dens elementer fra noden og geninstalleres i træet. (For at undgå en endeløs kaskade-nulstilling forårsaget af en anden knude, der flyder over på denne operation, kan nulstillingsproceduren kun kaldes én gang på hvert niveau i træet, når et nyt element indsættes). Dette resulterer i mere velklyngede grupper af elementer ved noder, hvilket reducerer nodedækningen. Desuden er opdelingen af noden ofte forsinket, hvilket fører til en stigning i den gennemsnitlige fyldning af noden. Genindsættelse kan opfattes som en teknik til at optimere et voksende træ, når en knude løber over.

Ydeevne

Den forbedrede partitioneringsheuristik giver sider, der er mere rektangulære og derfor bedre egnet til mange algoritmer.
Genindsættelsesmetoden optimerer det eksisterende træ, men øger kompleksiteten.
Vedligeholder punkter og rumlige data effektivt.

Resultater af forskellige opdelingsmetoder på en database over tyske postkontorer
R-træ med firkantet Gutman skillevæg [2] .
Der er mange sider, der spredes fra venstre mod højre over hele Tyskland, og siderne overlapper hinanden meget. Dette er ikke en særlig gunstig egenskab for de fleste applikationer, som ofte kun har brug for små rektangulære områder, der krydser mange striber.
R-træ med lineær Anga-Tan partition [3] .
Selvom rektanglerne ikke er så lange som i Gutmanns flisebelægning, påvirker båndproblemet næsten alle ark på siden. Arksider overlapper lidt, men man-sider overlapper meget.
Topologisk partition R* af et træ [1] .
Siderne overlapper meget lidt, fordi R*-træet forsøger at minimere overlappende sider, og genindsættelse optimerer træet yderligere. Partitioneringsstrategien favoriserer heller ikke bånd, så de resulterende sider er mere velegnede til kortlægningsapplikationer.

Algoritme og kompleksitet

R*-træet bruger den samme algoritme til forespørgsler og sletninger som det almindelige R-træ .
Til indsættelse bruger R*-træet en kombineret strategi. For bladknuder er overlapning minimeret, mens lineære dimensioner og areal for interne knudepunkter minimeres.
Til opdeling bruger R*-træet en topologisk opdeling, som vælger en opdeling af akserne langs omkredsen, hvorefter overlapningen minimeres.
Ud over en forbedret opdelingsstrategi forsøger R*-træet at undgå spaltning, når objekter og undertræer genindsættes i træet, i ånden bag konceptet med et balanceret B-træ .

Worst-case-forespørgsler og fjernelseskompleksitet er identiske med dem i et R-træ. R*-træindsættelsesstrategien har kompleksitet og er mere kompleks end R-træets lineære opdelingsstrategi ( ), men er mindre kompleks end kvadratisk opdelingsstrategien ( ) for objekters sidestørrelse og har et lille bidrag til den overordnede kompleksitet. Den overordnede indsættelseskompleksitet forbliver sammenlignelig med et R-træ: en genindsættelse påvirker højst én gren af træet og giver derfor gentagne indsættelser, som i ydeevne er sammenlignelig med et almindeligt R-træ. Så den samlede kompleksitet af et R*-træ er den samme som for et normalt R-træ. ${\mathcal {O}}(M\log M)$ ${\mathcal {O}}(M)$ ${\mathcal {O}}(M^{2})$ $M$ ${\mathcal {O}}(\log n)$

Implementeringen af den komplette algoritme skal håndtere mange hjørnesager og afhængige situationer, som ikke diskuteres her.

Noter

↑ 1 2 Beckmann, Kriegel, Schneider, Seeger, 1990 , s. 322.
↑ Guttman, 1984 , s. 47.
↑ Ang, Tan, 1997 , s. 337-349.

Litteratur

Beckmann N., Kriegel HP, Schneider R., Seeger B. R*-træet: en effektiv og robust adgangsmetode til punkter og rektangler // 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 Ny lineær nodeopdelingsalgoritme for R-træer // Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Tyskland, 15.–18. juli 1997 / Michel Scholl, Agnès Voisard. - Springer, 1997. - T. 1262. - (Lecture Notes in Computer Science). - doi : 10.1007/3-540-63238-7_38 .

Træ (datastruktur)
Binært søgetræ Træ (grafteori) træstruktur
Binære træer	binært træ T-træ
Selvbalancerende binære træer	AA træ AVL træ Rød-sort træ Splay træ træ med bøder kartesisk træ Fibonacci træ B-træ T-træ
B-træer	2-3-træ B⁺-træ B*-træ B x -træ UB træ 2-3-4 træ (a,b)-træ dansende træ
præfiks træer	suffiks træ Komprimeret præfikstræ Ternært søgetræ
Binær opdeling af rummet	k-dimensionelt træ VP træ
Ikke-binære træer	Quadtree oktre Sparsom Voxel Octree eksponentielt træ PQ træ
At bryde rummet op	R-træ Hilbert R-træ R+-træ R*-træ X-træ M-træ Fenwick træ Segmenttræ
Andre træer	dynge hash træ fingertræ metrisk træ Belægning træ BK-træ Dobbeltkædet træ iDistance Linkskåret træ LSM træ
Algoritmer	Bredde først søgning Dybde første søgning DSW algoritme spanning tree protokol

Datastrukturer
Lister	array enkelt linket liste dobbelt linket liste Beståelsesliste
Træer	B-træ Binært søgetræ AVL træ Rød-sort træ dynge
Tæller	Instrueret graf rettet acyklisk graf Binært beslutningsdiagram Hypergraf
Andet	Hash bord Stak