Analysis of the Clustering Properties of the Hilbert Space-Filling Curve 论文笔记

 

• 摘要

　　已经针对各种应用提出了用于多维空间的线性映射的若干方案，诸如用于时空数据库的访问方法和图像压缩。在这些应用中，来自这种线性映射的最期望的属性之一是聚类，这意味着多维空间中的对象之间的局部性被保留在线性空间中。人们普遍认为希尔伯特空间填充曲线可以实现最佳聚类[1]，[14]。在本文中，我们通过导出任意形状（例如，多边形和多面体）的给定查询区域中的聚类数的闭式公式来分析希尔伯特空间填充曲线的聚类特性。一般情况的渐近解和特殊情况的精确解都推广了以前的工作[14]。他们同意经验结果，即簇的数量取决于查询区域的超曲面区域而不是其超体积。我们还表明，希尔伯特曲线比z曲线实现更好的聚类。从实际的角度来看，本文中给出的公式提供了一个简单的度量，可用于预测所需的磁盘访问行为，从而预测总访问时间。

• 简介

　　与一维情况相比，多维访问方法的设计是困难的，因为没有保留空间局部性的总排序。 一旦找到给定空间或多维数据库的总排序，就可以使用任何一维访问方法（例如，B⁺ -tree），这可以为多维查询产生良好的性能。 在Orenstein [19]提出的多维索引技术中出现了有序的排序应用。 我们的想法是在多维空间中为每个点在一维空间上开发单个数字索引，这样，对于任何给定对象，从最小索引到最大索引的索引范围包括不在对象本身中的几个点。

　　考虑数据库的线性遍历或典型范围查询，其中记录签名使用多属性散列[24]映射到存储在磁盘上的存储桶。线性遍历指定从磁盘获取对象的顺序，以及获取的块数。非连续磁盘访问的数量将由获取的块的顺序确定。尽管在范围查询中没有明确指定所获取的块的顺序，但是可以合理地假设所获取的块集可以由数据库服务器或磁盘控制器机制重新排列为多个连续块组[25]。由于为了减少额外的搜索时间而获取一组连续的磁盘块而不是随机分散的集合更有效，因此希望在多维属性空间中靠近在一起的对象也在一维磁盘空间中靠近在一起。在磁盘块的一维维序列上对多维数据点进行良好聚类还可以减少范围查询所需的磁盘访问次数。

　　除了上述应用程序之外，其他几个应用程序也可以从保留局部性的线性映射中受益：

1. 在传统数据库中，必须将多属性数据空间映射到一维磁盘空间，以便有效处理部分匹配查询[22]; 在数值分析中，大型多维数组[6]必须存储在磁盘上，这是一种线性结构。
2. 在图像压缩中，一系列方法使用线性映射将图像转换为位串; 随后，可以应用任何标准压缩方法[18]。 良好的像素聚类将导致较少数量的相似像素值的长行程，从而提高压缩比。
3. 在地理信息系统（GIS）中，运行编码形式的图像表示是排序敏感的，因为它们基于图像的表示作为运行集[1]。
4. 计算几何问题中的启发式算法使用线性映射。 例如，对于旅行商问题，城市是线性排序并相应地访问[2]。
5. 保持位置的映射用于数字采样信号[4]的带宽减少和图形显示生成[20]。
6. 在科学并行处理中，局部保持线性化技术被广泛用于动态非结构化网格划分[17]。

 　　在文献中已经提出了复杂的映射函数。 提出了一种基于来自坐标的交错比特，称为z排序[19]。 它的改进是由Faloutsos [8]提出的，在交错比特上使用格雷编码。 第三种方法，基于希尔伯特曲线[13]，被提出用于二次密钥检索[11]。 在数学上下文中，这三个映射函数分别基于不同的空间填充曲线：z曲线，格雷编码曲线和希尔伯特曲线。 图1示出了由4X4网格的空间填充曲线产生的线性排序。

结果表明，在大多数情况下，基于希尔伯特空间填充曲线的线性映射在保持局部性方面优于其他曲线[14]。 在本文中，我们提供了希尔伯特空间填充曲线的聚类效应的分析结果，侧重于任意形状的范围查询，这需要在多维空间中检索给定超矩形或多面体内的所有对象。

　　出于分析的目的，我们假设具有有限粒度的多维空间，其中每个点对应于网格单元。希尔伯特空间填充曲线对网格单元施加线性排序，为每个单元分配单个整数值。理想情况下，希望具有导致更少磁盘访问的映射。但是，磁盘访问次数取决于几个因素，例如磁盘页面的容量，拆分算法，插入顺序等。这里，我们使用网格点的平均簇数或连续运行数，表示查询区域的子空间，作为希尔伯特曲线的聚类性能的度量。如果每个网格点映射到一个磁盘块，则此度量与非连续磁盘访问的数量完全对应，这涉及额外的查找时间。该度量也与访问的磁盘块的数量高度相关，因为（在磁盘块中有许多网格点）连续点可能在同一块中，而不连续点上的点可能在不同的块中。该测量仅用于使分析易于处理，并且在[14]中讨论了该测量的一些弱点。