深度优先遍历Δ-tree的非递归KNN查询

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (15): 6-8.

深度优先遍历Δ-tree的非递归KNN查询

刘艳1，2，郝忠孝1，3

1.哈尔滨理工大学计算机科学与技术学院，哈尔滨 150080
2.长春大学软件学院，长春 130022
3.哈尔滨工业大学计算机科学与技术学院，哈尔滨 150001

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-21 发布日期:2011-05-21

Non-recursive KNN search using depth-first traversal of Δ-tree

LIU Yan1，2，HAO Zhongxiao1，3

1.College of Computer Science and Technology，Harbin University of Science and Technology，Harbin 150080，China
2.Institute of Software，Changchun University，Changchun 130022，China
3.College of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-05-21 Published:2011-05-21

摘要/Abstract

摘要： kNN查询是高维数据库中最重要的操作之一，尽管它在数据库研究中得到了极大的关注，但很少有关于主存数据库kNN查询的工作。充分利用kNN查询自身的特点，基于高效的主存索引Δ-tree设计了一种新的kNN查询算法NR_DF_knn_Search，该算法采用非递归方式深度优先搜索Δ-tree中距离查询点较近的叶子节点，能够快速找到较优的kNN候选，更新修剪距离，加大剪枝力度，缩小搜索空间，从而提高kNN查询效率。通过实验对该算法进行了估价，结果证明该算法是有效的。

关键词: 高维索引, 主存kNN查询, 非递归, 最近邻查询, 深度优先搜索

Abstract: k Nearest Neighbor（kNN） search is one of the most important operations in high databases.Although it has received considerable attention in the database literature，there is little prior work on kNN retrieval in main-memory databases.Fully utilizing its own characteristics of kNN query，a new kNN search algorithm is proposed，called NR_DF_knn_Search，for efficient main memory index Δ-tree.This algorithm searches the leaf nodes of Δ-tree that nearer the query point by non-recursive depth first manner，can quickly find near optimal kNN candidates，update pruning distance，increase prune force，narrow the search space，so it improves kNN query efficiency.Extensive experiments are conducted to evaluate the NR_DF_knn_Search algorithm，and report results demonstrate its effectiveness.

Key words: high-dimensional index, main-memory kNN search, non-recursive, Nearest Neighbor（NN） search, depth-first search

刘艳1，2，郝忠孝1，3. 深度优先遍历Δ-tree的非递归KNN查询[J]. 计算机工程与应用, 2011, 47(15): 6-8.

LIU Yan1，2，HAO Zhongxiao1，3. Non-recursive KNN search using depth-first traversal of Δ-tree[J]. Computer Engineering and Applications, 2011, 47(15): 6-8.

[1]	钟德云，王李管，毕林，王晋淼. 复杂风网井下循环风快速搜索算法[J]. 计算机工程与应用, 2017, 53(8): 235-239.
[2]	姚博1，冯宏伟1，高原2，马佳丽1，冯筠1. 过必经节点集的动态剪枝搜索算法[J]. 计算机工程与应用, 2017, 53(15): 57-62.
[3]	张辰，李红军，罗柳红，何英豪. 等价关系矩阵的置换合同性质与标准形计算[J]. 计算机工程与应用, 2017, 53(13): 42-48.
[4]	周乐乐1，2，3，郑烇1，2，3，王嵩1，杨坚1，杨志伟1，2，3. 基于小世界模型的高维索引更新维护算法研究[J]. 计算机工程与应用, 2016, 52(11): 77-83.
[5]	桂舒婷，郑烇，周乐乐，刘欣，王嵩. 基于小世界模型的高维索引算法[J]. 计算机工程与应用, 2015, 51(16): 136-141.
[6]	张丽平1，李松1，郝晓红2，郝忠孝1. 障碍物增减情况下的单纯型连续近邻链查询[J]. 计算机工程与应用, 2015, 51(11): 99-103.
[7]	刘润涛1，陈琳琳2，田广悦2. Z曲线网格划分的最近邻查询[J]. 计算机工程与应用, 2013, 49(22): 123-126.
[8]	王龙飞，陈红，李杨，邓亚娟. 城市路网车辆出行轨迹获取的混合轨迹拆分[J]. 计算机工程与应用, 2013, 49(21): 1-5.
[9]	王丹丹1，郝忠孝1，2. 道路网络中的多类型K最近邻查询[J]. 计算机工程与应用, 2012, 48(3): 140-142.
[10]	邱永红1，2，曾永年2，邹滨2. 快速选择的循环迭代实现算法[J]. 计算机工程与应用, 2012, 48(29): 13-15.
[11]	章德斌¹，曹丽君²，梁永欣¹，张忠平¹. 支持k近邻查询的X*树索引结构[J]. 计算机工程与应用, 2011, 47(5): 123-125.
[12]	李进，余建桥. 空间对象的反最近邻查询处理技术研究[J]. 计算机工程与应用, 2011, 47(33): 146-148.
[13]	曹泽文，谭川豫，王晓辉. 移动对象反向最近邻查询处理技术研究进展[J]. 计算机工程与应用, 2011, 47(10): 138-141.
[14]	孙冬璞¹，郝忠孝^1，2. 时空数据库变体最近邻查询问题探讨[J]. 计算机工程与应用, 2010, 46(14): 12-16.
[15]	董军,杨秀娟. 移动对象的动态反向k最近邻研究[J]. 计算机工程与应用, 2009, 45(6): 155-157.