6
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – DuckQueen Mar 30 '16 at 2:32
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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...?!?!)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.