R*-träd

R*-träd är en variant av R-träd som används för att indexera rumslig information. R*-träd har en något högre kostnad att skapa än vanliga R-träd eftersom data kan behöva omarrangeras (radera + infoga), men det resulterande trädet har vanligtvis bättre frågeprestanda. Som ett vanligt R-träd kan det lagra både punkter och rumslig data. Trädet föreslogs av Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider och Bernhard Seeger 1990 [1] .

Skillnaden mellan R*-träd och R-träd

Att minimera både täckning och överlappning är viktigt för R-trädens prestanda. Överlappning innebär att när man frågar efter data eller infogar, behöver mer än en gren av trädet utökas (på grund av metoden att dela upp data i områden som kan överlappa varandra). Minimerad täckning förbättrar raderingen genom att tillåta att helsidor utesluts från sökningar oftare, särskilt för frågor med negativa intervall. R*-trädet försöker reducera båda värdena genom att använda en kombination av den skannade noddelningsalgoritmen och konceptet med tvingad ominstallation vid nodspill. Tillvägagångssättet är baserat på observationen att R-trädstrukturer är mycket känsliga för i vilken ordning trädelementen infogades, så insättningsbaserade (snarare än bulklastande) strukturer är mer benägna att vara suboptimala. Genom att ta bort och återinsätta trädelement kan de "hitta" en plats i trädet som är mer lämplig än deras ursprungliga plats.

När en nod svämmar över tas några av dess element bort från noden och återinstalleras i trädet. (För att undvika en oändlig kaskadåterställning orsakad av att en annan nod svämmar över på denna operation, kan återställningsproceduren endast anropas en gång på varje nivå i trädet när något nytt element infogas.) Detta resulterar i mer välklustrade grupper av element vid noder, vilket minskar nodtäckningen. Dessutom är ofta uppdelningen av noden ofta försenad, vilket leder till en ökning av den genomsnittliga fyllningen av noden. Återinsättning kan ses som en teknik för att optimera ett växande träd när en nod svämmar över.

Prestanda

• Den förbättrade partitioneringsheuristiken ger sidor som är mer rektangulära och därför bättre lämpade för många algoritmer.
• Återinsättningsmetoden optimerar det befintliga trädet, men ökar komplexiteten.
• Upprätthåller effektivt punkter och rumsliga data.

• Resultat av olika uppdelningsmetoder i en databas över tyska postkontor

• R-träd med fyrkantig Gutman-vägg [2] .
  Det finns många sidor som sprids från vänster till höger över Tyskland och sidorna överlappar varandra mycket. Detta är inte en särskilt fördelaktig egenskap för de flesta applikationer, som ofta bara behöver små rektangulära ytor som korsar sig med många ränder.

• R-träd med linjär Anga-Tan partition [3] .
  Även om rektanglarna inte är lika långa som i Gutmanns plattsättning, påverkar bandningsproblemet nästan varje ark på sidan. Bladsidor överlappar lite, men mansidor överlappar mycket.

• Topologisk partition R* av ett träd [1] .
  Sidorna överlappar väldigt lite eftersom R*-trädet försöker minimera överlappande sidor, och återinsättning optimerar trädet ytterligare. Partitioneringsstrategin gynnar inte heller band, så de resulterande sidorna är mer lämpade för kartläggningsapplikationer.

Algoritm och komplexitet

• R*-trädet använder samma algoritm för frågor och raderingar som det vanliga R-trädet .
• För insättning använder R*-trädet en kombinerad strategi. För lövnoder minimeras överlappningen, medan för interna noder minimeras linjära dimensioner och area.
• För partitionering använder R*-trädet en topologisk partitionering, som väljer en partitionering av axlarna längs omkretsen, varefter överlappningen minimeras.
• Förutom en förbättrad delningsstrategi försöker R*-trädet undvika delning när objekt och underträd återinförs i trädet, i andan av konceptet med ett balanserat B-träd .

Worst-case-frågor och borttagningskomplexitet är identiska med dem i ett R-träd. Strategin för insättning av R*-träd har komplexitet och är mer komplex än strategin för linjär delad ( ) för R-trädet, men är mindre komplex än strategin för kvadratdelning ( ) för sidstorleken på objekt, och har ett litet bidrag till den övergripande komplexiteten. Den övergripande insättningskomplexiteten förblir jämförbar med den för ett R-träd: en återinsättning påverkar högst en gren av trädet och ger därför upprepade infogningar, vilket är jämförbart i prestanda med ett vanligt R-träd. Så den totala komplexiteten för ett R*-träd är densamma som för ett normalt R-träd.

Implementeringen av den kompletta algoritmen måste hantera många hörnfall och beroende situationer, som inte diskuteras här.

Anteckningar

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

Litteratur

• Beckmann N., Kriegel HP, Schneider R., Seeger B. R*-trädet: en effektiv och robust åtkomstmetod för punkter och rektanglar // 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 linjär noddelningsalgoritm för R-träd // 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 .