KGraph is the next generation indexing technology for K-NN graph construction and nearest neighbor search.

  • It only assumes that a distance/similarity can be computed on any pair of data objects, absolutely nothing else about the form of the underlying data.
  • It is usually faster than popular libraries like FLANN on the distance metrics they support.

Some of the optimizations are back ported to my previous library nndes. Still, KGraph is about 2x faster than the latest nndes in building a K-NN graph. I have long abandoned LSHKIT because LSH is so hopelessly slow and/or inaccurate.

Speedup over FLANN brutal force search for 10-NN from 1 million SIFT features. At 0.9 recall,

  • KGraph is 100x 200x baseline. (Version 1.2)
  • FLANN hierarchical index is 40x baseline.
  • FLANN kmeans clustering is 30x baseline.
  • FLANN kdtree is 20x of baseline.

See Benchmark for details.


KGraph is now open-sourced in BSD license: https://github.com/aaalgo/kgraph.