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