一种在KNN查询处理中预估剪枝阈值的方法-《计算机技术与发展》

文章信息/Info

Title:: A Novel Method for Predicting Pruning Threshold in KNN Query Processing

Author(s):: LIU Can; ZHANG De-xian; School of Information Science and Engineering, Henan University of Technology

摘要:: KNN查询是多媒体数据库管理系统中最具代表性的查询方式之一。与范围查询不同，KNN查询过程中缺乏固定的剪枝阈值。为达到剪枝的目的KNN算法使用保守的KNN距离剪枝，通常把到当前访问过的第K个最近点的距离作为剪枝阈值。传统的KNN查询处理算法在找到K个候选查询结果之前无法生成剪枝阈值，使得在此期间所有访问到的节点都被置入待访问节点队列。文中提出了在KNN查询处理中预估剪枝阈值的方法，该方法在找到K个候选查询结果前通过分析当前所访问过的页区域来预估剪枝阈值，试验表明使用预估剪枝阈值进行剪枝可有效缩短待访问节点

Abstract:: KNN query is one of the most representative queries in multimedia database management system. Unlike range query processing, there is no fixed criterion to exclude branches of the indexing structure firm processing in KNN algorithms. To cut branches, KNN algorithms have to use conservative estimations of the KNN distance. A suitable estimation of the KNN distance is the K - th closest point among all points visited at the current state of execution. If there is not enough points have been visied yet, the pruning threshold will be infinited and allpoints visited will be inserted to the active node list, In this paper, a novel method for predicting pruning threshold in KNN query processing is proposed. In this method the pruning threshold is predicted from the page regions visited so far while there is not enough points have been visited. Experiments showed that the new algorithm can shorten the active node list