Skip to content

Latest commit

 

History

History
120 lines (84 loc) · 7.47 KB

README.md

File metadata and controls

120 lines (84 loc) · 7.47 KB
Raw

Benchmarking nearest neighbors

travis badge

Doing fast searching of nearest neighbors in high dimensional spaces is an increasingly important problem, but so far there has not been a lot of empirical attempts at comparing approaches in an objective way.

This project contains some tools to benchmark various implementations of approximate nearest neighbor (ANN) search for different metrics. We have pregenerated datasets (in HDF5) formats and we also have Docker containers for each algorithm. There's a test suite that makes sure every algorithm works.

Evaluated

Data sets

We have a number of precomputed data sets for this. All data sets are pre-split into train/test and come with ground truth data in the form of the top 100 neighbors. We store them in a HDF5 format:

Dataset Dimensions Train size Test size Neighbors Distance Download
Fashion-MNIST 784 60,000 10,000 100 Euclidean HDF5 (217MB)
GIST 960 1,000,000 1,000 100 Euclidean HDF5 (3.6GB)
GloVe 25 1,133,628 59,886 100 Angular HDF5 (121MB)
GloVe 50 1,133,628 59,886 100 Angular HDF5 (235MB)
GloVe 100 1,133,628 59,886 100 Angular HDF5 (463MB)
GloVe 200 1,133,628 59,886 100 Angular HDF5 (918MB)
MNIST 784 60,000 10,000 100 Euclidean HDF5 (217MB)
NYTimes 256 290,000 10,000 100 Angular HDF5 (301MB)
SIFT 128 1,000,000 10,000 100 Euclidean HDF5 (501MB)

Results

glove-100-angular

glove-100-angular

sift-128-euclidean

glove-100-angular

fashion-mnist-784-euclidean

fashion-mnist-784-euclidean

gist-960-euclidean

gist-960-euclidean

nytimes-256-angular

nytimes-256-angular

glove-25-angular

glove-25-angular

Results as of Feb 2018-02-05, running all benchmarks on a c5.4xlarge machine on AWS.

Install

The only prerequisite is Python (tested with 3.6) and Docker.

  1. Clone the repo.
  2. Run pip install -r requirements.txt.
  3. Run python install.py to build all the libraries inside Docker containers (this can take a while, like 10-30 minutes).

Running

  1. Run python run.py (this can take an extremely long time, potentially days)
  2. Run python plot.py to plot results.

You can customize the algorithms and datasets if you want to:

  • Check that algos.yaml contains the parameter settings that you want to test
  • To run experiments on SIFT, invoke python run.py --dataset glove-100-angular. See python run.py --help for more information on possible settings. Note that experiments can take a long time.
  • To process the results, either use python plot.py --dataset glove-100-angular or python createwebsite.py. An example call: python createwebsite.py --plottype recall/time --latex --scatter --outputdir website/.

Including your algorithm

  1. Add your algorithm into ann_benchmarks/algorithms by providing a small Python wrapper.
  2. Add a Dockerfile in install/ for it
  3. Add it to algos.yaml

Principles

  • Everyone is welcome to submit pull requests with tweaks and changes to how each library is being used.
  • In particular: if you are the author of any of these libraries, and you think the benchmark can be improved, consider making the improvement and submitting a pull request.
  • This is meant to be an ongoing project and represent the current state.
  • Make everything easy to replicate, including installing and preparing the datasets.
  • Try many different values of parameters for each library and ignore the points that are not on the precision-performance frontier.
  • High-dimensional datasets with approximately 100-1000 dimensions. This is challenging but also realistic. Not more than 1000 dimensions because those problems should probably be solved by doing dimensionality reduction separately.
  • No batching of queries, use single queries by default. ANN-Benchmarks saturates CPU cores by using a thread pool.
  • Avoid extremely costly index building (more than several hours).
  • Focus on datasets that fit in RAM. Out of core ANN could be the topic of a later comparison.
  • We currently support CPU-based ANN algorithms. GPU support is planned as future work.
  • Do proper train/test set of index data and query points.
  • Note that Hamming distance and set similarity was supported in the past. This might hopefully be added back soon.

Authors

Built by Erik Bernhardsson with significant contributions from Martin Aumüller and Alexander Faithfull.