计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (30): 157-160.DOI: 10.3778/j.issn.1002-8331.2009.30.048

• 数据库、信号与信息处理 • 上一篇    下一篇

CKDB-Tree:一种有效的高维动态索引结构

孙劲光,王淑娥   

  1. 辽宁工程技术大学 电子与信息工程学院,辽宁 葫芦岛 125105
  • 收稿日期:2008-06-03 修回日期:2008-09-16 出版日期:2009-10-21 发布日期:2009-10-21
  • 通讯作者: 孙劲光

CKDB-Tree:Effective index structure in high-dimensional data spaces

SUN Jin-guang,WANG Shu-e   

  1. School of Electronic and Information,Liaoning Technical University,Huludao,Liaoning 125105,China
  • Received:2008-06-03 Revised:2008-09-16 Online:2009-10-21 Published:2009-10-21
  • Contact: SUN Jin-guang

摘要: 在高维数据空间中提出了一种新的索引结构:CKDB-Tree(Compact KDB-Tree),该索引结构采用一种新的分裂策略,在进行分裂时,引入插入安全点和删除安全点的概念,不仅考虑到将来的数据,而且对已经进行索引的数据也进行考虑;给出了CKDB-Tree的定义以及节点结构的特点,针对CKDB-Tree,给出了相应的插入、查找、删除操作的算法;对该索引结构的存储性能进行定量分析和推理;最后经实验证明,CKDB-Tree是高维空间中一种有效的动态索引结构。

关键词: 高维数据空间, 压缩KDB树, 分裂策略, 动态索引结构

Abstract: An effective index structure is proposed for high-dimensional data spaces:CKDB-Tree(Compact KDB-Tree).The index structure uses one kind of new partitioning strategy.During the insert processing,this paper introduces the safe-inserted-node and safe-deleted node concept into the structure,which is not only considering the current node,but also considering the future node.This paper gives the definition of the CKDB-Tree and the character of the node;it also gives the algorithm of the insert,the search and the delete operation;then gives the analysis and the inference to the index structure’s memory property;finally,the experiment proves that CKDB-Tree is one kind of effective dynamic index structure in the high-dimensional spaces.

Key words: high-dimensional data space, Compact KDB-Tree, splitting policy, dynamic index structure

中图分类号: