Dynamic Continuous Indexing (DCI) is a family of randomized algorithms for exact k-nearest neighbour search that overcomes the curse of dimensionality. Its query time complexity is linear in ambient dimensionality and sublinear in intrinsic dimensionality. Details of the algorithm and analysis of time complexity can be found in the following papers:

"Fast k-Nearest Neighbour Search via Dynamic Continuous Indexing", International Conference on Machine Learning (ICML), 2016
"Fast k-Nearest Neighbour Search via Prioritized DCI", International Conference on Machine Learning (ICML), 2017

This repository contains the reference implementation of Prioritized DCI, which was written in C to take advantage of compile-time optimizations and multi-threading. It comes with a C interface, a Python 2 & 3 interface and a TensorFlow op. Currently, the code only runs on the CPU. GPU support will be added in the future.

1. A C compiler with support for OpenMP, e.g.: gcc
2. Python 2.7+ or Python 3.1+
3. A BLAS library (supported implementations include the reference implementation from Netlib, ATLAS, OpenBLAS and MKL)
4. Python development headers
5. (If Python interface is desired) NumPy
6. (If TensorFlow op is desired) TensorFlow and C++ compiler

The library can be compiled in one of two ways: using Python distutils or the good old Makefile. The former requires less manual configuration, but cannot be used if your code uses the C interface or the TensorFlow op.

Note: If your Python interpreter is named differently, e.g.: "python3", you will need to replace all occurrences of "python" with "python3" in the commands below.

If you have sudo access, run the following command from the root directory of the code base to compile and install as a Python package:

sudo python setup.py install

If you do not have sudo access, run the following command instead:

python setup.py install --user

In the root directory of the code base, follow the instructions in the Makefile to specify the paths to BLAS, and optionally, Python, NumPy and TensorFlow.

If you would like to build the Python interface, run the following from the root directory of the code base:

make py

If you would like to use DCI in a script outside of the root directory of the code base, either add a symbolic link to the "dciknn" subdirectory within the directory containing your script, or add the root directory of the code base to your PYTHONPATH environment variable.

If you would like to build the TensorFlow op, run the following from the root directory of the code base:

make tf

If you would like to build a binary executable from code that uses the C interface, run the following from the root directory of the code base:

make c

In the root directory of the code base, execute the following commands, depending on which interface you would like to use:

python examples/example.py

python examples/example_tf.py

examples/example

See the source code for example usage. The source code of the binary executable that uses the C interface is in "src/example.c".

Please cite the following paper if you found this library useful in your research:

Ke Li, Jitendra Malik
International Conference on Machine Learning (ICML), 2016

@inproceedings{li2016fast,
  title={Fast k-nearest neighbour search via {Dynamic Continuous Indexing}},
  author={Li, Ke and Malik, Jitendra},
  booktitle={International Conference on Machine Learning},
  pages={671--679},
  year={2016}
}