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

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

对高维主存的反向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.