高维主存的反向K最近邻查询及连接  

High-dimensional Main-memory Reverse K Nearest Neighbor Query and Join

作　　者：刘艳[1,2] 郝忠孝[1,3] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]长春大学计算机科学技术学院,长春130022 [3]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机工程》2011年第24期22-24,共3页Computer Engineering

基　　金：黑龙江省自然科学基金资助项目(F2006-01)

摘　　要：对高维主存的反向K最近邻(KNN)查询进行研究,提出一种△-RdKNN-tree索引结构。通过在该索引结构上进行主存KNN自连接,预处理数据集中点的KNN距离信息。将这些距离扩展到索引的各层节点中,基于该索引设计高维主存的反向KNN查询算法以及反向KNN连接算法。分析结果表明,该算法在高维空间中是有效的。The Reverse K Nearest Neighbor（RKNN） problem is a generalization of the reverse nearest neighbor problem which receives increasing attention recently, but high-dimensional RKNN problem is little explored. This paper studies on the high-dimensional main-memory RKNN queries, proposes an indexing structure called A-RdKNN-tree, precomputes KNN distances of points in the dataset by main-memory KNN self-join based on this index and propagates these distances to higher level index nodes. Main-memory RKNN query algorithm based on this index is proposed and main-memory RKNN join algorithm is given for set-oriented RKNN queries. Analysis shows that the two algorithms are effective in high dimension space.

关 键 词：高维 主存 反向K最近邻查询 反向K最近邻连接 预处理 

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