《多维数据索引方法综述杨凤召.ppt》由会员分享,可在线阅读,更多相关《多维数据索引方法综述杨凤召.ppt(30页珍藏版)》请在三一文库上搜索。
1、多维数据索引方法综述,杨 风 召,为什么要研究多维数据索引?,空间数据库 多媒体对象 图象、文本、视频等特征向量 相似性查询 数据挖掘 聚类、异常检测等 空间数据挖掘 多媒体数据挖掘 CAD、分子生物学等,传统的索引方法,哈希表 数值的精确匹配 不能进行范围查询 B-Trees ISAM 键值的一维排序 不能搜索多维空间,处理多维(multi-dimension)点数据的索引结构的比较,Cell 方法 K-d Trees Quad Trees K-D-B Trees(J T Robinson SIGMOD1981) Corner Stitching Grid files,处理多维(multi-
2、dimension)点数据的索引结构,处理矩形的方法,将矩形转变成更高维区间上的点(二维空间上的矩形可以看作四维空间上的点)。 用空间充填曲线(space filling curve)将k-d空间映射为1-d空间。这种方法适用于分页环境。它用z变换将k-d对象转变为线段 将原始空间划分为合适的子空间(重叠或分离的) 划分为分离子空间 用处理多维点的空间划分方法,只是若一个矩形被分到多个区域,可将该矩形分成几个部分,每一部分都加上标签,表示他们同属于一个矩形。 划分为有重叠子空间,R-tree(A. Guttman SIGMOD1984),R-tree的特点,R-tree是B-Tree对多维对象
3、(点和区域)的扩展 R-tree是一棵平衡树 一个多维对象只能被分到一个子空间中去 若用动态插入算法构建R-tree,在树的结点中会引起过多的空间重叠和死区(dead-space),使算法性能降低,R-tree的典型算法,查找 插入 选择叶子结点 分裂结点(有多种算法) 调整树 必要时增加树的高度 删除 找到包含要删除记录的叶子结点 删除 压缩树 必要时减小树的高度 更新 先删除老的记录索引,在插入新的记录索引,R+-tree (T. Sellis VLDB1987),R+-tree 的特点,R+-tree是K-D-B-tree对非0面积对象(不仅可以处理点,也可以处理矩形)的扩展 不需要覆盖
4、整个初始空间 R+-tree比R-tree表现出更好的搜索性能(特别对点的查询),但要占据较多的存储空间,R*-Tree(N. Beckmann SIGMOD1990),R*-Tree通过修改插入、分裂算法,并通过引入强制重插机制对R-Tree的性能进行改进。 R*-Tree和R-Tree一样允许矩形的重叠, R*-Tree在选择插入路径时同时考虑矩形的面积、空白区域和重叠的大小,而R-Tree只考虑面积的大小。,SS-Tree (D. A. White ICDE1996 ),SS-Tree的特点,SS-Tree对R*-Tree进行了改进,通过以下措施提高了最邻近查询的性能: 用最小边界园代替
5、最小边界矩形表示区域的形状; 增强了最邻近查询的性能; 减少将近一半的存储空间。 SS-Tree改进了R*-Tree的强制重插机制。,X-Tree (S. Berchtold VLDB1996),当维数增加到5时,R-Tree及其变种中的边界矩形的重叠将达到90%,因此在高维(high-dimension)情况(=5)下,其性能将变得很差,甚至不如顺序扫描。 X-Tree是线性数组和层状的R-Tree的杂合体,通过引入超级结点(supernode),大大地减少了最小边界矩形之间的重叠。提高了查询的效率。,X-Tree的结构,边界矩形和边界圆的比较,边界矩形的直径(对角线)比边界圆大, SS-T
6、ree将点分到小直径区域。由于区域的直径对最邻近查询性能的影响较大,因此SS-Tree的最邻近查询性能优于R*-Tree; 边界矩形的平均容积比边界圆小, R*-Tree将点分到小容积区域;由于大的容积会产生较多的覆盖,因此边界矩形在容积方面要优于边界圆。,SR-Tree (N. Katayama SIGMOD1997),SR-Tree的索引结构,SR-Tree的特点,既采用了最小边界圆(MBS),也采用了最小边界矩形(MBR)。 相对于SS-Tree,减小了区域的面积,提高了区域之间的分离性。 相对于R*-Tree,提高了最邻近查询的性能。,VA-File (R. Weber VLDB199
7、8),VA-File(Vector Approximation File)是一种简单但非常有效的方式,它将数据空间划分成2b单元(cell),b表示用户指定的二进制位数,每个单元分配一个位串。位于某个单元内的向量用这个单元近似代替。VA-File本身只是这些近似体的数组。查询时,先扫描VA-File,选择侯选向量,再访问向量文件进行验证。,VA-File的建立,A-Tree (Y. Sakurai VLDB2000),吸取SR-Tree和VA-File 的长处 引入虚拟边界矩形VBR(Virtual Bounding Rectangles),A-Tree的结构,多维索引方法的演变,边界形状,M
8、BRs (R-tree及其变种),MBSs (SS-Tree),MBRs and MBSs (SR-Tree),多维索引方法的演变,树结构 (R-Tree SS-Tree SR-Tree等),中低维,顺序结构 (线性扫描、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),对象
9、的表示方法,多维索引方法列表,K-D-B Trees(J T Robinson SIGMOD1981) R-tree(A. Guttman SIGMOD1984) R+-tree (T. Sellis VLDB1987) LSD-Tree (A. Henrich VLDB1989) R*-Tree(N. Beckmann SIGMOD1990) TV-Tree (K. I. Lin VLDB1994) SS-Tree (D. A. White ICDE1996 ) VAMSplit R-Tree (D. A. White SPIE1996) SR-Tree (N. Katayama SIGMOD1997),多维索引方法列表,M-Tree (P.Ciaccia VLDB1997) VA-File (R. Weber VLDB1998) Pyramid-Tree(S.Berchtold SIGMOD1998) hybrid-Tree(K.Chakrabarti ICDE1999) A-Tree (Y. Sakurai VLDB2000) IQ-Tree (S. Berchtold ICDE2000),
链接地址:https://www.31doc.com/p-3112794.html