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

【Abstract】 kNN-Join is an important but costly primitive operation of high-dimensional databases.As RAM gets cheaper and larger,more and more datasets can fit into the main memory,how to realize the kNN-Join efficiently brings people’s interests.Δ-tree-R and Δ-tree-S were designed especially for main-memory kNN-Join according to the properties of it.The core algorithms and relevant certificates of building them were presented combining with coding and node center coincidence technologies.Experiments show that the algorithmΔ-tree-kNN-Join based on Δ-tree-R and Δ-tree-S is superior to the existing kNN-Join algorithm of Gorder that can be used in main memory.更多还原