基于查询采样的高维数据混合索引  

High Dimensional Hybrid Index Based on Query Sampling

作　　者：张军旗[1] 周向东[2] 施伯乐[2] 

机构地区：[1]北京大学信息科学技术学院智能科学系 [2]复旦大学计算机与信息技术系,上海200433

出　　处：《软件学报》2008年第8期2054-2065,共12页Journal of Software

基　　金：国家自然科学基金No．60403018;国家重点基础研究发展计划(973)No．2005CB321905;上海市自然科学基金No．04ZR14011;AMD大学合作计划~~

摘　　要：为了改进高维数据库查询的效率,通常需要根据数据分布来选择合适的索引策略.然而,经典的分布模型难以解决实际应用中图像、视频等高维数据复杂的分布估计问题.提出一种基于查询采样进行数据分布估计的方法,并在此基础上提出了一种支持最近邻查询的混合索引,即针对多媒体数据分布的不均匀性,自适应地对不同分布的数据使用不同的索引结构,建立统一的索引结构.为了实现混合索引,采用构造性方法:首先通过聚类分解分割数据并建立树状索引;然后使用查询采样算法,对数据实际分布进行估计;最后根据数据分布的特性,把稀疏数据从树状索引中剪裁出来,进行基于顺序扫描策略的索引,而分布比较密集的数据仍然保留在树状索引中.在4个真实的图像数据集上进行了充分的实验,结果显示,该索引方法明显优于iDistance,M-Tree等度量空间索引,在维数达到336时,查询效率仍高于顺序扫描.实验结果显示,该查询采样算法在采样数据量仅为N^(1/2)(N为数据量)的情况下即可获得满足索引需要的分布估计结果.In order to improve the query answering of high-dimensional database, data distribution is necessary to select appropriate indexing strategy. However, traditional data distribution models can not estimate the accurate data distribution in the complex real multimedia data of image and video. This paper presents a method to estimate the accurate data distribution based on query sampling, and proposes a novel hybrid index to speed up processing of high-dimensional K-nearest neighbor （KNN） queries. The proposed hybrid index improves the query efficiency by adaptively selecting different index strategies for the data with different distribution. In the first step, the cluster analysis and cluster splitting methods are applied to construct a tree-based index, and then the relationship between data distribution and index performance is derived by sampling. At last some tree branches with sparse data are extracted for linear scan, while the aggregate data remains in the tree. Extensive experiments on four real image data sets show that the proposed hybrid index structure performs better than iDistance, M-Tree and linear scan, and scales better with dimensions. The index is still faster than linear scan when the dimension reaches 336. The experiments also show that the proposed query sampling algorithm can obtain the accurate data distribution when the amount of sampling is below √N （Nis the size of data set）.

关 键 词：最近邻查询 采样 高维索引 边缘数据 聚类分解 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]