# A key-value datastructure with fast (on average) member move and nearest neighbors search?

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?

• Currently I use KD-tree, I think on moving to OpenVDB. I wonder if there is any specialized data structure or one that can feet my needs better. Mar 30, 2016 at 2:32

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.

• It has a dedicate update() method for moving points. This is especially efficient for moving 'small' distances.