data-structures - R-Tree 中的最近邻算法

Question

我正在阅读 Guttman 的论文 Link to paper/book

我想知道最近邻查询如何与 R-Trees 一起工作，或者它是如何实际实现的。我想到的是，您从根开始遍历树并检查其中一个条目是否包含查询点。

所以第一个问题是，如果一个矩形包括查询点，这并不意味着这个矩形内的所有矩形都会自动成为离查询点最近的矩形。即使查询点不在矩形内，也可能存在另一个距离较小的矩形？

其次，假设查询点实际上是一个最小边界框，例如 mbr = [left,bottom, right, top] 并且我想要与该区域重叠的所有矩形或更好的所有矩形它的质心位于给定区域内。这也可以吗？

Answer 1

编辑

做了很多实验，算法由

Hjaltason、Gísli R. 和 Hanan Samet。 “空间数据库中的远程浏览。” ACM 数据库系统事务 (TODS) 24.2 (1999):265-318。

(正如@Anony-Mousse 在答案中所发布的)显然优于我在这里描述的算法。

旧答案:

据我所知，最好的 kNN 搜索算法是 by

Cheung、King Lum 和 Ada Wai-Chee Fu。 “增强 R 树上的最近邻搜索。” ACM SIGMOD 记录 27.3 (1998):16-21。 (复制自@Anony-Mousse 的回答)PDF download

基本算法在this presenation 中也有解释。

如果我没记错的话，它会做以下事情:

• 遍历树中的所有节点，除非它们可以根据当前最大已知距离排除。
• 在遍历候选子节点之前对其进行排序，以便首先遍历“最近”的子节点。

因此，该算法非常快速地找到最近的邻居，并且几乎不会遍历不包含部分最终结果的节点(如果有的话)。

有趣的是，Cheung 等人的算法改进了以前的算法，通过删除一些检查来排除更多子节点，然后再遍历它们。他们可以证明额外的检查不可能排除节点。