首页 | 本学科首页   官方微博 | 高级检索  
     

基于查询采样的高维数据混合索引
引用本文:张军旗,周向东,施伯乐.基于查询采样的高维数据混合索引[J].软件学报,2008,19(8):2054-2065.
作者姓名:张军旗  周向东  施伯乐
作者单位:复旦大学,计算机与信息技术系,上海,200433
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60403018 (国家自然科学基金); the National Basic Research Program of China under Grant No.2005CB321905 (国家重点基础研究发展计划(973)); the Natural Science Foundation of Shanghai of China under Grant No.04ZR14011 (上海市自然科学基金); the College Cooperation Plan of AMD (AMD大学合作计划)
摘    要:为了改进高维数据库查询的效率,通常需要根据数据分布来选择合适的索引策略.然而,经典的分布模型难以解决实际应用中图像、视频等高维数据复杂的分布估计问题.提出一种基于查询采样进行数据分布估计的方法,并在此基础上提出了一种支持最近邻查询的混合索引,即针对多媒体数据分布的不均匀性,自适应地对不同分布的数据使用不同的索引结构,建立统一的索引结构.为了实现混合索引,采用构造性方法:首先通过聚类分解分割数据并建立树状索引;然后使用查询采样算法,对数据实际分布进行估计;最后根据数据分布的特性,把稀疏数据从树状索引中剪裁出来,进行基于顺序扫描策略的索引,而分布比较密集的数据仍然保留在树状索引中.在4个真实的图像数据集上进行了充分的实验,结果显示,该索引方法明显优于iDistance,M-Tree等度量空间索引,在维数达到336时,查询效率仍高于顺序扫描.实验结果显示,该查询采样算法在采样数据量仅为N~(1/2)(N为数据量)的情况下即可获得满足索引需要的分布估计结果.

关 键 词:最近邻查询  采样  高维索引  边缘数据  聚类分解
收稿时间:2007/3/26 0:00:00
修稿时间:8/3/2007 12:00:00 AM

High Dimensional Hybrid Index Based on Query Sampling
ZHANG Jun-Qi,ZHOU Xiang-Dong and SHI Bai-Le.High Dimensional Hybrid Index Based on Query Sampling[J].Journal of Software,2008,19(8):2054-2065.
Authors:ZHANG Jun-Qi  ZHOU Xiang-Dong and SHI Bai-Le
Abstract: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~(1/2)(N is the size of data set).
Keywords:nearest neighbor query  high dimensional index  marginal data  cluster partitioning
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号