Abstract: An effective index structure was 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 invalid in low-dimensional spaces are usually invalid in high-dimensional spaces. In the process of spatial division, the γ division strategy was used to carry out the data compression. It reduced the index structure, and overcame the pyramid technologys shortcomings. The construction method and inquiry algorithm of pyramid tree were given. The experiments prove that compact pyramid technology is an effective spatial division strategy, and has good performance in highdimensional skew space.

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

摘要： 提出了一种压缩金字塔树，将d维数据空间划分为2d个金字塔，由于在低维空间中无效的信息在高维数据空间中往往无效，采用γ划分策略对低维空间中的数据进行压缩，减小索引结构，克服了金字塔技术的缺点。给出了压缩金字塔树的构造方法以及基于压缩金字塔树的查询算法。实验证明，压缩金字塔树是一种有效的空间划分策略，在高维稀疏空间有良好的性能。

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