我对有关空间索引的好文学感兴趣。哪些索引正在使用,它们在速度、空间需求、使用时的空间查询性能等方面的比较等。
我对有关空间索引的好文学感兴趣。哪些索引正在使用,它们在速度、空间需求、使用时的空间查询性能等方面的比较等。
我曾经使用一种自制的四叉树进行空间索引(在我学到 "quadtree" 这个词之前)。对于普通的空间数据(我处理街道地图数据),它们创建和查询速度很快,但是在查询过程中会扫描太多的叶节点。具体来说,对于合理的节点大小(50-100),我的四叉树 tend to 为点查询产生大约300个结果,即应用3-6个叶节点(非常粗略的估计;结果高度可变)。
现在,我偏爱的数据结构是 R*树。我自己编写并测试了一种实现方式,效果非常好。相比于我的四叉树代码,我的R*树构建代码非常慢,但是叶子节点上的边界框最终会被很好地组织起来;至少有一半的查询空间只有一个叶子节点来回答(即如果进行随机点查询,则很有可能只返回单个叶子节点),而大约90%的空间只被两个或更少的节点覆盖。因此,使用80个元素的节点大小,我通常会从点查询中获得80或160个结果,平均值更接近160(因为一些查询确实会返回3-5个节点)。这在地图的密集城市区域也适用。kd-tree 看起来高效而且实现并不太困难,但它只能用于点数据。
顺便说一下,我非常关注叶节点的原因是
我几年前开发了一种基于象限的快速搜索算法,并在ddj.com上发布了它。也许对你有兴趣:
加速搜索最近的线 http://drdobbs.com/windows/198900559