高维主存knn连接索引结构的核心算法

knn(k最近邻)连接是高维数据库中的一种重要但代价昂贵的基本操作。随着ram容量越来越大且价格逐渐低廉，更多的数据集能够被装入主存。如何实现快速主存knn连接，引起人们的关注。索引p-tree-r和p-tree-s是根据knn连接的特点专门为主存knn连接设计的索引。结合编码、节点中心重合技术，给出了构建p-trc}r和p-tree-s的核心算法及相关证明，实验表明，基于该索引的主存knn连接算法p-tree-knn-join明显优于目前已存在的可用于主存的knn连接算法gordcro