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

Core Algorithm of High-dimensional Main Memory kNN-Join Index Structure

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

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

出　　处：《计算机科学》2011年第9期146-149,共4页Computer Science

基　　金：黑龙江省自然科学基金(F200601)资助

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

关 键 词：kNN连接 高维空间 主存 索引结构 kNN搜索 

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