multidimensional-array - 在空间数据库中查找 K 个最近的对（无特定查询对象）

Question

输入：

• N 点{P1, .... , Pn} - 每个点都来自相同的维度 t：

• Pi = {x_1, ...., x_t} 其中 k 在 18-30 之间。

• 距离函数——dist(Pi, Pj) ——返回一个数字，表示点之间的距离。（该函数是一个自定义函数——不是标准的 Minkowski 距离）。

问题：

• 主要问题：

• 尽可能快地从所有 N 个点中找到 K 个最接近的对。

• 次要问题：

• 给定一个点 Q = {x_1, ..., x_t} 返回 K 个最接近的对。

• 很高兴拥有：

• 我们可以在其中添加/删除点 Pi 的数据库，上述查询将尽可能快地运行。

相关数据结构：

• KD-树

• https://en.wikipedia.org/wiki/K-d_tree

• http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KDTree.html

• R-树

• https://en.wikipedia.org/wiki/R-tree

• http://toblerity.org/rtree/

• 球树

• https://en.wikipedia.org/wiki/Ball_tree

• http://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html

可能的解决方案：

• 主要问题：

• 构建一个 BallTree (sklearn.neighbors.BallTree)。

• 对于 BallTree 中的每个点 P，找到 K 个最接近的对（现在我们有 N 个列表——每个列表包含每个点 Pi 的 K 个最接近的对）。

• 从上面的所有列表中选择最好的 K 对。

• 次要问题：

• 构建一个 BallTree (sklearn.neighbors.BallTree)。

• 查询给定点 Q 的最近 k 对。

到目前为止的时间复杂度：

• 对于树中的每个点（总共 N 个），找到 K 个最接近的对，它们取 O(K*log(N)) -所以总共 O(N * K * log(N))。

• 从 N 个排序列表中取出最好的 K 对 - 可以取O( Max{ K * log(K), N } )。例如，保持大小为 K 的最小 HEAP。

目前，总复杂度为O(N * K * log(N)) - 我们能做得更好吗？

标签： multidimensional-arrayspatialknnspatial-queryspatial-index