This repository has been archived by the owner. It is now read-only.
Benchmarking approximate nearest neighbors. Note: This is an archived version from our SISAP 2017 paper, see below.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
ann_benchmarks Merge branch 'master' of github.com:maumueller/ann-benchmarks Oct 11, 2017
frontend/website Print parameters. Mar 17, 2017
install Changed location of hamming and nytimes dataset. Oct 13, 2017
protocol Added a README file to the protocol directory Jul 31, 2017
results Removed the precomputed results files Jan 27, 2017
test
tools Small ruby script to split a dataset in a reliable way using a seed. Apr 27, 2017
website Updated website. Apr 25, 2017
.gitignore Added the C implementation of the text-based protocol Jul 31, 2017
.travis.yml remove python 3 for now Jun 21, 2015
Dockerfile
README.rst Update README.rst May 3, 2018
algos.yaml Merge branch 'master' of github.com:maumueller/ann-benchmarks Oct 11, 2017
createwebsite.py
install.sh Don't install sift Apr 26, 2017
plot.py Explicitly close pyplot figures once they've been saved to a file May 16, 2017
setup.py trying to add tox & setting up travis Jun 18, 2015
summarise-results.py

README.rst

Benchmarking nearest neighbors

This project contains some tools to benchmark various implementations of approximate nearest neighbor (ANN) search for different metrics. Visit http://sss.projects.itu.dk/ann-benchmarks to see the results of this benchmark.

Note: The main development of ann-benchmarks can be found at https://github.com/erikbern/ann-benchmarks. The version provided here is what has been used for the paper ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms, M. Aumüller, E. Bernhardsson, A. Faithfull http://www.itu.dk/people/maau/additional/sisap2017-preprint.pdf.

Evaluated

Euclidean space

Hamming distance

Set similarity

Data sets

Euclidean

Angular/Cosine

Hamming space

We used Spherical hashing to generate Hamming space versions of

  • SIFT
  • NYTimes

Set Similarity

We use the following three datasets from http://ssjoin.dbresearch.uni-salzburg.at/

  • Flickr
  • AOL
  • Kosarek

Motivation

Doing fast searching of nearest neighbors in high dimensional spaces is an increasingly important problem, but with little attempt at objectively comparing methods.

Install

Clone the repo and run bash install.sh. This will install all libraries. It could take a while. It has been tested in Ubuntu 16.04. We advice to run it only in a VM or in a docker container (see our Dockerfile).

Downloading and preprocessing the data sets is done by running the install/data-*.sh scripts, e.g., run bash install/data-glove.sh or bash install/data-sift.sh.

Experiment Setup

Running a set of algorithms with specific parameters works:

  • Check that algos.yaml contains the parameter settings that you want to test
  • To run experiments on SIFT, invoke python ann_benchmarks/main --dataset sift-data --query-dataset sift-query --distance euclidean. See python ann_benchmarks/main --help for more information on possible settings. Note that experiments can take a long time.
  • To process the results, either use python plot.py or python createwebsite.py. The website/ directory contains CSS and JS files necessary for displaying the websites generated by createwebsite.py. An example call: python createwebsite.py --plottype recall/time --latex --scatter --outputdir website/.

Including Your Algorithm

You have two choices to include your own algorithm. If your algorithm has a Python wrapper (or is entirely written in Python), then all you need to do is to add your algorithm into ann_benchmarks/algorithms by providing a small wrapper.

If your algorithm does not provide a Python wrapper, you can include it using the SubProcess system. Find a detailed documentation on how to do it here [TBD], or checkout the wrappers written for Annoy-Hamming, Dolphinn, and MIH in the install directory.

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.

Results

See http://sss.projects.itu.dk/ann-benchmarks.

Note that NMSLIB saves indices in the directory indices. If the tests are re-run using a different seed and/or a different number of queries, the content of this directory should be deleted.

Testing

The project is fully tested using Travis, with unit tests run for all different libraries and algorithms.

References