Fast k-Nearest Neighbour Search via Dynamic Continuous Indexing
Ke Li, Jitendra Malik
Link to Paper
Link to Paper on Prioritized DCI
Dynamic Continuous Indexing is a family of randomized algorithms for exact nearest neighbour search that overcomes the curse of dimensionality. Its query time scales linearly in the ambient dimensionality and sublinearly in the intrinsic dimensionality.
Slides, Poster and Talk Video
For an illustration of how the algorithm works, see the slides, poster and the talk video.
Our implementation is available here.
Please direct all questions to Ke Li (ke [dot] li [at] eecs [dot] berkeley [dot] edu).