计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (22): 114-116.DOI: 10.3778/j.issn.1002-8331.2009.22.037

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

压缩金字塔树:有效的高维数据索引结构

孙劲光1,王淑娥1,陈 虹2   

  1. 1.辽宁工程技术大学 电子与信息工程学院,辽宁 葫芦岛 125105
    2.辽宁工程技术大学 软件学院,辽宁 葫芦岛 125105
  • 收稿日期:2008-04-28 修回日期:2008-07-21 出版日期:2009-08-01 发布日期:2009-08-01
  • 通讯作者: 孙劲光

Compact pyramid tree:Effective index structure in high-dimensional data spaces

SUN Jin-guang1,WANG Shu-e1,CHEN Hong2   

  1. 1.School of Electronic and Information,Liaoning Technical University,Huludao,Liaoning 125105,China
    2.School of Software,Liaoning Technical University,Huludao,Liaoning 125105,China

  • Received:2008-04-28 Revised:2008-07-21 Online:2009-08-01 Published:2009-08-01
  • Contact: SUN Jin-guang

摘要: 提出了一种压缩金字塔树,基本思想是,首先将d维数据空间划分为2d个金字塔,由于在低维空间中无效的信息在高维数据空间中往往无效,采用γ划分策略对低维空间中的数据进行压缩,减小索引结构,解决了金字塔技术的缺点,给出了压缩金字塔树的插入、查询、删除算法。最后经实验证明,压缩金字塔树是一种有效的空间划分策略,在高维稀疏空间有良好的性能。

关键词: 压缩金字塔树, 高维数据空间, γ划分策略, 索引结构, 金字塔技术

Abstract: An effective index structure is proposed for high-dimensional data spaces:Compact pyramid tree.The basic idea is to divide the data space first into 2d pyramids sharing the center point of the space as a top.Its basic philosophy is:the data which is invalid in low-dimensional spaces are usually invalid in high-dimensional spaces.In the spatial division’s process,use the γ division strategy to carry on the compression to the data,which will reduce the index structure.It solves the pyramid technology’s shortcoming,and gives the compact pyramid technology with insert,inquiry and delete algorithm,finally the experiment proves that compact pyramid technology is one kind of effective spatial division strategy,it has the good performance in the high-dimensional skew space.

Key words: compact pyramid tree, high-dimensional data space, γ splitting strategy, indexing structure, pyramid technique