gre*_*sin 2 spatial r-tree data-structures
我正在阅读来自 Guttman 的论文Link to paper/book
我想知道最近邻查询如何与 R-Trees 一起工作或者它是如何实际实现的。我想到的是，您从根开始遍历树并检查其中一个条目是否包含查询点。
所以第一个问题是，如果一个矩形包含查询点，这并不意味着这个矩形内的所有矩形都会自动成为离查询点最近的矩形。即使查询点不在矩形内，也可能存在另一个距离更短的矩形？
其次，假设查询点实际上是一个最小的边界框，例如mbr = [left,bottom, right, top]，我想要与该区域重叠的所有矩形，或者更好的是其质心位于给定区域内的所有矩形。这也可以吗？
编辑
做了大量的实验，该算法由
Hjaltason、Gísli R. 和 Hanan Samet。“空间数据库中的远程浏览。” ACM 数据库系统事务 (TODS) 24.2 (1999)：265-318。
（如@Anony-Mousse 在回答中发布的那样）显然优于我在此处描述的算法。
旧答案：
据我所知，最好的 kNN 搜索算法是
张、景林和傅伟志。“增强了 R 树上的最近邻搜索。” ACM SIGMOD 记录 27.3（1998）：16-21。（从@Anony-Mousse 的回答中复制） PDF 下载
本演示文稿中还解释了基本算法
如果我没记错的话，它会做以下事情：
因此，该算法非常快速地找到最近的邻居，并且几乎不会遍历不包含部分最终结果的节点（如果有的话）。
有趣的是，Cheung 等人的算法通过删除一些旨在在遍历它们之前排除更多子节点的检查来改进以前的算法。他们可以表明附加检查不可能排除节点。