一种基于主存Δ-tree的高维数据KNN连接算法

作     者：刘艳 郝忠孝 Liu Yan;Hao Zhongxiao

作者机构：哈尔滨理工大学计算机科学与技术学院哈尔滨150080 长春大学软件学院长春130022 哈尔滨工业大学计算机科学与技术学院哈尔滨150001 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2010年第47卷第7期

页      面：1234-1243页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

基　　金：黑龙江省自然科学基金项目(F200601) 

主　　题：相似连接 KNN连接 高维空间 主存 数据挖掘 

摘      要：KNN连接作为数据挖掘的基元,可以用来大幅度提高相似搜索、数据分析和数据挖掘的速度.到目前为止,对KNN连接的研究主要在基于磁盘系统的背景下进行,假设数据库太大以至于不能装入主存.随着RAM越来越大,价格也越来越低廉,这种假设逐渐受到挑战.因此,有必要重新对基于主存的KNN连接进行研究.在高效主存索引的基础上,采用编码解码、自底向上、深度优先遍历和剪枝等技术提出了一种新的KNN连接算法Δ-tree-KNN-Join.该算法解决了KNN连接中确定搜索半径困难的问题,提高了连接效率.在真实数据和合成聚类数据上进行了实验,结果显示Δ-tree-KNN-Join是一种有效的主存KNN连接算法.