Search code examples
ruby-on-railsrubykdtree

Implementing a k-d tree in Rails - Need help to get started

I need to query my DB based on a range of two values which are essentially two columns of type float in my database.

After doing some research, I narrowed down my options to implementing this with an algorithm using either:

  1. 2D Orthogonal range search
  2. k-d tree structure

Now I eliminated the 1st option because my data are clustered and hence it won't be useful.

So I'm gonna need to use the k-d tree structure. But how? I've never done it and dont know where to start. I have a method in one of my controllers thats set up as a stub to retrieve the result of this search but the search itself is not implemented.

Im trying to get the systematic steps involved in creating this functionality. So far this is what I thought I would need to do, of but have no clue if it's the right way to go.

  1. A k-d tree has to be constructed in memory from data in the DB. (But not sure when this should be done—either when rails starts up or when a request comes in?)

  2. When an update happens to the data, edit the tree and save the entire tree into the database

  3. Would there be any way to save the k-d tree data-structure in the DB itself without constructing it explicitely?

Also, I have googled around but wondering if anyone out there has any resources that they could recommend for this?

Solution

  • There's a gem that we used in a previous project:

    https://rubygems.org/gems/kdtree

    There's also a thread-safe fork of it:

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

    Maybe look at that before implementing your own.