FALCONN

FALCONN (FAst Lookups of Cosine and Other Nearest Neighbors) is a C++ library with a Python wrapper for similarity search over high-dimensional data. It supports cosine similarity and the Euclidean distance. The main ingredient of FALCONN is a Locality-Sensitive Hashing family for cosine similarity that is:

• Optimal in theory,
• Fast in practice.

See the github repo for the source code and documentation (released under the MIT license) or just download version 1.3.1. To install the Pypi package, simply type pip install falconn in a terminal.

Benchmarks

On data sets with about 1 million points in around 100 dimensions, FALCONN typically requires a few milliseconds per query (running on a reasonably modern desktop CPU).

For more detailed results, see ann-benchmarks of Erik Bernhardsson. Let us point out that FALCONN is especially competitive, when the RAM budget is quite restrictive, which is not the regime the above benchmarks use.

Publications

The underlying algorithms are described and analyzed in the following paper:

• “Practical and Optimal LSH for Angular Distance” by A. Andoni, P. Indyk, T. Laarhoven, I. Razenshteyn and L. Schmidt, NIPS 2015, full version available at arXiv:1509.02897.

Authors

FALCONN is designed and implemented by:

• Ilya Razenshteyn (MIT)
• Ludwig Schmidt (MIT)

It grew out of a research project joint with:

• Alexandr Andoni (Columbia University)
• Piotr Indyk (MIT)
• Thijs Laarhoven (TU Eindhoven)

(see the paper above). If you would like to ask any questions, or tell us anything related to FALCONN, write to falconn.lib@gmail.com.

---

© 2015–2016