空间索引的好书/文章

Question

我对有关空间索引的好文学感兴趣。哪些索引正在使用，它们在速度、空间需求、使用时的空间查询性能等方面的比较等。

- watbywbarif

Answer 1

我曾经使用一种自制的四叉树进行空间索引（在我学到 "quadtree" 这个词之前）。对于普通的空间数据（我处理街道地图数据），它们创建和查询速度很快，但是在查询过程中会扫描太多的叶节点。具体来说，对于合理的节点大小（50-100），我的四叉树 tend to 为点查询产生大约300个结果，即应用3-6个叶节点（非常粗略的估计；结果高度可变）。

现在，我偏爱的数据结构是 R*树。我自己编写并测试了一种实现方式，效果非常好。相比于我的四叉树代码，我的R*树构建代码非常慢，但是叶子节点上的边界框最终会被很好地组织起来；至少有一半的查询空间只有一个叶子节点来回答（即如果进行随机点查询，则很有可能只返回单个叶子节点），而大约90%的空间只被两个或更少的节点覆盖。因此，使用80个元素的节点大小，我通常会从点查询中获得80或160个结果，平均值更接近160（因为一些查询确实会返回3-5个节点）。这在地图的密集城市区域也适用。

我知道这是因为我为我的R*树及其中的图形对象编写了一个可视化程序，并在大型数据集（600,000个道路段）上进行了测试。它在点数据（以及边界框很少重叠的其他数据）上的表现甚至更好。如果您实现了R*树，我建议您可视化结果，因为当我编写我的程序时，它有多个错误降低了树的效率（但不影响正确性），我能够调整一些决策以获得更好的结果。请务必在大型数据集上进行测试，因为它将显示小型数据集无法显示的问题。为了测试时能够查看树的深度，可以尝试减小树的扇出（节点大小）。

我很乐意给您源代码，但我需要得到雇主的许可。你知道怎么回事。在我的实现中，我支持强制重新插入，但我的PickSplit和插入惩罚已经进行了调整。

原始论文The R* tree: An Efficient and Robust Access Method for Points and Rectangles中缺少一些标点符号（没有句号，字母“i”上也没有点）。此外，他们的术语有些奇怪，例如当他们说“margin”时，实际上是指“perimeter”。

如果需要修改数据结构，则R*树是一个不错的选择。如果创建后不需要修改树，则可以考虑bulk loading algorithms。如果仅需要在批量加载后轻微修改树，则普通的R树算法就足够了。请注意，R*树和R树数据在结构上是相同的；只有插入算法（也许还有删除？我忘了）不同。R树是1984年的原始数据结构；这是R-tree paper的链接。

kd-tree 看起来高效而且实现并不太困难，但它只能用于点数据。

顺便说一下，我非常关注叶节点的原因是

1. 我需要处理基于磁盘的空间索引。通常可以将所有内部节点缓存到内存中，因为它们只占索引大小的一小部分；因此扫描它们所需的时间与未缓存的叶节点相比微不足道。
2. 通过不为空间索引中的元素存储边界框，我节省了很多空间，这意味着我必须测试每个元素的原始几何形状才能回答查询。因此，最大限度地减少触及的叶节点数量更加重要。

- Qwertie

Answer 2

我几年前开发了一种基于象限的快速搜索算法，并在ddj.com上发布了它。也许对你有兴趣：

加速搜索最近的线 http://drdobbs.com/windows/198900559

- RED SOFT ADAIR