Hilbert R-puu

Hilbertin R-puu , R -puun muunnos , on indeksointi moniulotteisista objekteista, kuten viivoista, kaksiulotteisista alueista, kolmiulotteisista objekteista tai parametrisoiduista objekteista, joiden mitat ovat korkeammat. Ne voidaan ymmärtää B+-puiden laajentamisena moniulotteisiin objekteihin.

R-puiden suorituskyky riippuu sen algoritmin laadusta, joka ryhmittelee tiedot suorakulmioihin. R-puut käyttävät tilan täyttäviä käyriä , tarkemmin sanottuna Hilbertin käyriä , järjestääkseen objektit lineaarisesti suorakulmioiksi.

Hilbert R-Trees -puita on kahta tyyppiä, yksi staattisille tiedoille ja toinen dynaamisille tiedoille. Molemmissa tapauksissa käytetään tilaa täyttäviä Hilbert-käyriä moniulotteisten kohteiden paremman järjestyksen saamiseksi. Tämä järjestys on "hyvä" siinä mielessä, että sen pitäisi ryhmitellä "samankaltaiset" tiedot suorakulmioiksi, minimoiden näiden Minimum Bounding Rectangles (MBR) -alueen ja -kehän Pakatut Hilbert R-puut sopivat staattiseen dataan, jota päivitetään hyvin harvoin tai ei ollenkaan.

Dynaamiset Hilbert R-Trees soveltuvat muuttuviin tietoihin, joissa lisäykset, poistot tai päivitykset tapahtuvat reaaliajassa. Lisäksi dynaamiset Hilbert R-puut käyttävät joustavaa viivästettyä halkaisumekanismia, mikä parantaa tilan käsittelyä. Jokaisella solmulla on hyvin määritelty joukko sisarussolmuja (yksi vanhempi). Säätämällä halkaisupolitiikkaa Hilbert R-puiden avulla saat tilankäsittelyasteen halutulle tasolle. Hilbertin R-puut lajittelevat suorakulmiot suorakulmioiden keskipisteiden Hilbert-etäisyyksien (MBR) mukaan. (Pisteen Hilbert-etäisyys on yhtä suuri kuin Hilbertin käyrän pituus käyrän alusta pisteeseen.). Sitä vastoin muissa R-puiden muunnelmissa ei ole mekanismeja tilankäsittelyn ohjaamiseksi.

Pääidea

Vaikka seuraava esimerkki viittaa staattiseen ympäristöön, se selittää intuitiiviset periaatteet hyvien R-puiden rakentamisen takana. Nämä periaatteet koskevat sekä staattista että dynaamista dataa. Roussopoulos ja Leifker ehdottivat menetelmää pakatun R-puun rakentamiseksi, jolla saavutetaan lähes 100 % prosessointi. Ajatuksena on lajitella tiedot x- tai y-koordinaatin mukaan suorakulmion yhdestä kulmasta. Lajittelu minkä tahansa neljän kulman mukaan tuottaa samanlaisia ​​tuloksia. Tässä artikkelissa pisteet ja suorakulmiot lajitellaan suhteessa suorakulmion vasemman alakulman x-koordinaattiin, ja Roussopoulosin ja Leifkerin menetelmää kutsutaan "x-pakatuksi R-puuksi". Menetelmä kiertää suorakulmioiden lajiteltua luetteloa. Peräkkäiset suorakulmiot osoitetaan samalle R-puun lehdelle, kunnes solmu on täynnä. Sitten luodaan uusi taulukko ja järjestetyn listan selaaminen jatkuu. Siten tuloksena olevan R-puun solmut pakataan kokonaan, lukuun ottamatta mahdollista kunkin tason viimeistä solmua. Tilankäsittely on siis lähes 100 %. Puun korkeammat tasot luodaan samalla tavalla.

Kuvassa 1 on esitetty x-pakattujen R-puiden ongelmat. Kuvassa (oikealla) näkyvät tällä menetelmällä saadut R-puun solmut vasemmalla näytetyille pisteille. Se tosiasia, että tuloksena olevat pääsolmut kattavat pienen alueen, selittää pistepyyntöjen nopean heikkenemisen. Suorakulmioiden suuri ympärysmitta selittää kuitenkin, miksi alueita koskevat kyselyt heikkenevät nopeasti. Tämä on yhdenmukainen R-puiden suorituskyvyn analyyttisten kaavojen kanssa [1] . On intuitiivisesti selvää, että pakkausalgoritmin tulee osoittaa lähipisteet samalle solmulle. Y-koordinaatin huomioimatta jättäminen "x-pakatun R-puun" avulla rikkoo tätä nyrkkisääntöä.

Kuva 1: [vasen] 200 tasaisin välein pistettä. [Oikea] R-tree x - packing -algoritmin luomien solmujen MBR

Hilbertin käyrä

Alkuperäinen Hilbertin käyrä 2x2 hilassa, jota merkitään H 1 :llä , on esitetty kuvassa 2. Jotta saadaan kertaluvun i käyrä, pääkäyrän kukin kärkipiste korvataan kertaluvun i - 1 käyrällä, jota kierretään ja/tai heijastetaan tarpeellista. Kuvassa 2 on myös toisen ja kolmannen kertaluvun Hilbertin käyrät. Kun käyrän järjestys pyrkii äärettömyyteen, kuten muutkin tilaa täyttävät käyrät, käyrä muuttuu fraktaaliksi, jonka fraktaalimitta on kaksi [1] [2] . Hilbertin käyrä voidaan yleistää korkeampiin ulottuvuuksiin. Algoritmi tietyn kertaluvun kaksiulotteisen käyrän piirtämiseksi löytyy Griffithsistä [3] ja Jagadishista [2] . Bialli [4] antoi algoritmin korkeammille ulottuvuuksille .

Tilan täyttökäyrä luo hilapisteiden lineaarisen järjestyksen. Tämä polku voidaan rakentaa aloittamalla käyrän päästä toiseen, ohittamalla kaikki pisteet käyrän loppuun. Kuvassa 2 on yksi tällainen järjestys 4x4 hilalle (katso käyrä H 2 ). Esimerkiksi käyrän H 2 pisteen (0,0) etäisyys on 0 ja pisteen (1,1) etäisyys 2. Suorakulmion Hilbert-etäisyys on määritelmän mukaan sen keskipisteen Hilbert-etäisyys.

Kuva 2: Hilbertin käyrät 1, 2 ja 3

Pakattu Hilbert R-puut

Hilbertin käyrä määrittää lineaarisen järjestyksen datasuorakulmioihin. Kävellessämme järjestetyn listan läpi, määritämme jokaisen suorakulmiojoukon solmulle R-puussa. Tämän seurauksena monet datasuorakulmiot samassa solmussa ovat lähellä toisiaan lineaarisessa järjestyksessä ja todennäköisimmin lähellä toisiaan luonnollisessa tilassa. Näin ollen tuloksena olevilla R-puun solmuilla on pieni pinta-ala. Kuvassa 2 on esitetty syyt, miksi Hilbertin käyriin perustuvat menetelmät johtavat hyvään suorituskykyyn. Tiedot koostuvat pisteistä (sama kuin kuvassa 1). Ryhmittelemällä pisteet niiden Hilbert-etäisyyksien mukaan tuloksena olevien R-puusolmujen MBR:t ovat yleensä pieniä, lähes neliön muotoisia suorakulmioita. Tämä tarkoittaa, että solmuilla on todennäköisesti pieniä alueita ja kehyksiä. Pienet aluearvot johtavat hyvään pisteiden kyselyn suorituskykyyn. Pienet alueet ja pienet ympärysmitat takaavat hyvän suorituskyvyn suurille kyselyille.

Hilbert-Pack Packing Algorithm

(R-puun suorakulmion pakkausalgoritmi)
Vaihe 1. Laske Hilbertin etäisyys kullekin datasuorakulmiolle
Vaihe 2. Lajittele suorakulmiot nousevan Hilbertin etäisyyden mukaan
Vaihe 3. /* Luo lehtiä (taso l = 0) */

Vaihe 4. /* Luo solmut tasolle ( l + 1) */

Tämä olettaa, että tiedot ovat staattisia tai muuttuvat harvoin. Algoritmi on yksinkertainen heuristinen algoritmi R-puun rakentamiseen 100 % tilankäsittelyllä ja sillä on myös hyvä vasteaika.

Hilbert dynaamiset R-puut

R-puiden suorituskyky riippuu algoritmin laadusta datan klusteroimiseksi suorakulmioiksi solmussa. Hilbert R-puut käyttävät tilan täyttäviä käyriä suorakulmioiden lineaarisella järjestyksellä. Suorakulmion Hilbert-etäisyys on määritelmän mukaan yhtä suuri kuin sen keskipisteen etäisyys.

Puurakenne

Hilbert R-puulla on seuraava rakenne. Lehti sisältää enintään C l -elementtejä, kukin muotoa (R, obj _id), jossa C l on lehden kapasiteetti, R on todellisen kohteen MBR (x matala , x korkea , y pieni , y high ), ja obj-id on osoitin objektin kuvausmerkintään. Suurin ero Hilbertin R-puun ja R*-puun [5] välillä on, että ei-lehtisolmut sisältävät LHV-informaatiota (Largest Hilbert Value). Siten R-puun ei-lehtiset solmut sisältävät korkeintaan C n -muotoista elementtiä (R, ptr, LHV), jossa C n on ei-lehtisolmun kapasiteetti, R on MBR, joka sisältää kaikki puun jälkeläiset. tämä solmu, ptr on osoitin lapsia kohti, ja LHV on rajalaatikon R datan suurin Hilbert-etäisyys. Huomaa, että koska ei-lehtisolmun LHV-arvo on yhden lapsensa Hilbert-etäisyys, ylimääräistä ei ole. ei-lehtisolmujen Hilbert-etäisyyksien MBR:n laskeminen. Kuva 3 esittää joitakin laatikoita järjestettynä Hilbert R-puuksi. Keskipisteiden Hilbert-etäisyydet ovat numeroita "x"-symbolien ympärillä (näkyy vain "II"-emosolmulle). LHV-arvot on annettu [suluissa]. Kuva 4 näyttää kuinka kuvan 3 puu tallennetaan levylle. Pääsolmun "II" sisältö esitetään yksityiskohtaisemmin. Minkä tahansa "I"-solmun datasuorakulmion arvo on v ≤33. Samoin minkä tahansa solmun suorakulmion "II" Hilbertin etäisyys on suurempi kuin 33 ja pienempi kuin 107 ja niin edelleen.

Kuva 3: Tietolaatikot on järjestetty Hilbertin R-puuhun (Hilbertin etäisyydet ja LHV-arvot ovat suluissa)

Yksinkertainen R-puu katkaisee solmun ylivuodon yhteydessä ja luo kaksi solmua. Tätä käytäntöä kutsutaan 1-2-jakokäytännöksi. Voit lykätä jakamista ja muuntaa kaksi solmua kolmeksi. Huomaa, että tämä käytäntö on samanlainen kuin B*-puun osiointikäytäntö. Tätä menetelmää kutsutaan 2-3-jakokäytännöksi. Yleisessä tapauksessa voidaan puhua jakokäytännöstä s-in-(s+1), jossa s on jakopolitiikan järjestys. Toteuttaakseen järjestyksen s jakopolitiikan, tungosta oleva solmu yrittää sijoittaa joitain solmuja yhteen s - 1 -sukulaisistaan ​​(solmut samalla tasolla). Jos ne ovat kaikki täytetty, sinun on jaettava s-osa (s+1). Näitä s -1-sukulaisia ​​kutsutaan yhteistyössä toimiviksi solmuiksi. Haku-, lisäys- ja ylivuodonkäsittelyalgoritmit kuvataan yksityiskohtaisesti alla.

Hae

Hakualgoritmi on samanlainen kuin muiden R-puiden muunnelmien algoritmit. Alkaen juuresta, algoritmi laskeutuu puuhun ja tarkistaa kaikki kaaret, jotka leikkaavat hakusuorakulmion. Arkilla algoritmi sisältää kaikki kyselyikkunan w elementit löytyneenä.

Toimenpide Etsi (solmujuuri, suorakulmio w):
S1. Etsitkö solmuja, jotka eivät ole lehtiä:

Aloitamme etsinnän jokaisesta elementistä, jonka MBR osuu kyselyikkunaan w.

S2. Lehtihaku:

Listaamme kaikki kyselyikkunaan w ehdokkaat elementit.

Kuva 4: Hilbert R-tree -tiedoston rakenne

Lisää

Uuden suorakulmion r lisäämiseksi Hilbertin R-puuhun käytetään avaimena uuden suorakulmion keskipisteen Hilbertin etäisyyttä h. Jokaisella tasolla, kaikkien tason elementtien joukosta, valitaan solmu, jonka LHV-minimiarvo on suurempi kuin h. Jos lehti saavutetaan, siihen lisätään suorakulmio r oikeassa järjestyksessä h:n arvon mukaan. Kun uusi suorakulmio on lisätty lehtiin N, Tree Reconciliation -menettely suoritetaan MBR- ja LHV-arvojen muuttamiseksi korkeamman tason solmuissa.

Toimenpide Insert(Juurisolmu, suorakulmio r) : /* Lisää uuden suorakulmion r Hilbertin R-puuhun.
h on suorakulmion Hilbertin etäisyys*/
I1. Oikean arkin löytäminen:

CallSearchList (r, h) valitaksesi arkin L, johon r sisällytetään.

I2. Lisää r arkkiin L:

Jos L:ssä on tyhjä paikka, lisää r L:hen sopivaan paikkaan Hilbertin etäisyyksien järjestyksen mukaisesti ja paluu. Jos L on täynnä, kutsu toimenpide Käsitteen ylivuoto (L,r), joka palauttaa uuden lehden, jos halkaisua tarvitaan,

I3. Muutosten levittäminen:

Muodostamme joukon S, joka sisältää L yhteistoiminnallisia solmuja ja uusi arkki (jos sellainen on) Aloitamme toimenpiteen Matching the Tree (S).

I4. Puun korkeuden lisääminen:

Jos muutosten eteneminen aiheuttaa juurihajoja, luo uusi juuri, jonka lapset ovat juuren jakamisesta johtuvat kaksi solmua.

Toimenpide EtsiSheet(suorakulmio r, kokonaisluku h) :
/* Palauttaa arkin, johon uusi suorakulmio r sijoitetaan. */
C1. Alustus:

Aseta juureksi N.

C2. Arkin tarkistus:

Jos N on lehti, palauta N.

C3. Alipuun valitseminen:

Jos N ei ole lehti, valitse elementti (R, ptr, LHV) joiden minimi LHV on suurempi kuin h.

C4. Menemme alas, kunnes saavutamme lehden:

Aseta N solmulle, johon ptr osoittaa, ja toista prosessi pisteestä C2.

Proceedure Tree Reconciliation (joukko S) :
/* S on joukko solmuja, jotka sisältävät muutettavat solmut,
niiden yhteistyössä toimivat solmut (jos ylivuoto tapahtui)
ja luodun NN-solmun (jos solmujako suoritettiin).
Proseduuri nousee lehdestä juureen muuttaen S:n solmut peittävien solmujen MBR- ja LHV-arvoja
. Proseduuri käsittelee solmujakaumia (jos sellaisia ​​on) */
A1. Jos saavutamme juuren, pysähdymme.
A2. Käsitellään solmujakoja:

Olkoon Np solmun N vanhempi. Jos solmu N on jaettu, olkoon NN uusi solmu. Lisää NN kohtaan Np oikeassa järjestyksessä sen Hilbert-etäisyyden mukaan, jos on tilaa. Muuten kutsumme menettelyä Overflow Handling (Np , NN ). Jos solmu Np on jaettu, olkoon PP uusi solmu.

A3. Muuta MBR- ja LHV-arvoja ylätason tasolla:

Olkoon P pääsolmujen joukko S:n solmuille. Muutamme vastaavat MBR- ja LHV-arvot P-solmuissa.

A4. Siirtyminen seuraavalle tasolle:

S:stä tulee pääsolmujen P joukko, NN = PP, jos Np jaettiin. mene kohtaan A1.

Poisto

Hilbert R-puussa roikkuvia solmuja ei tarvitse lisätä uudelleen, ennen kuin pääsolmu katoaa. Sen sijaan avaimet, jotka voidaan ottaa alla olevista solmuista, yhdistetään saman tason elementteihin. Tämä on mahdollista, koska solmuilla on selkeä järjestys (LHV:n mukaan). Sitä vastoin R-puille ei ole tällaista käsitettä. Huomaa, että poistotoiminto vaatii s yhteistyössä toimivia solmuja, kun taas lisäystoiminto vaatii s - 1 elementtejä.

Menettely Poista(r) :
D1. Arkin etsiminen:

Etsimme arkin L tarkan esiintymisen, joka sisältää r.

D2. Poista r:

Poista r solmusta L.

D3. Jos L on tyhjä

otamme joitain elementtejä yhteistyössä toimivista solmuista. jos sellaisia ​​elementtejä ei ole, tuo s + 1 solmua s solmuihin, laskea vastaanotetut solmut uudelleen.

D4. Muutamme MBR:n ja LHV:n arvoja ylätason tasoilla.

muodostavat joukon S, joka sisältää L:n ja sen osuuskunnan solmut (jos ylivuoto tapahtuu). soita MatchTree(S).

Ylivuodon käsittely

Hilbert R-puun ylivuodonkäsittelyproseduuri käsittelee ylivuotosolmuja joko siirtämällä joitain elementtejä johonkin s - 1 co-op -solmuista tai jakamalla s solmut s + 1 -solmuihin.

Proseduurin ylivuodon käsittely (solmu N, suorakulmio r) :
/* palauttaa uuden solmun, jos jako on tapahtunut. */
H1. Olkoon ε joukko, joka sisältää kaikki alkiot N:stä

ja sen s-1 yhteistyössä toimivat solmut.

H2. Lisäämme r:ään ε.
H3. Jos vähintään yksi s-1 yhteistyössä toimivista solmuista ei ole täytetty,

jakaa ε tasaisesti s:lle Hilbertin etäisyyksien mukaan.

H4. Jos kaikki yhteistyösolmut ovat täytetty,

luoda solmu NN ja jakaa ε tasaisesti s + 1 solmujen yli Hilbertin etäisyyksien mukaan palauttaa N.N.

Muistiinpanot

  1. ↑ 1 2 Kamel, Faloutsos, 1993 , s. 490-499.
  2. ↑ 1 2 Jagadish, 1990 , s. 332-342.
  3. ↑ Griffiths, 1986 , s. 403-411.
  4. ↑ Bially, 1969 , s. 658-664.
  5. ↑ Beckmann, Kriegel, Schneider, Seeger 1990 , s. 322.

Kirjallisuus