R-puu (tietorakenne)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 29. syyskuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 23 muokkausta .
R-puu
Tyyppi Moniulotteinen puu Binäärihakupuu
Keksintövuosi 1984
Tekijä Antonin Guttman
Monimutkaisuus O - symboleissa
Keskiverto Pahimmillaan
Hae O( log M n ) O( n )
 Mediatiedostot Wikimedia Commonsissa

R-tree ( eng.  R-trees ) on puumainen tietorakenne ( puu ), jonka Antonin Guttman ehdotti vuonna 1984 . Se on samanlainen kuin B-puu , mutta sitä käytetään spatiaalisen tiedon saamiseksi eli moniulotteisten tietojen , kuten maantieteellisten tietojen indeksointiin , joissa on kaksiulotteiset koordinaatit ( leveysaste ja pituusaste ). Tyypillinen R-puita käyttävä kysely voisi olla: "Etsi kaikki museot 2 kilometrin säteellä nykyisestä sijainnistani."

Tämä tietorakenne jakaa moniulotteisen avaruuden joukoksi hierarkkisesti sisäkkäisiä ja mahdollisesti leikkaavia suorakulmioita (kaksiulotteista tilaa varten). Kolmiulotteisen tai moniulotteisen avaruuden tapauksessa ne ovat suorakaiteen muotoisia suuntaissärmiöitä ( cuboids ) tai rinnakkaisia .

Lisäys- ja poistoalgoritmit käyttävät näitä rajoitusruutuja varmistaakseen, että "suljetut" objektit sijoitetaan samaan lehtien kärkeen. Erityisesti uusi objekti osuu lehtipisteeseen, joka tarvitsee rajauslaatikonsa pienimmän laajennuksen. Jokainen lehtisolmuelementti tallentaa kaksi tietokenttää: tavan tunnistaa objektia kuvaavat tiedot (tai itse dataa) ja tämän objektin rajoituslaatikon.

Vastaavasti hakualgoritmit (esim. risteys, sisällyttäminen, naapuruus) käyttävät rajausruutuja päättääkseen, etsitäänkö lapsisolmussa. Näin ollen useimpia pisteitä ei koskaan kosketeta haun aikana. Kuten B-puiden kohdalla, tämä R-puiden ominaisuus tekee niistä sopivia tietokantoihin , joissa kärjet voidaan vaihtaa levylle tarpeen mukaan.

Ylivuoteltujen pisteiden jakamiseen voidaan käyttää erilaisia ​​algoritmeja, mikä johtaa R-puiden jakamiseen alatyyppeihin: neliö ja lineaarinen.

Aluksi R-puut eivät takaaneet hyvää huonoimman tapauksen suorituskykyä , vaikka ne toimivat hyvin todellisilla tiedoilla. Vuonna 2004 kuitenkin julkaistiin uusi algoritmi , joka määrittää prioriteettipuut . Väitetään, että tämä algoritmi on yhtä tehokas kuin tehokkaimmat nykyaikaiset menetelmät ja samalla optimaalinen pahimpaan tapaukseen [1] .

R-puurakenne

Jokaisessa R-puun kärjessä on vaihteleva määrä elementtejä (ei enempää kuin jokin ennalta määrätty maksimi). Kukin ei-lehtipisteen elementti tallentaa kaksi tietokenttää: tavan tunnistaa lapsipiste ja rajauslaatikon (kuutiomuoto), joka sulkee sisäänsä kyseisen lapsipisteen kaikki elementit. Kaikki tallennetut tuplet säilytetään samalla syvyystasolla, joten puu on täydellisesti tasapainossa. Kun suunnittelet R-puuta, sinun on asetettava joitain vakioita:

Jotta algoritmit toimisivat oikein, ehdon MinEntries <= MaxEntries / 2 on täytyttävä. Juurisolmulla voi olla 2 - MaxEntries jälkeläisiä. Usein valitaan MinEntries = 2, jolloin juurelle täyttyvät samat ehdot kuin muille vertekseille. Joskus on myös viisasta varata erilliset vakiot lehtipisteiden pisteiden lukumäärälle, koska niitä voi usein tehdä enemmän.

Algoritmit

Lisää

R-puun rakentaminen tapahtuu pääsääntöisesti kutsumalla toistuvasti elementin puuhun lisäämistä. Lisäämisen idea on samanlainen kuin B-puuhun lisääminen: jos elementin lisääminen seuraavaan kärkeen johtaa ylivuotoon, kärki jaetaan. Alla on Antonin Guttmanin kuvaama klassinen lisäysalgoritmi .

Lisää funktio
  • Kutsuu ChooseLeafiä ja valitsee lehden, johon elementti lisätään. Jos lisäys on tehty, niin puu voidaan halkaista ja halkaisu voi mennä aina latvaan asti. Tässä tapauksessa ChooseLeaf palauttaa kaksi SplitNodea, jotka lisätään juureen
  • Kutsuu AdjustBounds-funktion, joka laajentaa juuren rajauslaatikon lisättävään pisteeseen
  • Tarkistaa, palauttiko ChooseLeaf nollasta poikkeavia SplitNodeja, jolloin puu kasvaa yhden tason ylöspäin: tästä hetkestä lähtien juuri on kärkipiste, jonka lapset ovat samat SplitNode-solmut
ChooseLeaf-funktio
  • jos syöte on lehti (rekursiokanta), niin:
    • kutsuu DoInsert-funktiota, joka lisää elementin suoraan puuhun ja palauttaa kaksi lehteä, jos jakaminen tapahtuu
    • muuttaa kärjen rajaavan suorakulmion vastaamaan lisättyä elementtiä
    • palauttaa DoInsertin palauttamat SplitNodesit
  • jos syöte on ei-lehtipiste:
    • kaikista lapsista valitaan se, jonka reunat vaativat vähimmäislisäyksen tietyn elementin lisäämiseksi
    • kutsuu rekursiivisesti ChooseLeafiä valitulle lapselle
    • korjaa rajaavat suorakulmiot
    • jos rekursiivisen kutsun jaetut solmut ovat nollia, jätämme funktion, muuten:
      • jos NumEntries < MaxEntries, lisää sitten uusi kärkipiste lapsiin, puhdista SplitNodes
      • muussa tapauksessa (kun ei ole paikkaa lisätä), ketjutamme lapsijoukon uuteen kärkeen ja välitämme tuloksena olevan funktion LinearSplitNodes-funktiolle tai muulle kärjenjakofunktiolle ja palautamme ChooseLeafista ne SplitNodes-solmut, jotka käytetty jakofunktio palautti meille. .
LinearSplit-funktio

Erilaisia ​​​​algoritmeja voidaan käyttää kärkien erottamiseen, tämä on yksi niistä. Sillä on vain lineaarinen monimutkaisuus ja se on helppo toteuttaa, vaikka se ei tuotakaan optimaalisin erottelua. Käytäntö kuitenkin osoittaa, että tällainen monimutkaisuus yleensä riittää.

  • kullekin koordinaatille koko jaetun kärkijoukon osalta lasketaan tämän koordinaatin suorakulmion suurimman alareunan ja ylärajan vähimmäismäärän välinen ero, sitten tämä arvo normalisoidaan pisteiden maksimi- ja vähimmäiskoordinaattien erolla. alkuperäinen sarja koko puun rakentamiseen
  • etsi tämän normalisoidun hajautuksen maksimi kaikkien koordinaattien yli
  • aseta ensimmäisiksi lapsiksi palautetuille pisteille solmu1 ja solmu2 ne syöttöluettelon kärjet, joissa maksimi saavutettiin, poista ne syöttöluettelosta, säädä solmu1 ja solmu2 rajoja
  • sitten lisäys suoritetaan jäljellä oleville kärkipisteille:
    • jos listassa on niin vähän pisteitä jäljellä, että jos ne kaikki lisätään johonkin tulostepisteistä, niin se sisältää MinEntries-pisteitä, siihen lisätään loput, palaa funktiosta
    • jos jollakin kärjestä on jo lapsia maksimi, loppuosa lisätään vastakkaiseen, return
    • listan seuraavalle kärkipisteelle sitä verrataan kuinka paljon rajoitusruutua tulee suurentaa, kun se lisätään kuhunkin kahdesta tulevasta kärjestä, missä se on pienempi, se lisätään sinne
Fyysinen lisäystoiminto DoInsert
  • jos kärjessä on vapaita paikkoja, piste lisätään sinne
  • jos paikkoja ei ole, niin kärjen lapset ketjutetaan lisätyn pisteen kanssa ja kutsutaan LinearSplit-funktiota tai muuta jakofunktiota, joka palauttaa kaksi jaettua kärkeä, jotka palautetaan doInsertistä
Osiointi klusterointialgoritmeilla

Joskus R-puun sijasta käytetään ns. cR-puuta (c tarkoittaa klusteroitua ). Perusajatuksena on, että klusterointialgoritmeja , kuten k-means , käytetään erottamaan pisteitä tai pisteitä . K-keskiarvojen monimutkaisuus on myös lineaarinen, mutta useimmissa tapauksissa se antaa paremman tuloksen kuin lineaarinen Guttman-erottelualgoritmi, toisin kuin se ei vain minimoi laatikoiden verhojen kokonaispinta-alaa, vaan myös etäisyyttä. niiden ja päällekkäisalueen välillä. Pisteklusteroinnissa käytetään alkuperäisen avaruuden valittua metriikkaa, kärkiklusteroinnissa voidaan käyttää niiden suuntaissärmiöiden verhojen keskipisteiden välistä etäisyyttä tai niiden välistä maksimietäisyyttä.

Klusterointialgoritmit eivät ota huomioon sitä, että algoritmin vakiot rajoittavat kärjen jälkeläisten määrää ylhäältä ja alhaalta. Jos klusterin jakaminen tuottaa kelpaamattoman tuloksen, voit käyttää klassista algoritmia tälle joukolle, koska näin ei tapahdu usein käytännössä.

Mielenkiintoinen idea on käyttää klusterointia useisiin klustereihin, joissa useita voi olla enemmän kuin kaksi. On kuitenkin otettava huomioon, että tämä asettaa tiettyjä rajoituksia p-puurakenteen parametreille.

Huomaa, että cR-puun lisäksi on sen klusterointimenetelmään perustuva muunnelma clR-puu, jossa keskipisteenä käytetään iteratiivista algoritmia "sijoitteluongelman" ratkaisemiseksi. Algoritmilla on neliöllinen laskennallinen monimutkaisuus, mutta se tarjoaa kompaktimpien suuntaissärmiöiden verhokäyrien rakentamisen rakenteen kärkipisteiden tietueissa.

Hae

Puussa etsiminen on melko triviaalia, sinun on vain otettava huomioon se tosiasia, että jokainen avaruuden piste voidaan peittää useilla pisteillä.

Poisto

Tämä algoritmi [2] poistaa jonkin merkinnän E R-puusta. Algoritmi koostuu seuraavista vaiheista:

  • Etsi merkinnän sisältävä solmu. Soita FindLeaf -hakutoimintoon löytääksesi merkinnän E sisältävä lehti L. Pysäytä algoritmi, jos merkintää ei löydy.
  • merkinnän poistaminen. Poista tietue E arkilta L.
  • Päivitä muutokset. Kutsu L-merkinnän CondenseTree -funktio.
  • Puun juuren tarkastus. Jos puun juuri ei ole lehtisolmu, jossa on vain yksi merkintä jäljellä, tee siitä puun juuri.

FindLeaf-toiminto

Olkoon T puun juuri ja olkoon E haluttu merkintä.

  • Alipuuhaku. Jos T ei ole lehtisolmu, tarkista jokainen E-merkinnän esiintyminen jokaisessa T:n merkinnässä seuraavan ehdon mukaisesti: jos merkintä E sisältyy T:n merkinnän suorakulmioon, kutsu FindLeaf- funktio .
  • Hae merkintää lehtisolmusta. Jos T on lehti, etsi tietue E tästä lehdestä ja jos se löytyy, palauta se.

CondenseTree-toiminto

Poistetaan tietue E taulukosta L. Sitten on tarpeen poistaa solmu, jolla on vähän tietueita jäljellä (vähemmän kuin MinEntries) ja siirtää sen tietueet. Kun siirryt ylös puussa, poista merkinnät tarvittaessa (samoilla kriteereillä). Matkalla juureen laske suorakulmiot uudelleen tekemällä niistä mahdollisimman pieniä. Algoritmi on kuvattu alla. Tämä toiminto voidaan toteuttaa myös rekursiolla.

  • Alustus. Olkoon N = L ja Q etäsolmujen joukko, aluksi tyhjä.
  • Etsi ylävirran solmu. Jos N on juuri, siirry algoritmin viimeiseen vaiheeseen (tietueiden lisääminen uudelleen). Muussa tapauksessa olkoon P solmun N vanhempi.
  • Pienten solmujen poissulkeminen. Jos solmussa N on vähemmän MinEntries-merkintöjä, poista N P:stä ja lisää se Q:hen.
  • Suorakulmioiden uudelleenlaskenta. Jos N:ää ei ole poistettu, laske sen suorakulmio uudelleen siten, että se sisältää kaikki N:n merkinnät.
  • Liikkuu ylös puuhun. Olkoon N = P. Toista pääsolmun etsimisen toinen vaihe.
  • "orpojen" tietueiden lisääminen. Sinun on lisättävä tietueet uudelleen joukosta Q. Jos Q:n tietue on lehtisolmu, lisää kaikki sen tietueet käyttämällä Insert -algoritmia . Jos Q ei ole lehtisolmu, niin se on lisättävä niin, että kaikki sen lehtisolmut ovat samalla puutasolla kuin itse puun lehtisolmut (R-puun ominaisuuden mukaan, jonka mukaan kaikki lehtisolmut tallennetaan samalle puun syvyystasolle).

Keskustelu R-puista

Edut

  • tallentaa tehokkaasti spatiaalisesti lokalisoituja objektiryhmiä
  • tasapainoinen tarkoittaa pahimmillaan nopeaa hakua
  • yhden pisteen lisääminen/poistaminen ei vaadi puun merkittävää uudelleenrakentamista (dynaaminen indeksi)

Haitat

  • herkkä lisättyjen tietojen järjestykselle
  • kärkipisteiden rajaavat laatikot voivat mennä päällekkäin

Katso myös

  • Luettelo tietorakenteista (puista)

Muistiinpanot

  1. ↑ Priority R-Tree: Käytännössä tehokas ja pahimman mahdollisen optimaalinen R-puu , SIGMOD. Arkistoitu alkuperäisestä 6. maaliskuuta 2021. Haettu 12. lokakuuta 2011.
  2. ↑ Antonin Guttman. [ https://klevas.mif.vu.lt/~algis/DSA/guttman.pdf R-TREES. DYNAAMINEN INDEKSIRAKENNE TILAHAKUA VARTEN]  //  ACM. - 1984. Arkistoitu 24. maaliskuuta 2018.

Linkit