ANNchor: Fast Approximate k-NN Graph Construction for Slow Metrics

ANNchor is an algorithm for the fast construction of approximate k-nearest neighbour (k-NN) graphs in a metric space where the metric is slow to compute. Given a metric space (X, d), we use anchor points (i.e. a small subset of X) and the triangle inequality to construct an approximation to d that is fast to compute. The fast metric is used to quickly identify candidate nearest neighbours, which are then checked by the slow metric. In this way, ANNchor aims to use significantly fewer calls to the slow metric than current state-of-the-art techniques for k-NN graph construction (e.g. Nearest Neighbour Descent, HNSW). This leads to significant decreases in algorithm run-time when calls to the slow metric are the bottleneck of the computational process.

Installation

Install from source (clone the annchor repo from github):

pip install -e ./annchor

User Guide:

• ANNchor User Guide (v1.1.0)
  • Example: Wasserstein
  • Example: Levenshtein
  • Example: Shortest Path Distance
• Basic Parameters
  • func_kwargs
  • n_anchors
  • n_neighbors
  • n_samples
  • p_work
  • locality and loc_thresh
  • verbose
  • backend
• Advanced Parameters
  • anchor_picker
  • sampler
  • regression
  • error_predictor
  • is_metric
  • get_exact_ijs
  • niters
• Parallelisation

API Reference:

• ANNchor API Guide
  • Annchor
  • Utility Functions
  • Data sets

Indices and tables

• Index

• Module Index

• Search Page