Többdimenziós adatszerkezet
A többdimenziós adatstruktúra egy logikai struktúra, amely lehetővé teszi az adatpárok tárolását, hogy a rájuk alkalmazott feldolgozási műveletek leegyszerűsödjenek.
Ezt a típusú struktúrát gyakran használják a földrajzi helymeghatározásban , annak érdekében, hogy a pozíciókat adatpárként tárolják (szélesség / hosszúság / magasság).
R-Tree család
R-fa
Az R-fa kiegyensúlyozott fa , a fa levelei indexelt tömböt tartalmaznak, amely tárolt objektumokra való hivatkozásokból áll. Az összes objektum egy gyűjteményben van tárolva, mindegyik objektumnak (vagy duplának ) egyedi azonosítója van annak megszerzéséhez.
Szerkezet
A fa csomópontjai a következő formájú elemekből állnak:
(én,fénls-referenemvs.e){\ displaystyle (I, fia-referencia)}
-
fénls-referenemvs.e{\ displaystyle son-reference} : a következő csomópont címe.
-
én{\ displaystyle I} : n-dimenziós téglalap, amely e gyermekek összes téglalapját tartalmazza.
A fa levelei a következő alakú elemekből állnak:
(én,tuole-éndenemténfénnál nélnemt){\ textstyle (I, tuple-id)}
-
tuole-éndenemténfénnál nélnemt{\ displaystyle tuple-azonosító} : kettős azonosító.
-
én{\ displaystyle I} : egy n-dimenziós téglalap, amely tartalmazza a lap által hivatkozott objektumokat.
Tulajdonságok
Mindegyik téglalap által képviselt formában van :, a száma dimenzió.
én{\ displaystyle I}én=(én0,én1,...,énnem-1){\ textstyle I = (I_ {0}, I_ {1}, ..., I_ {n-1})}nem{\ displaystyle _ {n}}
A következő posztulátum felhasználásával:
-
NEM{\ displaystyle N}, a tárolt elemek száma.
-
M{\ displaystyle M}, a csomópontban található elemek maximális száma.
-
m{\ displaystyle m}, a csomópont minimális elemszáma.
-
m≤M2{\ displaystyle m \ leq {M \ over 2}} , az R-fa beállítása.
A fa a következő tulajdonságokkal rendelkezik:
- Minden csomópont tartalmaz és elemeket tartalmaz , a gyökér kivételével.m{\ displaystyle m}M{\ displaystyle M}
- A gyökér legalább két gyermeket tartalmaz, kivéve, ha a fa magassága 0.
- Minden levél azonos mélységű.
-
∀(én,fénls-referenemvs.e)⇒{\ displaystyle \ forall (I, fia-referencia) \ Rightarrow} én{\ displaystyle I} a legkisebb téglalap, amely a gyermek téglalapokat tartalmazza.
-
∀(én,tuole-éndenemténfénnál nélnemt)⇒{\ displaystyle \ forall (I, tuple-id) \ Rightarrow} én{\ displaystyle I} a legkisebb téglalap, amely a lap által hivatkozott elemeket tartalmazza.
-
h≤|logmNEM-1|{\ displaystyle h \ leq | log_ {m} N-1 |}, a fa magasságával.h{\ displaystyle h}
-
1+∑én=1nem|NEMmén|{\ displaystyle 1+ \ sum _ {i = 1} ^ {n} \ balra | {N \ m ^ {i}} \ jobbra |}, a csomópontok maximális száma.
Hilbert r-fa
Ez a szerkezet lényegében megegyezik az R-Tree struktúrájával, csak a csomópontok vannak Hilbert-érték szerint rendezve a beillesztés javítása érdekében, ezért jobb eredményt érnek el, mint az R-fán.
Csomók
Minden csomópontnak van egy további értéke, az úgynevezett maximális Hilbert-érték. Ez az érték megegyezik a gyerekek között fennálló maximális Hilbert-értékkel.
Ezt a Hilbert-értéket a Hilbert-görbe segítségével számítják ki . A téglalap Hilbert-értéke a téglalap közepének Hilbert-értéke.
Hasított
Az R-fában meg kell várni az elemeket, mielőtt egy téglalapot két résznégyszögre osztana.
M+1{\ displaystyle M + 1}
A Hilbert R-Tree várja, hogy a csomópontban legyenek elemek, és ugyanúgy az apja is, mielőtt felosztaná.
M{\ displaystyle M}
X-fa
Ennek a szerkezetnek az a célja, hogy javítsa az R-fa keresését, sőt, az R-fában való keresés nagyon gyorsan romlik, amikor a dimenziók száma növekszik. A legrosszabb esetben azonban a teljesítmény hasonló marad az R-Tree-hez.
Célja az ugyanazon csomópont több téglalapja által lefedett teljes terület csökkentése (a 2. dimenzió esetében).
Erre a célra különbözteti meg az X-fa ezeket a csomópontokat két kategóriába
- Klasszikus csomók, hasonlóak az R-fához
- A szuper-csomópontok.
Supernodes
Ezek a szupercsomópontok hasonlítanak az R-fa klasszikus csomópontjaihoz, azonban a különbség a maximálisan tartalmazható elemek számában mutatkozik meg. Ez a szám nagyobb, mint a hagyományos csomópontoké.
M{\ displaystyle M}
Céljuk, hogy a lehető legnagyobb mértékben elkerüljék a hasadást, hogy csökkentsék a fa lehetséges útjait, és ezáltal javítsák a keresési időt.
A szupernódok a beillesztéskor jönnek létre, amikor a felosztás elkerülhetetlen.
Kd-Tree család
Kd-fa
A kd-fa egy többdimenziós bináris kereső fa, ahol k a tér dimenzióját képviseli.
Szerkezet
-
Minden csomópont tartalmaz kulcsokat, amelyeket megnevezünk .én{\ displaystyle i}K0(P),...,Kén(P){\ displaystyle K_ {0} (P), ..., K_ {i} (P)}
- Minden csomópont két mutatót tartalmaz, amelyek nullaak vagy a fa egy másik csomópontjára mutatnak.
- Egy csomópont esetén felhívjuk és két mutatóját, valamint megkülönböztetőjét.P{\ displaystyle P}fénlsG(P){\ displaystyle sonG (P)}fénlsD(P){\ displaystyle sonD (P)}DénSVS(P){\ displaystyle DISC (P)}
- A diszkrimináns 0-nál kezdődik a gyökércsomópontnál.
- Egy olyan csomópont esetében, amelynek ugyanolyan megkülönböztető képessége van , annak két gyermeke van, és ugyanolyan megkülönböztető képességgel rendelkezik .P{\ displaystyle P}én{\ displaystyle i}fénlsG(P){\ displaystyle sonG (P)}fénlsD(P){\ displaystyle sonD (P)}DénSVSSuénv(én)=(én+1){\ displaystyle DISCSuiv (i) = (i + 1)} mod{\ displaystyle mod} k{\ displaystyle k}
Tulajdonságok
- Mindenre, ami egy kd-fában van, vagyis bármely csomópontra ,P{\ displaystyle P}j=DénSVS(P){\ displaystyle j = LEMEZ (P)}Q{\ displaystyle Q} fénlsG(P){\ displaystyle sonG (P)}Kj(Q)<Kj(P){\ displaystyle K_ {j} (Q) <K_ {j} (P)}
- Mindenre, ami egy kd-fában van, vagyis bármely csomópontra ,P{\ displaystyle P}j=DénSVS(P){\ displaystyle j = LEMEZ (P)}Q{\ displaystyle Q} fénlsD(P){\ displaystyle sonD (P)}Kj(Q)>Kj(P){\ displaystyle K_ {j} (Q)> K_ {j} (P)}
KDB-fa
A KDB-fa megoldást kínál nagy, többkulcsos rekordok tárolására. Ehhez a B-fa és a kd-fa erősségeire támaszkodik annak érdekében, hogy az adatok hozzáadásakor vagy törlésénél az elsőhöz közeli bemeneti / kimeneti költséget kínáljon, valamint a a második.
A KDB-fában lévő rekordok olyan alakúak, ahol a konstans elem és konstans.
vs.le0,vs.le1,...,vs.lek-1{\ displaystyle key_ {0}, key_ {1}, ..., key_ {k} -_ {1}}vs.leén{\ displaystyle kulcs_ {i}}domnál nélénnemeén{\ displaystyle domaine_ {i}}k{\ displaystyle k}
A B-fához hasonlóan minden csomópontot oldalként tárolnak. Kétféle oldalt különböztetünk meg:
egy pontot a tartomány elemeként írnak ledomnál nélénneme0,domnál nélénneme1,...,domnál nélénnemek-1{\ displaystyle domain_ {0}, domain_ {1}, ..., domain_ {k} -_ {1}}
a régió az időközben a sor összes pontot megfelelő , .
x0,x1,...,xk-1{\ displaystyle x_ {0}, x_ {1}, ..., x_ {k} -_ {1}}ménnemén≤xén<mnál nélxén{\ displaystyle min_ {i} \ leq x_ {i} <max_ {i}}0≤én≤k-1{\ displaystyle 0 \ leq i \ leq k-1}
Tulajdonságok
- Az úgynevezett régiós oldalak mindig utódlapokra mutatnak, és nem lehetnek üresek. Az úgynevezett pontoldalak a fa levelei.
- A B fához hasonlóan a gyökértől bármely levélig terjedő út nagysága megegyezik.
- Minden régiónak nevezett oldal esetében az ezen az oldalon található régiók nem kapcsolódnak egymáshoz, és egyesülésük régió.
- Ha a gyökér régió, akkor régióinak egyesülése , vagyis a teljes keresési terület.domnál nélénneme0,domnál nélénneme1,...,domnál nélénnemek-1{\ displaystyle domain_ {0}, domain_ {1}, ..., domain_ {k} -_ {1}}
- Amikor az úgynevezett régióoldalon egy pár (régió, gyermek) gyermeke is régióoldal, akkor a gyermek összes régiójának egyesülése régió.
- Ezzel szemben, ha a gyermekoldal pont, akkor az oldal összes pontjának a régióban kell lennie.
BKD-fa
A sokdimenziós adatstruktúra közül a teljesítmény általában csökkenti a kiegészítések és a törlések számát. Valójában a következő három jellemző egyidejű fenntartása bonyolult:
- A szerkezet maximális kitöltése
- Minimális változás a struktúrában adatok hozzáadásakor vagy eltávolításakor.
- Minimális keresési idő egy elemre vagy a szerkezet területére.
Csomópont hozzáadása egy kd-fához átlagosan ben történik , de nem tartja kiegyensúlyozott szerkezetet. A gyakorlatban a nagyszámú kiegészítés során tehát kiegyensúlyozatlan struktúrával kell szembenéznünk, amely hatással van a kérések teljesítésére. Ezenkívül, ellentétben bizonyos struktúrákkal, amelyek könnyen egyensúlyba hozhatók minimális költség mellett, ez nagy területek átszervezését igényli, ami nagymértékben csökkenti annak teljesítményét.
O(log nem){\ displaystyle O (log \ n)}
Hasonlóképpen, a KDB-fa valószínűleg nagy átdolgozást igényel egy érték hozzáadásakor vagy eltávolításakor, ami erősen befolyásolja a szerkezet teljesítményét.
A BKD-fa a KDB-fán alapuló struktúrát kínál, amely lehetővé teszi a szerkezet közel 100% -os kihasználását, valamint az összeadás és törlés kiváló teljesítményét, hasonlóan a kd-fához . Ez utóbbival ellentétben azonban ez a teljesítmény fennmarad, függetlenül a benyújtott kérések számától.
Ehhez ahelyett, hogy egyetlen fát építene és minden adat hozzáadása vagy törlése után kiegyensúlyozná, az egyes részfákat kd-fának képviseli , és ezáltal meghatározza a szerkezet egyensúlyának frissítéséhez szükséges minimális minimumot.
Négyfás család
Quad-Tree
A Quad-Tree lehetővé teszi, hogy rekurzívan ossza fel a teret . A Quad-Tree-t kétdimenziós térhez használják, azonban a koncepció kiterjedhet a dimenziókra is.
2nem{\ displaystyle 2 ^ {n}}nem{\ displaystyle n}
Szerkezet
A fa csomópontjai a következő felépítésűek:
(én,elemenemts){\ displaystyle (I, elemek)}
-
én{\ displaystyle I} , a kérdéses csomópont által lefedett tér.
-
elemenemts{\ displaystyle elemek}, a csomópont által lefedett elemek halmaza.
Tulajdonságok
A következő posztulátum felhasználásával:
-
M{\ displaystyle M}, a csomópontban található elemek maximális száma.
-
nem{\ displaystyle n}, a méretek száma.
-
S{\ displaystyle S}, a fa által lefedett teljes terület
-
o{\ displaystyle p}, egy csomópont mélysége.
A fa a következő tulajdonságokkal rendelkezik:
- Ha egy csomópontnak vannak elemei, akkor ezek eloszlanak a gyermekekben, amelyek mindegyike a lefedett tér egyenlő részét képviseli .M+1{\ displaystyle M + 1}2nem{\ displaystyle 2 ^ {n}}én{\ displaystyle I}
- Mély csomó borítja S-to{\ displaystyle p}1o2nem{\ displaystyle 1 \ p2 felett ^ {n}}
Patricia-Tree család
Patricia-fa
A "Patrícia" eszközt " P GYAKORLATI Egy lgorithm T o R etrieve I NFORMÁCIÓK C Oded I n A lphanumeric".
A Patricia-fa lehetővé teszi a karakterláncok optimalizált tárolását a teljesítmény és a tér szempontjából.
Ezt a fajta fát gyakran használják egy szótárban található szavak előrejelzésére.
Szerkezet
A fa csomópontjai a következő felépítésűek:
(VS){\ displaystyle (C)}
Tulajdonságok
A következő posztulátum felhasználásával:
-
Smnál nélx{\ displaystyle S_ {max}}, a fában tárolt leghosszabb szó mérete.
- A gyökér az üres karakterlánc.
A fa a következő tulajdonságokkal rendelkezik:
- Egy csomópont összes gyermeke megfelel a közös előtagú szavaknak.
- Minél több előtaggal rendelkezik a fában tárolt szavak, annál több memóriahely optimalizálódik.
- A fa mélysége megegyezik Smnál nélx{\ displaystyle S_ {max}}
PH-Tree család
PH-fa
A PH-fa két fogalmat vesz fel, a P atricia-Tree család, valamint a Quad-Tree ( H ypercube, amikor a koncepció kiterjed a dimenziókra) fogalmakat .
nem{\ displaystyle n}
Ez a fa a Patricia-Fákkal ellentétben nem csak karakterláncokat tárol, hanem komplex objektumokat is tárol, például egész számokat.
nem{\ displaystyle n}
Ehhez a PH-Tree biteket tárol karakterek helyett.
Szerkezet
A fa csomópontjai a következő felépítésűek:
(Prefénxe,HVS,Postfénxes){\ displaystyle (előtag, HC, Postfixek)}
-
Prefénxe{\ displaystyle előtag}, az első megosztott bitek.nem{\ displaystyle n}
-
HVS{\ displaystyle HC}, sejtek tömbje , mindegyik bitet tartalmaz .2nem{\ displaystyle 2 ^ {n}}nem{\ displaystyle n}
-
Postfénxes{\ displaystyle Postfixes}, a dobozok tömbje , amelyek mindegyike tartalmaz biteket, a tárolt objektum bináris ábrázolásának végét jelenti.2nem{\ displaystyle 2 ^ {n}}nem{\ displaystyle n}
A fa gyökere a következő felépítésű:
(HVS){\ displaystyle (HC)}
-
HVS{\ displaystyle HC}, sejtek tömbje , mindegyik bitet tartalmaz .2nem{\ displaystyle 2 ^ {n}}nem{\ displaystyle n}
Tulajdonságok
A következő posztulátum felhasználásával:
-
Smnál nélx{\ displaystyle S_ {max}}, a legtovább tárolt bináris ábrázolás mérete.
- Értelmezhetjük a gyökér objektumként nemull{\ displaystyle null}
A fa a következő tulajdonságokkal rendelkezik:
- Egy csomópont összes gyermekének ugyanaz a bináris ábrázolás kezdete minden dimenziónál.
- Minél több a fában tárolt objektumnak van közös bináris reprezentációja, annál több memóriaterület optimalizálódik.
- A fa mélysége megegyezik Smnál nélx{\ displaystyle S_ {max}}
Összehasonlító
Az alábbi táblázat a leírt struktúrákra alkalmazott különféle műveletek összetettségének nem teljes felsorolását mutatja.
|
Bonyolultság
|
---|
Beszúrás
|
Módosítás
|
Törlés
|
Kutatás
|
---|
Fa
|
R
|
Θ(nem){\ displaystyle \ Theta (n)}
|
Θ(nem∗log(nem)){\ displaystyle \ Theta (n * log (n))}
|
Θ(nem){\ displaystyle \ Theta (n)}
|
Θ(log(mnem)){\ displaystyle \ Theta (napló (m ^ {n}))}
|
---|
Hilbert
|
|
|
|
Θ(log(mnem)){\ displaystyle \ Theta (napló (m ^ {n}))}
|
---|
x
|
Θ(nem∗log(nem)){\ displaystyle \ Theta (n * log (n))}
|
|
Θ(nem){\ displaystyle \ Theta (n)}
|
Θ(log(mnem)){\ displaystyle \ Theta (napló (m ^ {n}))}
|
---|
KD
|
Θ(nem){\ displaystyle \ Theta (n)}
|
Θ(nem){\ displaystyle \ Theta (n)}
|
Θ(nem){\ displaystyle \ Theta (n)}
|
Θ(nem){\ displaystyle \ Theta (n)}
|
---|
BKD
|
|
|
|
|
---|
KDB
|
|
|
|
|
---|
Quad
|
Θ(log(nem)){\ displaystyle \ Theta (log (n))}
|
|
|
Θ(log(nem)){\ displaystyle \ Theta (log (n))}
|
---|
Patricia
|
Θ(Smnál nélx){\ displaystyle \ Theta (S_ {max})}
|
Θ(Smnál nélx){\ displaystyle \ Theta (S_ {max})}
|
Θ(Smnál nélx){\ displaystyle \ Theta (S_ {max})}
|
Θ(Smnál nélx){\ displaystyle \ Theta (S_ {max})}
|
---|
PH
|
Θ(log(nemmnál nélx)){\ displaystyle \ Theta (napló (n_ {max}))}
|
Θ(log(nemmnál nélx)){\ displaystyle \ Theta (napló (n_ {max}))}
|
Θ(log(nemmnál nélx)){\ displaystyle \ Theta (napló (n_ {max}))}
|
Θ(log(nem)){\ displaystyle \ Theta (log (n))}
|
---|
Hivatkozások
-
Antonin Guttman , „ R-fák: Dinamikus indexstruktúra a térbeli kereséshez ”, SIGMOD , ACM, sIGMOD '84,1 st január 1984( ISBN 0-89791-128-8 , DOI 10.1145 / 602259.602266 , online olvasás )
-
Ibrahim Kamel és Christos Faloutsos , „ Hilbert R-tree: An Improved R-tree Fractals Using ”, VLBD , Morgan Kaufmann Publishers Inc., vLDB '94,1 st január 1994( ISBN 1-55860-153-8 , online olvasás )
-
Stefan Berchtold , Daniel A. Keim és Hans-Peter Kriegel , „ Az X-fa: A nagydimenziós adatok indexstruktúrája ”, VLDB , Morgan Kaufmann Publishers Inc., vLDB '96,1 st január 1996( ISBN 1-55860-382-4 , online olvasás )
-
Jon Louis Bentley , „ Az asszociatív kereséshez használt multidimenzionális bináris keresési fák ”, Commun. ACM , vol. 18,1 st szeptember 1975( ISSN 0001-0782 , DOI 10.1145 / 361002.361007 , online olvasás )
-
John T. Robinson , „ A KDB-fa: keresési struktúra nagy többdimenziós dinamikus indexek számára ”, SIGMOD , ACM, sIGMOD '81,1 st január 1981( ISBN 0-89791-040-0 , DOI 10.1145 / 582318.582321 , online olvasás )
-
(a) Octavian Procopiuc , Pankaj K. Agarwal , Lars Arge és Jeffrey Scott Vitter , BKD-Fa: Egy dinamikus skálázható kd-fa , Springer Berlin Heidelberg al. "Előadási jegyzetek a számítástechnikában",2003. július 24( ISBN 978-3-540-40535-1 és 978-3-540-45072-6 , DOI 10.1007 / 978-3-540-45072-6_4 , olvassa el online )
-
(in) RA Finkel és JL Bentley : "A quad fák adatszerkezete a visszakeresés összetett kulcsok " , Acta Informatica , vol. 4,1 st március 1974( ISSN 0001-5903 és 1432-0525 , DOI 10.1007 / BF00288933 , online olvasás )
-
Donald R. Morrison , „ PATRICIA - Gyakorlati algoritmus az alfanumerikusan kódolt információk lekérésére ”, J. ACM , vol. 15,1 st október 1968( ISSN 0004-5411 , DOI 10.1145 / 321479.321481 , online olvasás )
-
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">