PaperlayerView exact revision on arXiv

Source-linked AI summary

ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms

Martin Aumüller, Erik Bernhardsson, Alexander Faithfull

arXiv:1807.05614v2cs.IRcs.DB

TL;DR

High-dimensional nearest neighbor search requires approximate methods, while existing evaluations often use small, selective comparisons that are difficult to reproduce. ANN-Benchmarks standardizes benchmarking across implementations, datasets, parameter settings, and quality measures. Its evaluation reports that graph-based methods are fastest on GLOVE and SIFT while several approaches achieve close to perfect recall, with in-memory benchmarking as a scope boundary.

  • Problem

    High-dimensional data makes efficient exact nearest neighbor search impractical, while evaluations often compare few algorithms and datasets, limiting reproducibility and breadth.

  • Method

    ANN-Benchmarks provides a unified framework that runs configured implementations on standard datasets, computes timing and quality measures centrally, and supports extensible metrics.

  • Results

    Graph-based algorithms are fastest on GLOVE and SIFT, while most tested implementations achieve close to perfect recall on those datasets.

  • Takeaways & Limitations

    The benchmark overview helps users choose algorithm and parameter combinations and provides a testbed for comparing methods and developing automatic parameter tuning.

  • Takeaways & Limitations

    ANN-Benchmarks currently benchmarks in-memory datasets, in practice handling millions of points with dimensionality up to a few thousand dimensions.

Abstract

from arXiv · show

This paper describes ANN-Benchmarks, a tool for evaluating the performance of in-memory approximate nearest neighbor algorithms. It provides a standard interface for measuring the performance and quality achieved by nearest neighbor algorithms on different standard data sets. It supports several different ways of integrating $k$-NN algorithms, and its configuration system automatically tests a range of parameter settings for each algorithm. Algorithms are compared with respect to many different (approximate) quality measures, and adding more is easy and fast; the included plotting front-ends can visualise these as images, $\LaTeX$ plots, and websites with interactive plots. ANN-Benchmarks aims to provide a constantly updated overview of the current state of the art of $k$-NN algorithms. In the short term, this overview allows users to choose the correct $k$-NN algorithm and parameters for their similarity search task; in the longer term, algorithm designers will be able to use this overview to test and refine automatic parameter tuning. The paper gives an overview of the system, evaluates the results of the benchmark, and points out directions for future work. Interestingly, very different approaches to $k$-NN search yield comparable quality-performance trade-offs. The system is available at http://ann-benchmarks.com .

1 Introduction

ANN-Benchmarks standardizes empirical evaluation of approximate nearest neighbor algorithms, addressing selective comparisons and difficult reproducibility. It unifies experimentation, comparison, quality measurement, and visualization across implementations and datasets.

  • 1 Introduction: High-dimensional nearest neighbor search motivates approximation because exact search can require linear time or exponential time/space in dimensionality.The curse of dimensionality makes efficient exact search impractical for massive high-dimensional datasets.
  • 1 Introduction: Evaluations often compare new implementations against only a small set of algorithms and datasets, making results difficult to reproduce and potentially selective.Authors and reviewers may lack implementations, conventions may differ, parameters may be omitted, and exhaustive testing can be costly.
  • 1 Introduction: ANN-Benchmarks provides a unified framework for experimenting with and comparing nearest neighbor implementations using standard datasets and quality measures.The framework is designed to standardize benchmarking while accommodating different algorithm properties and evaluation measures.
  • 1 Introduction: The framework complements existing reproducibility and benchmarking tools by requiring a simple programmatic interface while performing timing and quality computation centrally.This design permits adding computable metrics without rerunning algorithms and benchmarks implementations as intended by their authors.
  • 1 Introduction: The benchmark overview helps users select algorithms and parameters while exposing challenging datasets and metrics for future algorithm development and automatic tuning.The authors also expect the suite to serve as a testbed for parameter tuning.

2 Problem Definition and Qality Measures

The paper formalizes approximate nearest neighbor queries and evaluates returned results with distance-based recall measures. It also supports multiple performance measures for preprocessing and querying, while noting concerns about approximate recall in high dimensions.

  • Problem definition: A nearest-neighbor algorithm builds a data structure over dataset S and returns at most k close, distinct points for each query q.The formal setup uses a distance measure on space X and compares returned tuples with the true nearest neighbors.
  • Quality measures: The framework defines recall using the distance of the k-th true neighbor as a threshold, avoiding issues from ties and approximate results.The same thresholding principle supports (1 + ε)-approximative recall.
  • Quality measures: (1 + ε)-approximative recall counts returned points within (1 + ε) times the distance to the k-th true nearest neighbor, divided by k.The definition applies for ε > 0.
  • Quality measures: The authors note that approximate recall in high dimensions is sometimes criticized and plan to include position-related measures in future work.This identifies a scope boundary in the currently included quality measures.
  • Performance measures: Performance measures cover both preprocessing and query execution, including query time and the number of distance computations.The framework accommodates communities that prefer timing-based or operation-count-based cost measures.

3 System Design

ANN-Benchmarks combines containerized installation, configurable algorithm instances, a query protocol, dataset management, and extensible metrics into an experimental pipeline. Its current scope is in-memory benchmarking, with single-CPU evaluation and future interest in parallel and batched queries.

  • System design: ANN-Benchmarks automatically downloads datasets, installs implementations and dependencies with Docker, and provides front-ends for running and plotting experiments.Implementations can also be run locally during development.
  • System design: A text-based protocol lets external programs configure parameters, receive training data, and run queries through wrappers implemented in any programming language.The protocol is flexible and extensible, though plaintext communication adds some overhead.
  • Datasets and ground truth: Datasets contain points, queries, a distance metric, true k = 100 neighbors, and their distances, with scripts supporting alternative k values and private datasets.Most query sets contain ten thousand pseudorandomly selected entries separated from training data.
  • Creating algorithm instances: YAML configurations expand algorithm and query parameter groups into multiple constructor settings and experiments, enabling systematic parameter sweeps.Cartesian products generate many algorithm instances and query configurations from compact entries.
  • The experiment loop: The framework benchmarks in-memory datasets, handling millions of points with dimensionality up to a few thousand dimensions in practice.This dataset-residency requirement constrains which datasets can be included.
  • Results and metrics: Metric functions receive ground truth and run results, so new quality measures can be added as short Python functions and supported automatically by plotting scripts.The framework can compute metrics independently of algorithm implementations.

4 Evaluation

The evaluation benchmarks diverse approximate nearest-neighbor implementations and datasets under a standardized experimental setup. It examines algorithmic principles, dataset construction, parameter settings, and implementation status.

  • Experimental setup: Experiments ran in Docker containers on Amazon EC2 c5.4xlarge instances with 32GB of RAM, allowing five hours per parameter setting and dataset.Results were also compared with a four-core Intel Core i7-4790 system, while the relative algorithm order remained stable.
  • Visualization: Figure 3 illustrates an interactive plot showing queries per second against recall for an Annoy run.The highlighted run achieves about 1249 queries per second at about 0.52 recall.
  • Tested Algorithms: The evaluation covers graph-based, tree-based, and hashing-based nearest-neighbor algorithms.Graph methods traverse k-NN graphs; tree and hashing methods use different candidate-generation strategies.
  • Datasets: The benchmark uses multiple datasets, including NYTimes, Hamming-space SIFT, Word2Bits, and Rand-Euclidean.Rand-Euclidean combines mostly unstructured data with locally separated neighbors around each query point.
  • Parameters of Algorithms: Most algorithms lack an explicit quality target, so the framework tests many parameter settings for each implementation.Detailed settings are maintained on the framework’s website.
  • Status of FALCONN: The evaluation omits FALCONN from this submission because its performance had drastically decreased in recent versions.The authors reported the issue to FALCONN’s developers and planned inclusion in a revised version.

4.1 Objectives of the Experiments

The experiments use ANN-Benchmarks to study performance, robustness, approximation, and embeddings across algorithms, datasets, quality measures, and distance spaces. The reported discussion combines framework plots, with fuller and more current results available online.

  • Performance: Q1 compares algorithms by query performance and index size for a dataset, quality measure, and requested neighbor count.The question considers measures such as query time and index size.
  • Robustness: Q2 examines how an algorithm’s performance and result quality change across datasets and numbers of returned neighbors.This objective targets robustness to dataset and output-size changes.
  • Approximation: Q3 studies how allowing approximate neighbors improves performance and whether the effect is comparable across algorithms.The comparison fixes a dataset and requested neighbor count while varying approximation.
  • Embeddings: Q4 investigates algorithms and internal techniques across Euclidean, Cosine, and Hamming spaces.It asks whether cross-space use and Hamming-specific internals improve performance.
  • Evidence base: The discussion is based on framework plots, while the website contains more complete and up-to-date results.The paper presents the plots as the basis for its discussion rather than as the complete result repository.

4.2 Discussion

Across datasets and metrics, graph-based methods often provide strong recall-QPS trade-offs, but performance varies with dataset structure, representation, and approximation. The benchmark also exposes differences in index size, parameter tuning, and robustness.

  • Performance: Graph-based algorithms generally outperform tree-based approaches on GLOVE and SIFT recall-QPS comparisons.On GLOVE, HNSW is fastest overall and KGraph is competitive at high recall; on SIFT, graph-based methods are again fastest.
  • Performance: Most implementations achieve close to perfect recall on GLOVE and SIFT, although graph-based indexes may fail to build for nearly perfect recall within five hours on GLOVE.
  • Parameter tuning: Very few algorithms automatically tune themselves to a target recall, leaving users to select parameter combinations for many fast methods.KGraph uses one parameter and still gives high recall, while FLANN tunes well but may exceed the time limit at high recall, especially for 100-NN.
  • Index size: Index-size performance differs substantially: HNSW is best on SIFT, while FAISS-IVF and HNSW are nearly indistinguishable on GLOVE.The metric scales index size by achieved QPS, penalizing small indexes when probing makes queries expensive.
  • Robustness: Robustness depends on dataset structure: PANNG, KGraph, NND, Annoy, and FAISS-IVF handle Rand-Euclidean well, whereas HNSW and SWG perform poorly.The passage attributes the latter behavior to their small-world structure, and no tested HNSW setting exceeds .86 recall.
  • Cross-dataset behavior: Across datasets, algorithms usually agree on relative difficulty, but Rand-Euclidean and NYTimes are notable exceptions.HNSW is least affected by high-recall performance loss, yet shows the largest slowdown from 10-NN to 100-NN queries.
  • Representation: Embedding SIFT in Hamming space makes queries faster despite doubling dimensionality, while Hamming-aware methods can also reduce index size.The Hamming-space Annoy variant is two to three times faster until high recall, but the original version is faster on Word2Bits.

4.3 Index build time remarks

Index construction time varies dramatically across implementations, even when indexes meet the same recall threshold. Faster construction reduces the time needed to explore parameter choices.

  • Build-time comparison: FAISS-IVF builds a recall-at-least-0.9 GLOVE index in around 2 seconds, while HNSW takes almost 5 hours.These times compare minimum build times for indexes achieving recall of at least 0.9 for 10-NN.
  • Build-time comparison: Graph and tree construction generally takes considerably longer than the inverted-file approach used by FAISS-IVF.
  • Practical implication: Shorter build times make it quicker to search for the best parameter choices for a dataset.
  • Implementation variation: An HNSW index built through FAISS reached recall .9 in 1 700 seconds.

4.4 Batched Qeries

Batched queries allow algorithms to process all query points together and exploit optimizations such as reduced GPU transfer overhead. In this setting, FAISS-IVF on the GPU is substantially faster than CPU execution.

  • Batching: Batched querying allows optimizations such as amortizing GPU data-transfer overhead across the full query set.
  • Results: FAISS-IVF on the GPU answers around 655 000 queries per second at .7 recall and 61 000 at recall .99.
  • Results: GPU FAISS-IVF runs around 20 to 30 times faster than the corresponding CPU data structure.
  • Results: Batched HNSW achieves roughly a threefold speedup at .5 recall and nearly a fivefold speedup at higher reported recall.

4.5 Summary

Graph-based algorithms generally provide the strongest performance, but their advantages depend on dataset structure and incur higher preprocessing costs. Parameter exploration remains important because users often must configure many settings themselves.

  • Algorithm choice: Graph-based algorithms provide the best performance on most datasets, with HNSW often fastest and PANNG more robust when datasets lack global structure.Graph-based methods can be less suitable when datasets change regularly because their indexes require substantial preprocessing.
  • Generalization: Algorithms usually agree on dataset difficulty and relative ordering, but Rand-Euclidean is an exception where implementations behave differently.The generalization pattern therefore has a clear dataset-dependent boundary.
  • Evaluation views: Figure 11 compares Recall-QPS trade-offs for batched and non-batched HNSW with CPU and GPU FAISS indexes on SIFT 10-NN.The figure uses up-and-right as the better direction.
  • Parameter choice: Users often need to set many parameters themselves, although interactive plots can expose choices that achieve selected quality guarantees.Only a few implementations allow recall to be specified directly as an input parameter.
  • Parameter choice: Larger indexes generally perform better at high recall and are more robust to query-parameter choices.Build parameters estimate index size, while query parameters control search effort.

5 Conclusion & Further Work

ANN-Benchmarks automates evaluation of approximate nearest-neighbor implementations and shows that graph-based approaches often lead at very high recall. The authors identify limitations in usability, metric coverage, dataset understanding, and batched-query benchmarking as directions for further work.

  • Conclusion: ANN-Benchmarks is an automated system for evaluating existing approximate nearest-neighbor algorithms.The paper uses the system to compare implementations across datasets and quality settings.
  • Conclusion: Graph-based approaches such as HNSW and KGraph outperform other approaches for very high recall on most datasets.The conclusion notes exceptions on a few datasets.
  • Conclusion: Graph-based indexes require long construction times for datasets with difficult queries.This is identified as a practical cost of the strongest high-recall approaches.
  • Future work: Most performant implementations remain difficult to use because their internal parameters are exposed rather than automatically tuned from a few quality targets.The authors propose tuning from a small dataset sample before training begins.
  • Future work: The benchmark does not yet explain which dataset properties make particular algorithms easy or difficult, especially where random datasets produce divergent behavior.The authors contrast this with the more homogeneous results observed on many real-world datasets.
  • Future work: Batched-query benchmarking, particularly on GPUs, remains an area for future work.The authors suggest exploiting similarities among queries in a batch.
Loading 1807.05614v2…