摘要： 对高维主存的反向K最近邻(KNN)查询进行研究，提出一种Δ-RdKNN-tree索引结构。通过在该索引结构上进行主存KNN自连接，预处理数据集中点的KNN距离信息。将这些距离扩展到索引的各层节点中，基于该索引设计高维主存的反向KNN查询算法以及反向KNN连接算法。分析结果表明，该算法在高维空间中是有效的。

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

Abstract: 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 Δ-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.

Key words: high-dimensional, main-memory, Reverse K Nearest Neighbor(RKNN) query, Reverse K Nearest Neighbor(RKNN) join, preprocess- ing

中图分类号: 

• TP311.13