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
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?
source to share