期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

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

Core Algorithm of High-dimensional Main Memory kNN-Join Index Structure
在线阅读 下载PDF
导出
摘要 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.
作者 刘艳 郝忠孝
机构地区 哈尔滨理工大学计算机科学与技术学院 长春大学计算机科学技术学院 哈尔滨工业大学计算机科学与技术学院
出处 《计算机科学》 CSCD 北大核心 2011年第9期146-149,共4页 Computer Science
基金 黑龙江省自然科学基金(F200601)资助
关键词 kNN连接 高维空间 主存 索引结构 kNN搜索 kNN-Join High-dimensional space Main-memory Index structure kNN search
分类号 TP311.13 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献10

  • 1Bohm C, Krebs F. The k-nearest neighbor join: turbo charging the kdd process [J ]. Knowledge and Information Systems (KAIS), 2004,6 (6) :728-749.
  • 2Xia C,Lu J, Ooi B C, et al. GORDER: An efficient method for KNN join processing[C]//Proceedings of the 30th International Conference on Very Large Data Bases(VLDB'04). San Francisco, CA: Morgan Kaufmann, 2004 : 756-767.
  • 3Cui Y, Cui B, Wang S, et al. Efficient index-based KNN join processing for high-dimensional data[J]. Information and Software Technology, 2007,49 (4) : 332-344.
  • 4何洪辉,王丽珍,周丽华.pgi-distance:一种高效的并行KNN-join处理方法[J].计算机研究与发展,2007,44(10):1774-1781. 被引量：3
  • 5梁俊杰,冯玉才.LBD:基于局部位码比较的高维空间KNN搜索算法[J].计算机科学,2007,34(6):145-148. 被引量：3
  • 6Emrich T, Graf F, Kriegel H-P, et al. Optimizing All-Nearest- Neighbor Queries with Trigonometric Pruning[C]///Proceedings of the 22nd International Conference on Scientific and Statistical Database Management (SSDBM). Heidelberg, Germany: Springer, 2010 : 501-518.
  • 7Wang J J, Lin L, Huang T, et al. Effcient K-Nearest Neighbor Join Algorithms for High Dimensional Sparse Data. Computing Research Repository(CoRR)[R]. cs. DB/1011.2807. 2010-11.
  • 8Yu C, Zhang R, Huang Y, et al. High-dimensional k NN Joins with Incremental Updates[J]. GeoInformatica, 2010,14 ( 1 ):55- 82.
  • 9刘艳,郝忠孝.一种基于主存Δ-tree的高维数据KNN连接算法[J].计算机研究与发展,2010,47(7):1234-1243. 被引量：7
  • 10Cui B, Ooi B C, Su J W, et al. Indexing high-dimensional data for efficient in-memory similarity search[J]. IEEE Trans on Knowledge and Data Engineering, 2005,17 (3) : 339-353.

二级参考文献37

  • 1董道国,梁刘红,薛向阳.VAR-Tree——一种新的高维数据索引结构[J].计算机研究与发展,2005,42(1):10-17. 被引量：9
  • 2Bohm C,Krebs F.The k-nearest neighbor join:Turbo charging the kdd process[J].Knowledge and Information Systems (KAIS).Berlin:Springer,2004,6(6):728-749.
  • 3Bohm C,Krebs F.Supporting kdd applications by the k-nearest neighbor join[G] //LNCS 2736:Proc of the 14th Int Conf on Database and Expert Systems Applications (DEXA).Berlin:Springer,2003:504-516.
  • 4Xia C,Lu J,Ooi B C,et al.GORDER:An efficient method for KNN join processing[C] //Proc of the 30th Int Conf on Very Large Data Bases(VLDB04).San Francisco,CA:Morgan Kaufmann,2004:756-767.
  • 5Cui Y,Cui B,Wang S,et al.Efficient index-based KNN join processing for high-dimensional data[J].Information and Software Technology.2007,49(4):332-344.
  • 6Cui B,Ooi B C,Su J W,et al.Indexing high-dimensional data for efficient in-memory similarity search[J].IEEE Trans on Knowledge and Data Engineering,2005,17(3):339-353.
  • 7Cui B,Ooi B C,Su J W,et al.Contorting high dimensional data for efficient main memory processing[C] //Proc of the ACM SIGMOD Int Conf on Management of Data.New York:ACM,2003:479-490.
  • 8Jolliffe I T.Principal Component Analysis[M].Berlin:Springer,1986.
  • 9Bohm C.A cost model for query processing in high dimensional data spaces[J].ACM Trans on Database Systems,2000,25(2):129-178.
  • 10Jin H,Ooi B C,Shen H T,et al.An adaptive and efficient dimensionality reduction algorithm for high-dimensional indexing[C] //Proc of the 19th Int Conf on Data Engineering.Los Alamitos,CA:IEEE Computer Society,2003:87-98.

共引文献10

计算机科学
2011年 第9期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部