高維索引(數(shù)據(jù)庫(kù))

時(shí)間：2022-12-22 12:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-12-22 12:30:01 來(lái)源：信息時(shí)代

    高維索引 : 針對(duì)三維或更多維空間數(shù)據(jù)所建立的索引。隨著三維地理信息系統(tǒng)、多媒體數(shù)據(jù)庫(kù)及時(shí)空數(shù)據(jù)庫(kù)的研究和發(fā)展,對(duì)多維空間目標(biāo)的搜索及更新功能的要求越來(lái)越迫切,而目前常用的空間索引技術(shù),主要是針對(duì)一維或二維空間中的空間數(shù)據(jù)。將這些索引技術(shù)運(yùn)用于三維或更高維空間數(shù)據(jù)時(shí),其查詢效率將大大降低,有時(shí),索引機(jī)制甚至不起作用?？蓴U(kuò)展的高維索引技術(shù)不但能有效地檢索一維或二維空間數(shù)據(jù),而且能有效地檢索高維的空間數(shù)據(jù)。
1. VP-樹(shù)
VP-樹(shù)(vantage point tree)是度量空間(metric space)中較早提出的索引技術(shù)。它將三個(gè)對(duì)象間的距離所存在的三角不等式關(guān)系用于近似查詢的過(guò)濾,從而保證查詢的正確性,并減少了目標(biāo)點(diǎn)和空間數(shù)據(jù)點(diǎn)之間進(jìn)行距離計(jì)算的次數(shù)。VP-樹(shù)包含兩類結(jié)點(diǎn): 內(nèi)部結(jié)點(diǎn)和葉子結(jié)點(diǎn)。以二叉VP-樹(shù)為例,其每個(gè)內(nèi)部結(jié)點(diǎn)的結(jié)構(gòu)形如(S_v,M,L_ptr,R_ptr),其中S_v代表受益對(duì)象點(diǎn)(vantage point),M是被當(dāng)前結(jié)點(diǎn)所索引的子樹(shù)中所有數(shù)據(jù)點(diǎn)與受益點(diǎn)S_v之間的距離的中值,L_ptr和R_ptr分別是指向該索引結(jié)點(diǎn)左、右子樹(shù)的指針。L_ptr指向的數(shù)據(jù)結(jié)點(diǎn)到受益點(diǎn)S_v之間的距離均小于或等于M,R_ptr指向的數(shù)據(jù)結(jié)點(diǎn)到受益點(diǎn)S_v之間的距離均大于或等于M。
對(duì)于一個(gè)給定的查詢對(duì)象Q,如果令d(Q,S_v)表示查詢對(duì)象Q與受益點(diǎn)S_v之間的距離,那么滿足與Q之間的距離在某個(gè)值r之內(nèi)的所有數(shù)據(jù)對(duì)象的查找步驟如下:
(1)從根結(jié)點(diǎn)開(kāi)始查找。
(2)如果d(Q,S_v)≤r,那么根結(jié)點(diǎn)中的S_v就是結(jié)果集。
(3)如果d(Q,S_v)+r≥M,那么遞歸查找當(dāng)前結(jié)點(diǎn)的右子樹(shù)。
(4)如果d(Q,S_v)-r≤M,那么遞歸查找當(dāng)前結(jié)點(diǎn)的左子樹(shù)。
注意,如果條件(3)和(4)都滿足,那么當(dāng)前結(jié)點(diǎn)的兩個(gè)左、右分支都要被查找。
2. M-樹(shù)
為了克服靜態(tài)索引結(jié)構(gòu)的缺點(diǎn),P.Ciaccia等提出了一種動(dòng)態(tài)的基于度量空間的索引結(jié)構(gòu)M-樹(shù)(M-tree),它很好地解決了數(shù)據(jù)更新頻繁的問(wèn)題,當(dāng)向數(shù)據(jù)庫(kù)中添加或刪除媒體對(duì)象時(shí),不需要進(jìn)行索引的重構(gòu)。
同VP-樹(shù)相比,M-樹(shù)是一種全新的索引結(jié)構(gòu)。它是一種分頁(yè)的平衡樹(shù)結(jié)構(gòu),采用自底向上的建樹(shù)方法,引入對(duì)象提升和分裂機(jī)制,實(shí)現(xiàn)了索引結(jié)構(gòu)的動(dòng)態(tài)變化,從而避免了數(shù)據(jù)庫(kù)更新過(guò)程中對(duì)索引進(jìn)行定期更新的繁瑣工作。它在進(jìn)行查詢時(shí),充分采用三角不等式的過(guò)濾機(jī)制,大大減少了查詢時(shí)的距離計(jì)算次數(shù)。
M-樹(shù)中的對(duì)象分為兩類:數(shù)據(jù)庫(kù)對(duì)象和路徑對(duì)象。葉子結(jié)點(diǎn)保存所有的數(shù)據(jù)庫(kù)對(duì)象,而內(nèi)部結(jié)點(diǎn)保存所有的路徑對(duì)象。路徑對(duì)象是通過(guò)特定的結(jié)點(diǎn)提升算法獲得的。
M-樹(shù)中包含兩類結(jié)點(diǎn): 葉子結(jié)點(diǎn)和非葉子結(jié)點(diǎn)(中間結(jié)點(diǎn))。非葉子結(jié)點(diǎn)的結(jié)構(gòu)為:L(O_r,ptr(T(O_r)),r(O_r),d(O_r,P(O_r)),其中O_r是路徑對(duì)象的特征值;ptr(T(O_r))是一個(gè)指向子樹(shù)T(O_r)根結(jié)點(diǎn)的指針,其中的T(O_r)稱為O_r的覆蓋樹(shù); r(O_r)是O_r的覆蓋半徑;d(O_r,P(O_r))是O_r到它父結(jié)點(diǎn)中心的距離。葉子結(jié)點(diǎn)的結(jié)構(gòu)為: R(O_j,oid(O_j),d(O_j,P(O_j)),其中O_j是數(shù)據(jù)庫(kù)對(duì)象的特征值; oid(O_j)是對(duì)象標(biāo)識(shí)符,它指向數(shù)據(jù)庫(kù)對(duì)象;d(O_j,P(O_j))是O_j到它父結(jié)點(diǎn)中心的距離。
M-樹(shù)結(jié)構(gòu)有如下特點(diǎn):
(1)根結(jié)點(diǎn)如果不是葉子結(jié)點(diǎn),則至少有兩條記錄。除了根結(jié)點(diǎn)以外的每個(gè)結(jié)點(diǎn)中記錄的最小數(shù)目由結(jié)點(diǎn)的最低空間利用率決定,而結(jié)點(diǎn)中記錄的最大個(gè)數(shù)受到外存頁(yè)面大小的限制。
(2)子空間之間存在交叉重疊現(xiàn)象。
M-樹(shù)第一次考慮了距離計(jì)算的復(fù)雜性,實(shí)現(xiàn)了范圍查詢。并在范圍查詢的基礎(chǔ)上,采用啟發(fā)式規(guī)則,實(shí)現(xiàn)了近鄰查詢。當(dāng)M-樹(shù)進(jìn)行范圍查詢時(shí),首先從根結(jié)點(diǎn)出發(fā),遞歸遍歷所有沒(méi)能被濾掉的路徑,直到葉子結(jié)點(diǎn)。在中間結(jié)點(diǎn),通過(guò)三角不等式運(yùn)算,不經(jīng)過(guò)任何距離計(jì)算,就可能將一些子樹(shù)過(guò)濾掉。在M-樹(shù)的最近鄰查詢中,同樣使用了三角不等式的過(guò)濾作用,同時(shí)利用了啟發(fā)式機(jī)制,利用優(yōu)先隊(duì)列和結(jié)果數(shù)組的更新來(lái)控制有效子樹(shù)的選擇和查詢的進(jìn)程。