Hilbert R-fa

A Hilbert R-fa , az R -fa egy változata , többdimenziós objektumok, például vonalak, kétdimenziós régiók, háromdimenziós objektumok vagy nagyobb méretű paraméterezett objektumok indexelése. Felfoghatók a B+-fák többdimenziós objektumokra való kiterjesztéseként .

Az R-fák teljesítménye az adatokat téglalapokba csoportosító algoritmus minőségétől függ. Az R-fák térkitöltő görbéket , pontosabban Hilbert-görbéket használnak, hogy az objektumokat lineárisan téglalapokba rendezzék.

Kétféle Hilbert R-Trees létezik, az egyik a statikus, a másik a dinamikus adatokhoz. Mindkét esetben térkitöltő Hilbert-görbéket használnak a többdimenziós objektumok jobb rendezettségének eléréséhez. Ez a rendezés "jó" abban az értelemben, hogy a "hasonló" adatokat téglalapokba kell csoportosítani, minimalizálva ezen Minimum Bounding Rectangles (MBR) területét és kerületét A csomagolt Hilbert R-fák olyan statikus adatok tárolására alkalmasak, amelyek nagyon ritkán vagy egyáltalán nem frissülnek.

A Dynamic Hilbert R-Trees olyan változó adatokhoz alkalmasak, ahol valós időben történnek beillesztések, törlések vagy frissítések. Ezenkívül a dinamikus Hilbert R-fák rugalmas késleltetett hasítómechanizmust alkalmaznak, ami javítja a helykezelést. Minden csomópont rendelkezik egy jól meghatározott testvér (egyszülős) csomópontkészlettel. A felosztási politika beállításával a Hilbert R-trees segítségével elérheti a kívánt szintű térfeldolgozási fokot. A Hilbert R-fák a téglalapokat a téglalapok középpontjainak Hilbert-távolságai (MBR) szerint rendezik. (Egy pont Hilbert-távolsága megegyezik a Hilbert-görbe hosszával a görbe elejétől a pontig.). Ezzel szemben az R-fák más változatai nem rendelkeznek a térkezelés szabályozására szolgáló mechanizmusokkal.

Fő ötlet

Bár a következő példa statikus környezetre vonatkozik, elmagyarázza a jó R-fák felépítésének intuitív alapelveit. Ezek az elvek statikus és dinamikus adatokra egyaránt érvényesek. Roussopoulos és Leifker egy olyan módszert javasoltak egy tömörített R-fa létrehozására, amely közel 100%-os feldolgozást tesz lehetővé. Az ötlet az, hogy az adatokat x vagy y koordináták szerint rendezzük a téglalap egyik sarkából. A négy sarok bármelyike ​​szerinti rendezés hasonló eredményeket ad. Ebben a cikkben a pontok és téglalapok a téglalap bal alsó sarkának x-koordinátájához viszonyítva vannak rendezve, és Roussopoulos és Leifker módszerét "x-csomagolt R-fának" nevezzük. A módszer a téglalapok rendezett listáján halad keresztül. Az egymást követő téglalapokat az R-fa ugyanahhoz a leveléhez rendeljük, amíg a csomópont meg nem telik. Ezután egy új lap jön létre, és a rendezett lista böngészése folytatódik. Így az eredményül kapott R-fa csomópontjai teljesen meg lesznek csomagolva, kivéve az egyes szintek utolsó csomópontját. Így a térfeldolgozás közel 100%. A fa magasabb szintjei hasonlóképpen jönnek létre.

Az 1. ábra az x-csomagolt R-fák problémáit mutatja be. A jobb oldali ábra az ezzel a módszerrel kapott R-fa csomópontokat mutatja a bal oldalon látható pontokhoz. Az a tény, hogy az eredményül kapott szülőcsomópontok kis területet fednek le, magyarázza a pontkérelmek gyors leromlását. A téglalapok nagy kerülete azonban megmagyarázza, miért romlanak gyorsan a területekre vonatkozó lekérdezések. Ez összhangban van az R-fák teljesítményére vonatkozó analitikai képletekkel [1] . Intuitív módon egyértelmű, hogy a csomagoló algoritmusnak közeli pontokat kell hozzárendelnie ugyanahhoz a csomóponthoz. Az y-koordináta figyelmen kívül hagyása egy "x-csomagolt R-fával" sérti ezt az ökölszabályt.

1. ábra: [Balra] 200 egyenletesen elosztott pont. [Jobbra] Az " R-tree x-packing " algoritmus által generált csomópontok MBR

Hilbert-görbe

A kezdeti Hilbert-görbe egy 2x2-es rácson, amelyet H 1 -el jelöltünk , a 2. ábra mutatja. Az i-es rendű görbe eléréséhez a főgörbe minden csúcsát lecseréljük egy i-1 rendű görbére, amelyet elforgatunk és/vagy tükrözünk szükséges. A 2. ábrán a második és harmadik rendű Hilbert-görbék is láthatók. Mivel a görbe sorrendje a végtelenbe hajlik, a többi térkitöltő görbéhez hasonlóan a görbe kettős fraktáldimenziójú fraktállá változik [1] [2] . A Hilbert-görbe általánosítható magasabb dimenziókra. Egy adott sorrendű kétdimenziós görbe megrajzolására szolgáló algoritmus megtalálható Griffiths [3] és Jagadish [2] könyvében . Bialli [4] adott egy algoritmust a magasabb dimenziókhoz .

A térkitöltő görbe a rácspontok lineáris sorrendjét hozza létre. Ezt az utat úgy lehet megépíteni, hogy a görbe egyik végétől a másikig indulunk, minden pontot áthaladva a görbe végéig. A 2. ábra egy ilyen sorrendet mutat be egy 4x4-es rácsra (lásd a H 2 görbét ). Például a H 2 görbe (0,0) pontja távolsága 0, az (1,1) pont távolsága pedig 2. Egy téglalap Hilbert-távolsága értelemszerűen a középpontjának Hilbert-távolsága.

2. ábra: 1., 2. és 3. rendű Hilbert-görbék

Csomagolt Hilbert R-fák

A Hilbert-görbe lineáris sorrendet határoz meg az adattéglalapokon. A rendezett listát végigjárva minden téglalapkészletet hozzárendelünk egy csomóponthoz az R-fában. Ennek eredményeként számos adattéglalap ugyanazon a csomóponton lineáris sorrendben közel lesz egymáshoz, és valószínűleg közel lesz a természetes térben. Így az R-fa eredményül kapott csomópontjai kis területűek lesznek. A 2. ábra bemutatja, hogy a Hilbert-görbéken alapuló módszerek miért vezetnek jó teljesítményhez. Az adatok pontokból állnak (ugyanaz, mint az 1. ábrán). A pontok Hilbert-távolságuk szerinti csoportosításával az eredményül kapott R-fa csomópontok MBR-ei általában kicsi, közel négyzet alakú téglalapok. Ez azt jelenti, hogy a csomópontok valószínűleg kis területtel és kerülettel rendelkeznek. A kis területértékek jó lekérdezési teljesítményt eredményeznek a pontokhoz. Kis területek és kis kerületek jó teljesítményt eredményeznek nagy lekérdezések esetén.

Hilbert-Pack Packing Algorithm

(R-fa téglalap-csomagoló algoritmus)
1. lépés. Számítsa ki a Hilbert-távolságot minden adattéglalaphoz
2. lépés. Rendezze a téglalapokat növekvő Hilbert-távolság szerint
3. lépés. /* Levelek létrehozása ( l szint = 0) */

4. lépés. /* Csomópontok létrehozása szinten ( l + 1) */

Ez azt feltételezi, hogy az adatok statikusak vagy ritkán változnak. Az algoritmus egy egyszerű heurisztikus algoritmus egy 100%-os térkezeléssel és jó válaszidővel rendelkező R-fa létrehozására.

Hilbert dinamikus R-fák

Az R-fák teljesítménye az adatok téglalapokba csoportosítására szolgáló algoritmus minőségétől függ egy csomóponton. A Hilbert R-fák térkitöltő görbéket használnak a téglalapok lineáris rendezésével. Egy téglalap Hilbert-távolsága értelemszerűen egyenlő a középpontja távolságával.

Fa szerkezete

A Hilbert R-fa szerkezete a következő. A levél maximum C l elemet tartalmaz, mindegyik alakja (R, obj _id), ahol C l a levél kapacitása, R a valós objektum MBR-je (x low , x high , y low , y high ), az obj-id pedig az objektumleírás bejegyzésére mutató mutató. A fő különbség a Hilbert R-fa és az R*-fa között [5] az, hogy a nem levél csomópontok LHV (legnagyobb Hilbert érték) információt tartalmaznak. Így a nem levél csomópontok az R-fában legfeljebb C n alakú elemet tartalmaznak (R, ptr, LHV), ahol C n a nem levél csomópont kapacitása, R az MBR, amely magában foglalja az összes leszármazottját. ez a csomópont, a ptr a mutató gyermekenként, az LHV pedig az R határolódobozban lévő adatok legnagyobb Hilbert-távolsága. Vegye figyelembe, hogy mivel egy nem leveles csomópont LHV-je az egyik gyermekének Hilbert-távolsága, nincs extra. a nem levél csomópontok Hilbert-távolságának MBR kiszámításának költsége. A 3. ábra néhány Hilbert R-fába rendezett dobozt mutat be. A középpontok Hilbert-távolságai az "x" szimbólumok körüli számok (csak a "II" szülőcsomópontnál látható). Az LHV értékek [zárójelben] vannak megadva. A 4. ábra azt mutatja, hogy a 3. ábrán látható fa hogyan kerül tárolásra a lemezen. A "II" szülőcsomópont tartalma részletesebben látható. Bármely "I" csomópont adattéglalap értéke v ≤33. Hasonlóképpen, bármely "II" csomóponti téglalap Hilbert-távolsága nagyobb, mint 33 és kisebb, mint 107, és így tovább.

3. ábra: Hilbert R-fában rendezett adatdobozok (zárójelben a Hilbert-távolságok és az LHV értékek)

Egy egyszerű R-fa túlcsorduláskor megtör egy csomópontot, és két csomópontot hoz létre. Ezt a házirendet 1-2-re osztott szabályzatnak nevezik. Elhalaszthatja a felosztást, és két csomópontot háromra konvertálhat. Vegye figyelembe, hogy ez a házirend hasonló a B*-fa particionálási szabályzathoz. Ezt a módszert 2-3-as felosztási irányelvnek nevezik. Általános esetben az s-in-(s+1) felosztási rendről beszélhetünk, ahol s a felosztási politika sorrendje. Az s sorrend felosztási politikájának megvalósítása érdekében egy zsúfolt csomópont megpróbál néhány csomópontot az s - 1 rokonai közé helyezni (azonos szintű csomópontok). Ha mind ki van töltve, akkor az s-t (s+1) kell felosztani. Ezeket az s -1 rokonokat együttműködő csomópontoknak nevezzük. A keresés, beillesztés és túlcsordulás kezelési algoritmusait az alábbiakban részletesen ismertetjük.

Keresés

A keresési algoritmus hasonló az R-fák más változataiban található algoritmusokhoz. A gyökértől kiindulva az algoritmus leereszkedik a fára, és ellenőrzi az összes ívet, amely metszi a keresési téglalapot. A lapon az algoritmus a w lekérdezési ablakban található összes elemet tartalmazza.

Eljárás keresése(csomópont'gyök, w téglalap):
S1. Olyan csomópontokat keres, amelyek nem levelek:

Elkezdjük a keresést minden olyan elemnél, amelynek MBR-je a w lekérdező ablakba esik.

S2. Levél keresés:

Felsoroljuk az összes elemet, amely a w lekérdezési ablakba esik, mint jelölt.

4. ábra: A Hilbert R-tree fájl szerkezete

Beszúrás

Új r téglalap beszúrásához a Hilbert R-fába, az új téglalap középpontjának h Hilbert-távolságát használjuk kulcsként. Minden szinten, a szint elemei közül egy h-nál nagyobb minimális LHV értékű csomópont kerül kiválasztásra. Ha elérjük a levelet, az r téglalapot a h értékének megfelelő sorrendben illesztjük be. Miután az új téglalapot beszúrtuk az N levélbe, a Tree Reconciliation eljárás lefut az MBR és LHV értékek megváltoztatásához a magasabb szintű csomópontokon.

Eljárás Insert(Gyökércsomópont, r téglalap) : /* Új r téglalapot szúr be a Hilbert R-fába.
h a téglalap Hilbert-távolsága*/
I1. A megfelelő lap megtalálása:

CallSearchList (r, h) annak az L lapnak a kiválasztásához, amelyen r szerepeljen.

I2. Szúrja be az r betűt az L lapba:

Ha L-nek van egy üres helye, szúrja be az r-t az L-be megfelelő helyre a Hilbert-távok és a visszaérkezés sorrendje szerint. Ha L tele van, hívja meg a Handle Overflow (L,r) eljárást, amely új levelet ad vissza, ha hasításra van szükség,

I3. A változások terjesztése:

L, kooperatív csomópontokat tartalmazó S halmazt alkotunk és egy új lap (ha van) Elkezdjük a Fa illesztése (S) eljárást.

I4. A fa magasságának növelése:

Ha a változások terjesztése gyökérhasadást okoz, hozzon létre egy új gyökér, amelynek gyermekei a gyökér felosztásából származó két csomópont.

Eljárás FindSheet(r téglalap, h egész) :
/* Visszaadja azt a lapot, amelybe az új r téglalapot el kell helyezni. */
C1. Inicializálás:

Állítsa be az N-t gyökérként.

C2. Lapellenőrzés:

Ha N egy levél, adja vissza N-t.

C3. Egy részfa kiválasztása:

Ha N nem levél, válassza ki az elemet (R, ptr, LHV) h-nál nagyobb minimális LHV-vel.

C4. Lefelé megyünk, amíg el nem érjük a levelet:

Állítsa be az N-t a ptr által mutatott csomópontra, és ismételje meg a folyamatot a C2 ponttól.

Procedure Tree Reconciliation (S halmaz) :
/* S a csomópontok halmaza, amely tartalmazza a módosítandó csomópontokat,
azok együttműködő csomópontjait (ha túlcsordulás történt)
és a létrehozott NN csomópontot (ha csomópontfelosztás történt).
Az eljárás a levéltől a gyökérig emelkedik, megváltoztatva az S-ben lévő csomópontokat lefedő csomópontok MBR-ét és LHV-jét.
Az eljárás kezeli a csomópont-felosztásokat (ha van ilyen) */
A1. Ha elérjük a gyökeret, megállunk.
A2. Csomópont felosztások feldolgozása:

Legyen Np az N csomópont szülője. Ha az N csomópont fel van osztva, legyen NN az új csomópont. Szúrja be az NN-t az Np-be a Hilbert-távolságnak megfelelő sorrendben, ha van hely. Egyébként az eljárást túlcsorduláskezelésnek (Np , NN ) nevezzük . Ha az Np csomópont fel van osztva, legyen PP az új csomópont.

A3. MBR és LHV értékek módosítása szülői szinten:

Legyen P az S-beli csomópontok szülőcsomópontjainak halmaza. Módosítjuk a megfelelő MBR és LHV értékeket a P csomópontokban.

A4. Továbblépés a következő szintre:

S lesz a P szülő csomópontok halmaza, NN = PP, ha Np fel van osztva. menj az A1-re.

Eltávolítás

A Hilbert R-fában nincs szükség a lelógó csomópontok újra beszúrására, amíg a szülőcsomópont el nem tűnik. Ehelyett a mögöttes csomópontokból vehető kulcsok azonos szintű elemekkel egyesülnek. Ez azért lehetséges, mert a csomópontok (LHV szerint) világos sorrendűek. Ezzel szemben az R-fák esetében nincs ilyen koncepció. Vegye figyelembe, hogy a törlési művelethez s együttműködő csomópontok, míg a beszúrási műveletekhez s - 1 elemek szükségesek.

Eljárás Törlés(r) :
D1. Lap keresése:

Keressük az L lap pontos előfordulását, amely r-t tartalmaz.

D2. R eltávolítása:

Távolítsa el az r-t az L csomópontból.

D3. Ha L üres

az együttműködő csomópontokból átveszünk néhány elemet. ha nincsenek ilyen elemek, s + 1 csomópontot hozzon s csomópontba, újraszámolja a kapott csomópontokat.

D4. Az MBR és LHV értékeit a szülői szinten változtatjuk.

alkotnak egy S halmazt, amely L-t és szövetkezetét tartalmazza csomópontok (ha túlcsordulás történik). hívja a MatchTree(S)-t.

Túlcsordulás kezelése

A Hilbert R-fa túlcsorduláskezelési eljárása a túlcsordulási csomópontokat úgy kezeli, hogy egyes elemeket áthelyez az s - 1 kooperációs csomópontok egyikébe, vagy úgy, hogy s csomópontokat s + 1 csomópontokra oszt fel.

Eljárás túlcsordulás kezelése (N csomópont, r téglalap) :
/* egy új csomópontot ad vissza, ha felosztás történt. */
H1. Legyen ε olyan halmaz, amely tartalmazza az összes elemet N-ből

és s - 1 együttműködő csomópontjai.

H2. ε-hez r-t adunk.
H3. Ha az s - 1 együttműködő csomópontok közül legalább az egyik nincs kitöltve,

ossza el egyenletesen ε-t s-ben a Hilbert-távolságok szerint.

H4. Ha az összes kooperatív csomópont megtelt,

létrehozzuk az NN csomópontot, és egyenletesen elosztjuk az ε-t s + 1 csomópont felett a Hilbert távolságok szerint vissza N.N.

Jegyzetek

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

Irodalom