I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N neighbors in a range surrounding a given key) as fast as possible in terms of search algorithmic complexity (on average). Also I need a fast (on average) remove-insert or key update mechanism in that datastructure. I wonder what is such structure?
An octree or k-d tree are standard data structures for this sort of task, and should provide reasonably efficient support for all of the operations you listed.
The Covertree is a specialized data structure for neighbour search. However I don't know it's update performance.
A better option may be the PH-Tree (my own implementation). It is similar to a quadtree, but implemented as a prefix-sharing bit-level trie.
- Maximum depth of the tree is 64 (assuming 64bit per dimension)
- No reordering, ever. This is important for insertion/deletion/updates, at most two nodes are modified for every insert/delete.
- It has a dedicate
update()method for moving points. This is especially efficient for moving 'small' distances.
- Very good N-neighbour-serach performance, especially for low numbers of N, such as closest 10 neighbours or so.
- Quite space efficient in memory
- Scales very well with large number of entries (1,000,000 or more)
- Very good with clustered data (it prefers clustered data of evenly distributed data)
- Less efficient for small data sets
- Complex to implement, currently there is only a Java implementation available, see link above. (One reason: Nobody has yet managed to write a C++ implementation that is faster than the Java version...?!?!)