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?

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.

Advantages:

• 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)

Disadvantages:

• 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...?!?!)

StackExchange Computer Science Q#55154, answer score: 2