大规模高维向量空间的快速范围查询  

Fast Range Query in Large High-dimensional Spaces

作　　者：梁俊杰[1] 杨泽新[1] 冯玉才[1] 

机构地区：[1]华中科技大学计算机科学与技术学院

出　　处：《小型微型计算机系统》2007年第7期1225-1229,共5页Journal of Chinese Computer Systems

基　　金：国家"八六三"电子信息产业发展基金([2005]555)资助.

摘　　要：金字塔技术是目前针对高维空间范围查询的有效方法之一,但是随着数据量的增加,检索过程由于引入过多的误中点而导致不必要的高维距离计算,为此本文提出改进的金字塔技术.引入向量排序、活性维等概念,利用分段处理思想,将不包含候选点的误中分段剪枝,并通过逐维距离累加法过滤剩余分段内的误中点,从而快速排除所有的误中点,尽可能减少距离计算次数,实现大规模高维向量空间的快速范围查询.利用模拟数据和真实数据,实验验证了OPT方法的正确性和有效性.The PT is one of the efficient approaches to the range query, performing well with the increase of dimensionality. However, with the number of the points increasing in the data space, the retrieval performance of the PT degrades dramatically because the cost of distance computation with high dimensions increases greatly with many false hit points brought in the process of the range query. Motivated by the drawbacks of the PT, an Optimized Pyramid Technique （OPT） is proposed to reduce the number of the expensive distance computations, which has three crucial properties. First, it introduces a new definition of vector order, on the basis of which some high dimensional points can be ordered. Second, an adaptable algorithm is presented for dividing an ordered sequence, if needed, into a set of sequences with some benefits. Thereby, those points formed of the false hit points can be pruned in a sequence way, with the candidate sequences remained. Third, a modest algorithm is proposed, which can filter out the false hits from a candidate sequence in a rapid speed. Consequently, the OPT can exclude all the false hits from distance computation as rapidly as possible, thus leading to a fast range query. The results of our experiments using both, synthetic and real data, demonstrate that the OPT outperforms PT for the range query in the large high-dimensional data space.

关 键 词：大规模高维向量空间 范围查询 误中点 向量排序 活性维 

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