ruby-on-rails - 在 Rails 中实现 k-d 树 - 需要帮助才能开始

Question

我需要根据两个值的范围查询我的数据库，这两个值本质上是我数据库中的两列 float 类型。

在做了一些研究之后，我缩小了我的选择范围，使用以下任一算法来实现它:

1. 二维正交范围搜索
2. k-d树结构

现在我取消了第一个选项，因为我的数据是集群的，因此它没有用。

所以我需要使用 k-d 树结构。但是怎么办？我从来没有做过，也不知道从哪里开始。我的一个 Controller 中有一个方法，该方法设置为 stub 来检索此搜索的结果，但搜索本身未实现。

我试图获得创建此功能所涉及的系统步骤。到目前为止，这是我认为我需要做的，但不知道这是否是正确的方法。

1. 必须根据数据库中的数据在内存中构建 k-d 树。 (但不确定应该在什么时候完成——是在 Rails 启动时还是在收到请求时？)

2. 当数据发生更新时，编辑树并将整个树保存到数据库中

3. 是否有任何方法可以在不显式构造的情况下将 k-d 树数据结构保存在数据库中？

另外，我用谷歌搜索了一下，但想知道是否有人可以为此推荐任何资源？

Answer 1

我们在之前的项目中使用了一个 gem:

https://rubygems.org/gems/kdtree

它还有一个线程安全的分支:

https://rubygems.org/gems/tupalo-kdtree

也许在实现您自己的之前先看一下。