Search code examples
mongodbredisspatial-indexdatabase

k nearest neighbors query in 3-space

I have a data set stored in database table that includes a position in 3-space. I need to retrieve the k nearest neighbors in an efficient manner. My datastore does not include native spacial indexes for 3 dimensions. How do I simulate a spacial index in the client.

This question might be rephrased, How can KD-Trees be implemented for date stored in a database?

(if it makes a difference, the actual databases used are MongoDB and Redis)

Solution

  • Maybe that could interest you:

    http://en.wikipedia.org/wiki/Octree

    I suppose it could play nicely with algorithms such as Map-Reduce.