多維數據索引方法綜述

1、整理課件多維數據索引方法綜述楊 風 召整理課件為什么要研究多維數據索引？n空間數據庫n多媒體對象圖象、文本、視頻等特征向量 相似性查詢n數據挖掘n聚類、異常檢測等n空間數據挖掘n多媒體數據挖掘nCAD、分子生物學等整理課件傳統(tǒng)的索引方法n哈希表 n數值的精確匹配 n不能進行范圍查詢 nB-Trees ISAM n鍵值的一維排序 n不能搜索多維空間整理課件處理多維（multi-dimension）點數據的索引結構的比較 nCell 方法 nK-d Trees Quad TreesnK-D-B Trees（J T Robinson SIGMOD1981） nCorner Stitching nGr

2、id files 整理課件處理多維（multi-dimension）點數據的索引結構方 法位 置維位 置Point quad-tree自適應k-d磚 墻k-d tree自適應1-d磚 墻Grid file固 定1-d網 格K-D-B-tree自適應1-d磚 墻整理課件處理矩形的方法 n將矩形轉變成更高維區(qū)間上的點（二維空間上的矩形可以看作四維空間上的點）。 n用空間充填曲線（space filling curve）將k-d空間映射為1-d空間。這種方法適用于分頁環(huán)境。它用z變換將k-d對象轉變?yōu)榫€段 n將原始空間劃分為合適的子空間（重疊或分離的） n劃分為分離子空間 用處理多維點的空間劃分方法

3、，只是若一個矩形被分到多個區(qū)域，可將該矩形分成幾個部分，每一部分都加上標簽，表示他們同屬于一個矩形。 n劃分為有重疊子空間 整理課件R-tree（A. Guttman SIGMOD1984） 整理課件R-tree的特點nR-tree是B-Tree對多維對象（點和區(qū)域）的擴展 nR-tree是一棵平衡樹 n一個多維對象只能被分到一個子空間中去 n若用動態(tài)插入算法構建R-tree，在樹的結點中會引起過多的空間重疊和死區(qū)（dead-space）,使算法性能降低 整理課件R-tree的典型算法n查找n插入n選擇葉子結點n分裂結點（有多種算法）n調整樹n必要時增加樹的高度n刪除n找到包含要刪除記錄的葉子

4、結點n刪除n壓縮樹n必要時減小樹的高度n更新n先刪除老的記錄索引，在插入新的記錄索引整理課件R+-tree (T. Sellis VLDB1987) 整理課件R+-tree 的特點nR+-tree是K-D-B-tree對非0面積對象（不僅可以處理點，也可以處理矩形）的擴展 n不需要覆蓋整個初始空間 nR+-tree比R-tree表現出更好的搜索性能（特別對點的查詢），但要占據較多的存儲空間 整理課件R*-Tree（N. Beckmann SIGMOD1990） nR*-Tree通過修改插入、分裂算法，并通過引入強制重插機制對R-Tree的性能進行改進。 nR*-Tree和R-Tree一樣允許矩

5、形的重疊，nR*-Tree在選擇插入路徑時同時考慮矩形的面積、空白區(qū)域和重疊的大小，而R-Tree只考慮面積的大小。整理課件SS-Tree (D. A. White ICDE1996 ) 整理課件SS-Tree的特點nSS-Tree對R*-Tree進行了改進，通過以下措施提高了最鄰近查詢的性能：n用最小邊界園代替最小邊界矩形表示區(qū)域的形狀；n增強了最鄰近查詢的性能；n減少將近一半的存儲空間。 nSS-Tree改進了R*-Tree的強制重插機制。 整理課件X-Tree (S. Berchtold VLDB1996) n當維數增加到5時，R-Tree及其變種中的邊界矩形的重疊將達到90%，因此在高

6、維（high-dimension）情況（=5)下，其性能將變得很差，甚至不如順序掃描。nX-Tree是線性數組和層狀的R-Tree的雜合體，通過引入超級結點（supernode），大大地減少了最小邊界矩形之間的重疊。提高了查詢的效率。 整理課件X-Tree的結構整理課件邊界矩形和邊界圓的比較n邊界矩形的直徑（對角線）比邊界圓大， SS-Tree將點分到小直徑區(qū)域。由于區(qū)域的直徑對最鄰近查詢性能的影響較大，因此SS-Tree的最鄰近查詢性能優(yōu)于R*-Tree；n邊界矩形的平均容積比邊界圓小， R*-Tree將點分到小容積區(qū)域；由于大的容積會產生較多的覆蓋，因此邊界矩形在容積方面要優(yōu)于邊界圓。整理

7、課件SR-Tree (N. Katayama SIGMOD1997)整理課件SR-Tree的索引結構整理課件SR-Tree的特點n既采用了最小邊界圓（MBS），也采用了最小邊界矩形（MBR）。n相對于SS-Tree，減小了區(qū)域的面積，提高了區(qū)域之間的分離性。n相對于R*-Tree，提高了最鄰近查詢的性能。整理課件VA-File (R. Weber VLDB1998) nVA-File（Vector Approximation File）是一種簡單但非常有效的方式，它將數據空間劃分成2b單元（cell），b表示用戶指定的二進制位數，每個單元分配一個位串。位于某個單元內的向量用這個單元近似代替。V

8、A-File本身只是這些近似體的數組。查詢時，先掃描VA-File，選擇侯選向量，再訪問向量文件進行驗證。 整理課件VA-File的建立整理課件A-Tree (Y. Sakurai VLDB2000) n吸取SR-Tree和VA-File 的長處n引入虛擬邊界矩形VBR（Virtual Bounding Rectangles)整理課件A-Tree的結構整理課件多維索引方法的演變邊界形狀 MBRs（R-tree及其變種）MBSs(SS-Tree)MBRs and MBSs(SR-Tree)整理課件多維索引方法的演變樹結構（R-Tree SS-Tree SR-Tree等）中低維順序結構（線性掃描、

9、VA-File等) 高 維樹結構和順序結構的混合體（X-Tree)索引結構 整理課件多維索引方法的演變空間分割（K-D-B Tree grid file等)數據均勻分布數據分割（R-Tree SR-Tree X-Tree A-Tree等分割方法 整理課件多維索引方法的演變精確表示（R-Tree X-Tree 順序掃描等）近似表示（VA-File A-Tree)對象的表示方法 整理課件多維索引方法列表nK-D-B Trees（J T Robinson SIGMOD1981）nR-tree（A. Guttman SIGMOD1984）nR+-tree (T. Sellis VLDB1987)nLSD-Tree (A. Henrich VLDB1989)nR*-Tree（N. Beckmann SIGMOD1990）nTV-Tree (K. I. Lin VLDB1994） nSS-Tree (D. A. White ICDE1996 ) nVAMSplit R-Tree (D. A. White SPIE1996)nSR-Tree (N. Katayama SIGMOD1997) 整理課件多維索引方法列表nM-Tree (P.Ciaccia VLDB1997) nVA-File