R*-puu

R*-puut ovat muunnelmia R-puista, joita käytetään paikkatietojen indeksointiin. R*-puiden luominen on hieman kalliimpaa kuin tavallisten R-puiden, koska tiedot on ehkä järjestettävä uudelleen (poista + lisää), mutta tuloksena olevalla puulla on yleensä parempi kyselyn suorituskyky. Kuten tavallinen R-puu, se voi tallentaa sekä pisteitä että paikkatietoja. Puun ehdottivat Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider ja Bernhard Seeger vuonna 1990 [1] .

Ero R*-puiden ja R-puiden välillä

Sekä peiton että päällekkäisyyden minimoiminen on tärkeää R-puiden suorituskyvyn kannalta. Päällekkäisyys tarkoittaa, että tietoja haettaessa tai lisättäessä on laajennettava useampi kuin yksi puun haara (koska menetelmä jakaa tiedot alueille, jotka voivat olla päällekkäisiä). Minimaalinen kattavuus parantaa poistamista sallimalla kokonaisten sivujen sulkemisen pois hauista useammin, erityisesti negatiivisten vaihteluvälien kyselyissä. R*-puu yrittää pienentää molempia arvoja käyttämällä skannatun solmun jakamisalgoritmin ja pakotetun uudelleenasennuksen konseptia solmun ylivuodon yhteydessä. Lähestymistapa perustuu havaintoon, että R-puurakenteet ovat erittäin herkkiä puuelementtien lisäysjärjestykseen, joten lisäyspohjaiset (eikä bulkkilataus) rakenteet ovat todennäköisemmin alioptimaalisia. Puuelementtien poistaminen ja lisääminen uudelleen antaa heille mahdollisuuden "löytää" puusta paikan, joka on sopivampi kuin niiden alkuperäinen sijainti.

Kun solmu ylivuodon, jotkin sen elementit poistetaan solmusta ja asennetaan uudelleen puuhun. (Jotta vältetään loputon peräkkäinen nollaus, jonka aiheuttaa toinen solmu ylivuoto tässä toiminnossa, nollausmenettely voidaan kutsua vain kerran kullakin puun tasolla, kun uusi elementti lisätään.) Tämä johtaa paremmin klusteroituihin elementtiryhmiin solmuja, mikä vähentää solmun peittoa. Lisäksi usein solmun jakaminen viivästyy, mikä johtaa solmun keskimääräisen täyttömäärän kasvuun. Uudelleenasettamista voidaan pitää tekniikana kasvavan puun optimoimiseksi solmun ylivuodon yhteydessä.

Suorituskyky

• Parannettu osiointiheuristiikka tuottaa sivut, jotka ovat suorakaiteen muotoisempia ja sopivat siksi paremmin useisiin algoritmeihin.
• Uudelleenlisäysmenetelmä optimoi olemassa olevan puun, mutta lisää monimutkaisuutta.
• Ylläpitää tehokkaasti pisteitä ja paikkatietoja.

• Tuloksia erilaisista osiointimenetelmistä Saksan postitoimistojen tietokannassa

• R-puu neliömäisellä Gutman-osiolla [2] .
  Monet sivut leviävät vasemmalta oikealle ympäri Saksaa ja sivut menevät paljon päällekkäin. Tämä ei ole kovin edullinen ominaisuus useimmille sovelluksille, jotka usein tarvitsevat vain pieniä suorakaiteen muotoisia alueita, jotka leikkaavat monia raitoja.

• R-puu, jossa on lineaarinen Anga-Tan-osio [3] .
  Vaikka suorakulmiot eivät ole yhtä pitkiä kuin Gutmannin laatoituksessa, raitaongelma vaikuttaa lähes jokaiseen arkkiin sivulla. Taulukkosivut menevät vähän päällekkäin, mutta man-sivut ovat paljon päällekkäisiä.

• Puun topologinen osio R* [1] .
  Sivut menevät hyvin vähän päällekkäin, koska R*-puu yrittää minimoida päällekkäiset sivut, ja uudelleenlisäys optimoi puun entisestään. Osiointistrategia ei myöskään suosi kaistoja, joten tuloksena olevat sivut sopivat paremmin kartoitussovelluksiin.

Algoritmi ja monimutkaisuus

• R*-puu käyttää samaa algoritmia kyselyihin ja poistoihin kuin tavallinen R-puu .
• Lisäämiseen R*-puu käyttää yhdistettyä strategiaa. Lehtisolmujen kohdalla limitys on minimoitu, kun taas sisäisten solmujen lineaariset mitat ja pinta-ala on minimoitu.
• Osiointiin R*-puu käyttää topologista osiointia, joka valitsee akselien osioinnin kehää pitkin, jolloin limitys minimoidaan.
• Parannetun halkaisustrategian lisäksi R*-puu yrittää välttää halkeilua, kun esineitä ja alipuita lisätään uudelleen puuhun tasapainoisen B-puun konseptin hengessä .

Huonoin tapauksen kyselyt ja poiston monimutkaisuus ovat samat kuin R-puussa. R*-puun lisäysstrategia on monimutkainen ja monimutkaisempi kuin R-puun lineaarinen jakostrategia ( ), mutta se on vähemmän monimutkainen kuin objektien sivukoon neliöjakostrategia ( ) , ja sillä on pieni vaikutus yleistä monimutkaisuutta. Yleinen lisäyksen monimutkaisuus on verrattavissa R-puuhun: uudelleenlisäys vaikuttaa enintään yhteen puun haaraan ja antaa siksi toistuvia lisäyksiä, mikä on suorituskyvyltään verrattavissa tavalliseen R-puuhun. Joten R*-puun kokonaismonimutkaisuus on sama kuin normaalin R-puun.

Koko algoritmin toteutuksen tulee käsitellä monia kulmatapauksia ja riippuvaisia ​​tilanteita, joita ei käsitellä tässä.

Muistiinpanot

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

Kirjallisuus

• Beckmann N., Kriegel HP, Schneider R., Seeger B. R*-puu: tehokas ja vankka pääsymenetelmä pisteisiin ja suorakulmioihin // 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: Dynamic Index Structure for Spatial Search // Proceedings of 1984 ACM SIGMOD International Conference on Management of Data - SIGMOD '84 . - 1984. - ISBN 0897911288 . - doi : 10.1145/602259.602266 .
• Ang CH, Tan TC Uusi lineaarinen solmujakoalgoritmi R-puille // Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berliini, Saksa, 15.–18. heinäkuuta 1997 / Michel Scholl, Agnès Voisard. - Springer, 1997. - T. 1262. - (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/3-540-63238-7_38 .