关于空间索引的好书/文章

Question

我对有关空间索引的优秀文献感兴趣.哪一个正在使用中,它们在速度,空间要求,使用它们时的空间查询性能等方面进行了比较.

Answer 1

我曾经使用一种本土的QuadTree进行空间索引(在我学习" quadtree " 这个词之前).对于普通类型的空间数据(我处理街道地图数据),它们可以快速创建并快速查询,但它们在查询期间扫描太多叶节点.具体来说,使用合理的节点大小(50-100),我的四叉树倾向于为点查询生成大约300个结果,即应用3-6个叶子节点(非常粗略的球场;结果变化很大.)

如今,我首选的数据结构是R*树.我自己编写并测试了一个实现非常好的结果.与我的QuadTree代码相比,我构建R*树的代码非常慢,但叶节点上的边界框最终组织得很好; 至少有一半的查询空间仅由一个叶子节点回答(即如果你进行随机点查询,很有可能只返回一个叶子节点),并且90%的空间被覆盖了两个节点或更少.因此,如果节点大小为80个元素,我通常会从点查询中获得80或160个结果,平均值接近160(因为一些查询会返回3-5个节点).即使在地图密集的城市地区也是如此.

我知道这是因为我为我的R*树及其中的图形对象编写了一个可视化工具,并且我在一个大型数据集(600,000个路段)上测试了它.它在点数据(以及边界框很少重叠的其他数据)上表现更好.如果你实现一个R*树我敦促你想象结果,因为当我写我的时候它有多个错误降低了树的效率(不影响正确性),我能够调整一些决策到获得更好的结果.一定要测试一个大型数据集,因为它会揭示一个小数据集没有的问题.它可能有助于减少树的扇出(节点大小)以进行测试,以查看树在多层深度时的工作情况.

我很乐意给你源代码,除非我需要得到雇主的许可.你知道是怎么回事.在我的实现中,我支持强制重新插入,但我的PickSplit和插入惩罚已被调整.

原始论文,R*树:点和矩形的高效且稳健的访问方法,由于某种原因缺少点(没有句点和"i"上没有点).此外,他们的术语有点奇怪,例如,当他们说"边缘"时,他们的意思是"周长".

如果需要可修改的数据结构,R*树是一个不错的选择.如果在首次创建树之后不需要修改树,请考虑批量加载算法.如果你只需要在批量加载后少量修改树,普通的R-tree算法就足够了.注意,R*-tree和R-tree数据在结构上是相同的; 只有插入算法(也许删除？我忘了)是不同的.R-tree是1984年的原始数据结构; 这是R树纸的链接.

该kd树看起来效率并不算难实现,但它只能用于点数据.

顺便说一句,我如此关注叶子节点的原因是

1. 我需要处理基于磁盘的空间索引.您通常可以将所有内部节点缓存在内存中,因为它们只是索引大小的一小部分; 因此,与未缓存的叶节点所需的时间相比,扫描它们所花费的时间很少.
2. 我通过不为空间索引中的元素存储边界框来节省大量空间,这意味着我必须实际测试每个元素的原始几何以回答查询.因此,最小化触摸的叶节点的数量更为重要.