Çok boyutlu veri yapısı
Çok boyutlu bir veri yapısı , veri çiftlerinin depolanmasını mümkün kılan mantıksal bir yapıdır, böylece bunlara uygulanan işleme operasyonları basitleştirilir.
Bu tür bir yapı, konumları bir veri çifti (Enlem / Boylam / Yükseklik) olarak depolamak için genellikle coğrafi konum belirlemede kullanılır .
R-Tree ailesi
R-Ağacı
R-Ağacı dengeli bir ağaçtır , ağacın yaprakları saklanan nesnelere yapılan referanslardan oluşan indekslenmiş bir dizi içerir. Tüm nesneler bir koleksiyonda saklanır, her nesnenin (veya demetin ) elde edilebilmesi için benzersiz bir tanımlayıcısı vardır.
Yapısı
Ağacın düğümleri aşağıdaki formdaki öğelerden oluşur:
(ben,fbenls-referedeğilvse){\ displaystyle (I, oğul referansı)}
-
fbenls-referedeğilvse{\ displaystyle oğul referansı}
: sonraki düğümün adresi.
-
ben{\ displaystyle I}
: bu çocukların tüm dikdörtgenlerini içeren n boyutlu bir dikdörtgen.
Ağacın yaprakları aşağıdaki şekle sahip unsurlardan oluşur:
(ben,tsenple-bendedeğiltbenfben-dedeğilt){\ textstyle (I, demet kimliği)}
-
tsenple-bendedeğiltbenfben-dedeğilt{\ displaystyle demet tanımlayıcısı}
: bir demet tanımlayıcısı.
-
ben{\ displaystyle I}
: Bu sayfada referans verilen nesneleri içeren n boyutlu bir dikdörtgen.
Özellikleri
İle temsil edilen her dikdörtgen boyut sayısı ile : biçimindedir .
ben{\ displaystyle I}
ben=(ben0,ben1,...,bendeğil-1){\ textstyle I = (I_ {0}, I_ {1}, ..., I_ {n-1})}
değil{\ displaystyle _ {n}}![{\ displaystyle _ {n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afb3a560f0bf252b2365b300441b4b074c75e4b1)
Aşağıdaki varsayımı alarak:
-
DEĞİL{\ displaystyle N}
, depolanan öğelerin sayısı.
-
M{\ displaystyle M}
, bir düğümdeki maksimum öğe sayısı.
-
m{\ displaystyle m}
, bir düğümdeki minimum öğe sayısı.
-
m≤M2{\ displaystyle m \ leq {M \ 2'den fazla}}
, R-Tree'nin bir ayarı.
Ağaç aşağıdaki özelliklere sahiptir:
- Her düğüm , kök hariç, ve öğeleri içerir .m{\ displaystyle m}
M{\ displaystyle M}![M](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
- Ağacın yüksekliği 0 olmadığı sürece kök en az iki çocuk içerir.
- Tüm yapraklar eşit derinliktedir.
-
∀(ben,fbenls-referedeğilvse)⇒{\ displaystyle \ forall (I, oğul-referans) \ Rightarrow}
ben{\ displaystyle I}
alt dikdörtgenleri içeren en küçük dikdörtgendir.
-
∀(ben,tsenple-bendedeğiltbenfben-dedeğilt)⇒{\ displaystyle \ forall (I, tuple-id) \ Rightarrow}
ben{\ displaystyle I}
sayfanın referans verdiği öğeleri içeren en küçük dikdörtgendir.
-
h≤|lÖgmDEĞİL-1|{\ displaystyle h \ leq | log_ {m} N-1 |}
, ağacın yüksekliği ile.h{\ displaystyle h}![h](https://wikimedia.org/api/rest_v1/media/math/render/svg/b26be3e694314bc90c3215047e4a2010c6ee184a)
-
1+∑ben=1değil|DEĞİLmben|{\ displaystyle 1+ \ toplam _ {i = 1} ^ {n} \ sol | {N \ m ^ {i}} üzerinde \ sağ |}
, maksimum düğüm sayısı.
Hilbert r-ağacı
Bu yapı esasen R-Ağacı ile aynıdır, eklemeyi iyileştirmek ve dolayısıyla R-Ağacı'ndan daha iyi bir sonuç elde etmek için sadece düğümler Hilbert değerine göre sıralanır.
Knot
Her düğümün maksimum Hilbert değeri adı verilen ek bir değeri vardır. Bu değer, tüm bu çocuklar arasında mevcut olan maksimum Hilbert değerine karşılık gelir.
Bu Hilbert değeri, Hilbert Eğrisi kullanılarak hesaplanır . Bir dikdörtgenin Hilbert değeri, dikdörtgenin merkezinin Hilbert değeridir.
Bölünmüş
R-Ağacında, bir dikdörtgeni iki alt dikdörtgene bölmeden önce öğeleri beklemeniz gerekir .
M+1{\ displaystyle M + 1}![{\ displaystyle M + 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03c0b0dc5ee6ec29023977ea04ad152977fcba18)
Hilbert R-Ağacı, düğümün elemanlara sahip olmasını bekler ve onu bölmeden önce babası da yapar.
M{\ displaystyle M}![M](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
X-Ağacı
Bu yapı, R-Ağacının aranmasını geliştirmeyi amaçlamaktadır, aslında R-Ağacındaki arama, boyutların sayısı arttıkça çok hızlı bir şekilde bozulmaktadır. Bununla birlikte, en kötü durumda, performans R-Ağacı'na benzer kalır.
Amacı, aynı düğümün birkaç dikdörtgeninin kapladığı toplam alanı azaltmaktır (boyut 2 için).
Bu amaçla, X-Tree bu düğümleri iki kategoriye ayırır.
- R-Ağacına benzer klasik düğümler
- Süper düğümler.
Süper düğümler
Bu süper düğümler, bir R-Ağacının klasik düğümlerine benzer, ancak fark, içerilebilecek maksimum öğe sayısındadır. Bu sayı , geleneksel düğümlerden daha fazladır.
M{\ displaystyle M}![M](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
Amaçları, ağaçtaki olası yolları azaltmak ve dolayısıyla arama süresini iyileştirmek için mümkün olduğunca bölünmekten kaçınmaktır.
Bölme kaçınılmaz olduğunda, yerleştirme sırasında süper düğümler oluşturulur.
Kd-Tree ailesi
Kd-Ağacı
Kd-ağaç bir olan çok boyutlu ikili arama ağacı k alan boyutunu temsil eder.
Yapısı
-
Her düğüm, adlandıracağımız anahtarları içerir .ben{\ displaystyle i}
K0(P),...,Kben(P){\ displaystyle K_ {0} (P), ..., K_ {i} (P)}![{\ displaystyle K_ {0} (P), ..., K_ {i} (P)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb6b8539fe0be5a6098052d5d0b1cf34d95ece99)
- Her düğüm, sıfır olan veya her biri ağaçtaki başka bir düğüme işaret eden iki işaretçi içerir.
- Bir düğüm için , biz arayacak ve onun iki işaretçileri ve onun ayırt edici.P{\ displaystyle P}
fbenlsG(P){\ displaystyle sonG (P)}
fbenlsD(P){\ displaystyle sonD (P)}
DbenSVS(P){\ displaystyle DISC (P)}![{\ displaystyle DISC (P)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7deceecc6c08358d11ef5c7da3d5748e95fdef0c)
- Ayırıcı, kök düğüm için 0'da başlar.
- Ayırıcıya sahip bir düğüm için , iki çocuğu ve ayırıcı olarak sahip .P{\ displaystyle P}
ben{\ displaystyle i}
fbenlsG(P){\ displaystyle sonG (P)}
fbenlsD(P){\ displaystyle sonD (P)}
DbenSVSSsenbenv(ben)=(ben+1){\ displaystyle DISCSuiv (i) = (i + 1)}
mÖd{\ displaystyle modu}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Özellikleri
- Bir kd ağacındaki her şey için, yani herhangi bir düğüm için ,P{\ displaystyle P}
j=DbenSVS(P){\ displaystyle j = DISC (P)}
Q{\ displaystyle Q}
fbenlsG(P){\ displaystyle sonG (P)}
Kj(Q)<Kj(P){\ displaystyle K_ {j} (Q) <K_ {j} (P)}
- Bir kd ağacındaki her şey için, yani herhangi bir düğüm için ,P{\ displaystyle P}
j=DbenSVS(P){\ displaystyle j = DISC (P)}
Q{\ displaystyle Q}
fbenlsD(P){\ displaystyle sonD (P)}
Kj(Q)>Kj(P){\ displaystyle K_ {j} (Q)> K_ {j} (P)}
KDB-Ağacı
KDB ağacı büyük çoklu anahtar kayıtları saklamak için bir çözümdür. Bunun için, veri eklerken veya silerken ilkine yakın bir girdi / çıktı maliyeti ve aynı zamanda yakın bir arama performansı sunmak için kd ağacının yanı sıra B-ağacının güçlü yönlerine dayanır. ikinci.
Bir de Kayıtlar KDB-ağacın formunun olan bir elementtir ve bir sabittir.
vsle0,vsle1,...,vslek-1{\ displaystyle key_ {0}, key_ {1}, ..., key_ {k} -_ {1}}
vsleben{\ displaystyle key_ {i}}
dÖm-debendeğileben{\ displaystyle domaine_ {i}}
k{\ displaystyle k}![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
Olduğu gibi , B-ağacın , her düğüm bir sayfa olarak depolanır. İki tür sayfayı ayırt edeceğiz:
bir nokta , alanın bir öğesi olarak tanımlanırdÖm-debendeğile0,dÖm-debendeğile1,...,dÖm-debendeğilek-1{\ displaystyle alan_ {0}, alan_ {1}, ..., alan_ {k} -_ {1}}
Bir bölge tüm noktaların sette arada olduğu tekabül , .
x0,x1,...,xk-1{\ displaystyle x_ {0}, x_ {1}, ..., x_ {k} -_ {1}}
mbendeğilben≤xben<m-dexben{\ displaystyle min_ {i} \ leq x_ {i} <max_ {i}}
0≤ben≤k-1{\ displaystyle 0 \ leq i \ leq k-1}![{\ displaystyle 0 \ leq i \ leq k-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/252522375b741fb617dd857c18886a3ac917d3c4)
Özellikleri
- Sözde bölge sayfaları her zaman alt sayfalara işaret eder ve boş olamaz. Nokta sayfaları, ağacın yapraklarıdır.
- B ağacı gibi, kökten herhangi bir yaprağa giden yolun boyutu aynıdır.
- Bölge olarak adlandırılan her sayfa için, bu sayfadaki bölgeler ayrıktır ve bunların birleşimi bir bölgedir.
- Kök bir bölge ise, o zaman bölgelerinin birleşimi , yani tüm arama alanıdır.dÖm-debendeğile0,dÖm-debendeğile1,...,dÖm-debendeğilek-1{\ displaystyle alan_ {0}, alan_ {1}, ..., alan_ {k} -_ {1}}
![{\ displaystyle alan_ {0}, alan_ {1}, ..., alan_ {k} -_ {1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b174bd0419f6db34d7d1da769bb559e06c7bc310)
- Sözde bölge sayfasındaki bir çiftin (bölge, çocuk) çocuğu da bir bölge sayfası olduğunda, çocuğun tüm bölgelerinin birleşimi bir bölgedir.
- Tersine, alt sayfa bir nokta ise, sayfadaki tüm noktalar bölgede olmalıdır.
BKD-Ağacı
Birçok çok boyutlu veri yapısı arasında performans, ekleme ve silme sayısı arttıkça düşme eğilimindedir. Aslında, aşağıdaki üç özelliği aynı anda sürdürmek karmaşıktır:
- Yapının maksimum doldurulması
- Veri eklerken veya çıkarırken yapıda minimum değişiklik.
- Yapının bir elemanı veya alanı için minimum arama süresi.
Bir kd ağacına düğüm eklemek ortalama olarak yapılır , ancak dengeli bir yapıyı korumaz. Uygulamada, çok sayıda ekleme sırasında, taleplerin performansını etkileyen dengesiz bir yapı ile karşı karşıyayız. Ek olarak, minimum maliyetle kolayca yeniden dengelenen bazı yapıların aksine, bu, performansını büyük ölçüde azaltan geniş alanların yeniden düzenlenmesini gerektirir.
Ö(lÖg değil){\ displaystyle O (günlük \ n)}![O (günlük \ n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5c5ba521532fa0456492593264b53caee1a71ea)
Benzer şekilde, KDB ağacı potansiyel olarak ağaca bir değer eklerken veya kaldırırken büyük bir yeniden çalışma gerektirir, bu da doldurulurken yapının performansını büyük ölçüde etkiler.
BKD ağacı teklifleri göre bir yapı KDB ağacı % 100 yapısı yakın, hem de karşılaştırılabilir ekleme ve silme mükemmel bir performans kullanımını sağlar kd ağacı . Ancak, ikincisinden farklı olarak, bu performans, yapılan istek sayısına bakılmaksızın korunur.
Bunun için, tek bir ağaç inşa etmek ve her veri ekleme veya silme işleminden sonra onu yeniden dengelemek yerine, her bir alt ağacı bir kd ağacı olarak temsil eder ve böylece yapıyı güncellerken yeniden dengelenecek minimum çıplaklığı belirler.
Dört Ağaç Ailesi
Dört Ağaç
Dörtlü Ağaç, alanı yinelemeli olarak parçalara ayırmanıza olanak tanır . Dörtlü Ağaç, 2 boyutlu bir alan için kullanılır, ancak konsept boyutlara genişletilebilir .
2değil{\ displaystyle 2 ^ {n}}
değil{\ displaystyle n}![değil](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Yapısı
Ağacın düğümleri aşağıdaki yapıdadır:
(ben,elemedeğilts){\ displaystyle (I, öğeler)}
-
ben{\ displaystyle I}
, söz konusu düğümün kapladığı alan.
-
elemedeğilts{\ displaystyle öğeleri}
, bu düğüm tarafından kapsanan öğeler kümesi.
Özellikleri
Aşağıdaki varsayımı alarak:
-
M{\ displaystyle M}
, bir düğümdeki maksimum öğe sayısı.
-
değil{\ displaystyle n}
, boyutların sayısı.
-
S{\ displaystyle S}
ağacın kapladığı toplam alan
-
p{\ displaystyle p}
, bir düğümün derinliği.
Ağaç aşağıdaki özelliklere sahiptir:
- Bir düğümün öğeleri varsa, bunlar çocuklara dağıtılır ve her biri kapladığı alanın eşit bir bölümünü temsil eder .M+1{\ displaystyle M + 1}
2değil{\ displaystyle 2 ^ {n}}
ben{\ displaystyle I}![ben](https://wikimedia.org/api/rest_v1/media/math/render/svg/535ea7fc4134a31cbe2251d9d3511374bc41be9f)
- Derin bir düğüm S'yi örterp{\ displaystyle p}
1p2değil{\ displaystyle 1 \ p2 ^ üzerinde ^ {n}}![{\ displaystyle 1 \ p2 ^ üzerinde ^ {n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6399fb64982a7a73c2ca9f7d7996eb36f777a1a6)
Patricia-Tree ailesi
Patricia ağacı
Burada kullanılan "Patricia" terimi " P ractical bir lgorithm T O R etrieve I için belirtilen bilgi Cı Oded I , n bir lphanumeric".
Patricia-Tree, karakter dizilerini performans ve alan açısından optimize edilmiş bir şekilde saklamanıza izin verir .
Bu tür bir ağaç genellikle bir sözlükte bulunan kelime tahmini için kullanılır.
Yapısı
Ağacın düğümleri aşağıdaki yapıdadır:
(VS){\ displaystyle (C)}
Özellikleri
Aşağıdaki varsayımı alarak:
-
Sm-dex{\ displaystyle S_ {max}}
, ağaçta depolanan en uzun kelimenin boyutu.
- Kök boş dizedir.
Ağaç aşağıdaki özelliklere sahiptir:
- Bir düğümün tüm çocukları, ortak bir öneke sahip kelimelere karşılık gelir.
- Ağaçta depolanan sözcükler ne kadar çok ön eke sahipse, o kadar fazla bellek alanı optimize edilir.
- Ağacın derinliği eşittir Sm-dex{\ displaystyle S_ {max}}
PH-Ağaç ailesi
PH-Ağacı
PH-Tree, P atricia-Tree ailesinin yanı sıra Quad-Tree ( kavram boyutlara genişletildiğinde H ypercube) olmak üzere iki kavramı alır .
değil{\ displaystyle n}![değil](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Bu ağaç, Patricia-Trees'ten farklı olarak, yalnızca dizeleri depolamakla kalmaz, aynı zamanda karmaşık nesneleri, örneğin tamsayı demetlerini depolamanıza olanak tanır .
değil{\ displaystyle n}![değil](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Bunu yapmak için PH-Ağacı , karakterler yerine bitleri depolar .
Yapısı
Ağacın düğümleri aşağıdaki yapıdadır:
(Prefbenxe,HVS,PÖstfbenxes){\ displaystyle (Önek, HC, Son ekler)}
-
Prefbenxe{\ displaystyle Öneki}
, Birinci ortak bit.değil{\ displaystyle n}![değil](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
-
HVS{\ displaystyle HC}
, her biri bit içeren bir hücre dizisi .2değil{\ displaystyle 2 ^ {n}}
değil{\ displaystyle n}![değil](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
-
PÖstfbenxes{\ displaystyle Postfixes}
her biri bit içeren bir kutu dizisi , depolanmış nesnenin ikili temsilinin sonunu temsil eder.2değil{\ displaystyle 2 ^ {n}}
değil{\ displaystyle n}![değil](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Ağacın kökü aşağıdaki yapıdadır:
(HVS){\ displaystyle (HC)}
-
HVS{\ displaystyle HC}
, her biri bit içeren bir hücre dizisi .2değil{\ displaystyle 2 ^ {n}}
değil{\ displaystyle n}![değil](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
Özellikleri
Aşağıdaki varsayımı alarak:
-
Sm-dex{\ displaystyle S_ {max}}
, depolanan en uzun ikili gösterimin boyutu.
- Kökü nesne olarak yorumlayabiliriz değilsenll{\ displaystyle boş}
Ağaç aşağıdaki özelliklere sahiptir:
- Bir düğümün tüm çocukları, her boyut için aynı ikili gösterim başlangıcına sahiptir.
- Ağaçta depolanan nesneler ne kadar çok ortak ikili gösterime sahipse, o kadar fazla bellek alanı optimize edilir.
- Ağacın derinliği eşittir Sm-dex{\ displaystyle S_ {max}}
Karşılaştırmalı
Aşağıdaki tablo, açıklanan yapılara uygulanan çeşitli işlemlerin karmaşıklıklarının kapsamlı olmayan bir listesini göstermektedir.
|
Karmaşıklık
|
---|
Yerleştirme
|
Değişiklik
|
Silme
|
Araştırma
|
---|
Ağaç
|
R
|
Θ(değil){\ displaystyle \ Teta (n)}
|
Θ(değil∗lÖg(değil)){\ displaystyle \ Theta (n * günlük (n))}
|
Θ(değil){\ displaystyle \ Teta (n)}
|
Θ(lÖg(mdeğil)){\ displaystyle \ Theta (günlük (m ^ {n}))}
|
---|
Hilbert
|
|
|
|
Θ(lÖg(mdeğil)){\ displaystyle \ Theta (günlük (m ^ {n}))}
|
---|
X
|
Θ(değil∗lÖg(değil)){\ displaystyle \ Theta (n * günlük (n))}
|
|
Θ(değil){\ displaystyle \ Teta (n)}
|
Θ(lÖg(mdeğil)){\ displaystyle \ Theta (günlük (m ^ {n}))}
|
---|
KD
|
Θ(değil){\ displaystyle \ Teta (n)}
|
Θ(değil){\ displaystyle \ Teta (n)}
|
Θ(değil){\ displaystyle \ Teta (n)}
|
Θ(değil){\ displaystyle \ Teta (n)}
|
---|
BKD
|
|
|
|
|
---|
KDB
|
|
|
|
|
---|
Dörtlü
|
Θ(lÖg(değil)){\ displaystyle \ Theta (günlük (n))}
|
|
|
Θ(lÖg(değil)){\ displaystyle \ Theta (günlük (n))}
|
---|
Patricia
|
Θ(Sm-dex){\ displaystyle \ Theta (S_ {maks})}
|
Θ(Sm-dex){\ displaystyle \ Theta (S_ {maks})}
|
Θ(Sm-dex){\ displaystyle \ Theta (S_ {maks})}
|
Θ(Sm-dex){\ displaystyle \ Theta (S_ {maks})}
|
---|
PH
|
Θ(lÖg(değilm-dex)){\ displaystyle \ Theta (günlük (n_ {maks}))}
|
Θ(lÖg(değilm-dex)){\ displaystyle \ Theta (günlük (n_ {maks}))}
|
Θ(lÖg(değilm-dex)){\ displaystyle \ Theta (günlük (n_ {maks}))}
|
Θ(lÖg(değil)){\ displaystyle \ Theta (günlük (n))}
|
---|
Referanslar
-
Antonin Guttman , " R-ağaçları: Uzamsal Arama için Dinamik Bir Dizin Yapısı ", SIGMOD , ACM, sIGMOD '84,1 st Ocak 1984( ISBN 0-89791-128-8 , DOI 10.1145 / 602259.602266 , çevrimiçi okuyun )
-
Ibrahim Kamel ve Christos Faloutsos , " Hilbert R-tree: An Improved R-tree Using Fractals ", VLBD , Morgan Kaufmann Publishers Inc., vLDB '94,1 st Ocak 1994( ISBN 1-55860-153-8 , çevrimiçi okuyun )
-
Stefan Berchtold , Daniel A. Keim ve Hans-Peter Kriegel , " The X-tree: An Index Structure for High-Dimensional Data ", VLDB , Morgan Kaufmann Publishers Inc., vLDB '96,1 st Ocak 1996( ISBN 1-55860-382-4 , çevrimiçi okuyun )
-
Jon Louis Bentley , " İlişkisel Arama için Kullanılan Çok Boyutlu İkili Arama Ağaçları, " Commun. ACM , cilt. 18,1 st Eylül 1975( ISSN 0001-0782 , DOI 10.1145 / 361002.361007 , çevrimiçi okuyun )
-
John T. Robinson , " KDB-ağacı: Büyük Çok Boyutlu Dinamik Dizinler için Bir Arama Yapısı ", SIGMOD , ACM, sIGMOD '81,1 st Ocak 1981( ISBN 0-89791-040-0 , DOI 10.1145 / 582318.582321 , çevrimiçi okuyun )
-
(inç) Octavian Procopiuc , Pankaj K. Agarwal , Lars Arge ve Jeffrey Scott Vitter , Bkd-Tree: A Dynamic Scalable kd-tree , Springer Berlin Heidelberg al. "Bilgisayar Bilimlerinde Ders Notları",24 Temmuz 2003( ISBN 978-3-540-40535-1 ve 978-3-540-45072-6 , DOI 10.1007 / 978-3-540-45072-6_4 , çevrimiçi okuyun )
-
(inç) RA Finkel ve JL Bentley , " Dörtlü ağaçların geri alma için veri yapısı vardır, bileşik anahtarlardır " , Acta Informatica , cilt. 4,1 st Mart 1974( ISSN 0001-5903 ve 1432-0525 , DOI 10.1007 / BF00288933 , çevrimiçi okuyun )
-
Donald R. Morrison , " PATRICIA - Alfanümerik Olarak Kodlanmış Bilgileri Almak İçin Pratik Algoritma " J. ACM , cilt. 15,1 st Ekim 1968( ISSN 0004-5411 , DOI 10.1145 / 321479.321481 , çevrimiçi okuyun )
-
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">