R树中的最近邻算法
Nearest Neighbor Algorithm in R-Tree
我正在阅读 Guttman 的论文 Link to paper/book
我想知道最近邻查询如何与 R 树一起工作，或者它是如何实际实现的。
我想到的是从根开始遍历树并检查其中一个条目是否包含查询点。
所以第一个问题是，如果一个矩形包含查询点，这并不意味着这个矩形内的所有矩形都会自动距离查询点最近。也有可能存在距离更短的另一个矩形，即使查询点不在矩形内？
其次，假设查询点实际上是一个最小边界框，例如 mbr = [left,bottom, right, top] 并且我想要所有与该区域重叠的矩形，或者更好的是其质心位于给定区域内的所有矩形。这也可以吗？
有很多关于在 R 树中寻找最近邻的论文。
Roussopoulos、Nick、Stephen Kelley 和 Frédéric Vincent。 "Nearest neighbor queries." ACM sigmod 记录。卷。 24. 第 2 期. ACM, 1995.
Papadopoulos、Apostolos 和 Yannis Manolopoulos。 "Performance of nearest neighbor queries in R-trees." 数据库理论—ICDT'97 (1997)：394-408。
Hjaltason、Gísli R. 和 Hanan Samet。 "Distance browsing in spatial databases." ACM 数据库系统事务 (TODS) 24.2 (1999)：265-318。
Cheung、King Lum 和 Ada Wai-Chee Fu。 "Enhanced nearest neighbour search on the R-tree." ACM SIGMOD 记录 27.3 (1998)：16-21。
Berchtold, S.、Böhm, C.、Keim, D. A. 和 Kriegel, H. P.（1997 年 5 月）。高维数据中最近邻搜索的成本模型space。在第十六届 ACM SIGACT-SIGMOD-SIGART 数据库系统原理研讨会论文集中（第 78-86 页）。 ACM.
编辑
做了无数次实验，算法通过
Hjaltason、Gísli R. 和 Hanan Samet。 "Distance browsing in spatial databases." ACM 数据库系统事务 (TODS) 24.2 (1999)：265-318。
（如@Anony-Mousse 在回答中发布的那样）明显优于我在此处描述的算法。
旧答案：
据我所知，最好的 kNN 搜索算法是
Cheung、King Lum 和 Ada Wai-Chee Fu。 "Enhanced nearest neighbour search on the R-tree." ACM SIGMOD 记录 27.3 (1998)：16-21。 （从@Anony-Mousse 的回答中复制）PDF download
基本算法在this presenation
中也有说明
如果我没记错的话，它会做以下事情：
- 遍历树中的所有节点，除非它们可以根据当前最大已知距离排除。
- 在遍历候选子节点之前对其进行排序，以便首先遍历 'closest' 个子节点。
因此，该算法可以非常快速地找到最近的邻居并且几乎遍历（如果有的话）不包含部分最终结果的节点。
有趣的是，Cheung 等人的算法通过 删除 一些旨在在遍历它们之前排除更多子节点的检查来改进以前的算法。他们可以证明额外的检查不可能排除节点。
我正在阅读 Guttman 的论文 Link to paper/book
我想知道最近邻查询如何与 R 树一起工作，或者它是如何实际实现的。 我想到的是从根开始遍历树并检查其中一个条目是否包含查询点。
所以第一个问题是，如果一个矩形包含查询点，这并不意味着这个矩形内的所有矩形都会自动距离查询点最近。也有可能存在距离更短的另一个矩形，即使查询点不在矩形内？
其次，假设查询点实际上是一个最小边界框，例如 mbr = [left,bottom, right, top] 并且我想要所有与该区域重叠的矩形，或者更好的是其质心位于给定区域内的所有矩形。这也可以吗？
有很多关于在 R 树中寻找最近邻的论文。
Roussopoulos、Nick、Stephen Kelley 和 Frédéric Vincent。 "Nearest neighbor queries." ACM sigmod 记录。卷。 24. 第 2 期. ACM, 1995.
Papadopoulos、Apostolos 和 Yannis Manolopoulos。 "Performance of nearest neighbor queries in R-trees." 数据库理论—ICDT'97 (1997)：394-408。
Hjaltason、Gísli R. 和 Hanan Samet。 "Distance browsing in spatial databases." ACM 数据库系统事务 (TODS) 24.2 (1999)：265-318。
Cheung、King Lum 和 Ada Wai-Chee Fu。 "Enhanced nearest neighbour search on the R-tree." ACM SIGMOD 记录 27.3 (1998)：16-21。
Berchtold, S.、Böhm, C.、Keim, D. A. 和 Kriegel, H. P.（1997 年 5 月）。高维数据中最近邻搜索的成本模型space。在第十六届 ACM SIGACT-SIGMOD-SIGART 数据库系统原理研讨会论文集中（第 78-86 页）。 ACM.
编辑
做了无数次实验，算法通过
Hjaltason、Gísli R. 和 Hanan Samet。 "Distance browsing in spatial databases." ACM 数据库系统事务 (TODS) 24.2 (1999)：265-318。
（如@Anony-Mousse 在回答中发布的那样）明显优于我在此处描述的算法。
旧答案：
据我所知，最好的 kNN 搜索算法是
Cheung、King Lum 和 Ada Wai-Chee Fu。 "Enhanced nearest neighbour search on the R-tree." ACM SIGMOD 记录 27.3 (1998)：16-21。 （从@Anony-Mousse 的回答中复制）PDF download
基本算法在this presenation
中也有说明如果我没记错的话，它会做以下事情：
- 遍历树中的所有节点，除非它们可以根据当前最大已知距离排除。
- 在遍历候选子节点之前对其进行排序，以便首先遍历 'closest' 个子节点。
因此，该算法可以非常快速地找到最近的邻居并且几乎遍历（如果有的话）不包含部分最终结果的节点。
有趣的是，Cheung 等人的算法通过 删除 一些旨在在遍历它们之前排除更多子节点的检查来改进以前的算法。他们可以证明额外的检查不可能排除节点。