Rails kd tree implementation - need help getting started

I need to query my DB based on two values, which are essentially two float columns in my database.

After some research, I narrowed down my options for implementing this algorithm using either:

• 2D Orthogonal Range Search Tree Structure
• kd

I have now ruled out the first option because my data is clustered and hence it won't be useful.

So I will need to use the kd tree structure. But how? I have never done this and I don't know where to start. I have a method in one of my controllers that is configured as a stub to get the result of this search, but the search itself is not implemented.

I am trying to get the systematic steps involved in creating this feature. For now, this is what I thought I would need to do, but has no idea if it's the right thing to do.

• The kd tree must be built in memory from the data in the DB. (But not sure when this should be done - when does the rails start or when the request comes in?)

• When updating with data, edit the tree and store the whole tree in the database

• Is there any way to store the kd tree data structure in the DB itself without explicitly creating it?

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