【作者】 梁俊杰； 杨泽新； 冯玉才；

【Author】 Liang Junjie~(1,2),Yang Zexin~1,and Feng Yucai~1 1(College of Computer Science & Technology,Huazhong University of Science and Technology,Wuhan 430074) 2(Faculty of Mathematics & Com puter Science,Hubei University,Wuhan 430062)

【机构】 华中科技大学计算机科学与技术学院； 湖北大学数学与计算机科学学院；

【摘要】 近几十年来,大规模高维数据库的应用越来越多,范围查询作为高维数据空间主要检索技术也面临越来越多的机遇和挑战.如何提高大规模高维数据的检索效率,学者提出了很多方法,金字塔技术是目前针对高维空间范围检索的有效方法之一,但是随着数据量的增加,检索过程可能引入过多的误中点而导致不必要的高维距离计算,为此提出改进的金字塔技术.利用向量排序和分段处理思想,首先将不包含候选点的误中分段剪枝;然后通过逐维距离累加法过滤剩余分段内的误中点,从而快速排除所有的误中点,减少距离计算次数,实现大规模高维数据的快速范围查询.利用模拟数据和真实数据,实验验证了OPT方法的正确性和有效性.更多还原

【Abstract】 During recent years,a variety of large high-dimensional data set applications have been developed in many respects.The range query is an important operation for mining high-dimensional data spaces,so that many methods for improving its performance are widely discussed in literature,such as pyramidtechnique (PT).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 poyramid 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 by using the definition of active dimension and accumulation order,which can filter out the false hits from a candidate sequence at 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 the experiments using both,synthetic and real data,demonstrate that the OPT outperforms PT for the range query in the large high-dimensional data space.更多还原