• Stars
    star
    12,751
  • Rank 2,409 (Top 0.05 %)
  • Language
    C++
  • License
    Apache License 2.0
  • Created about 11 years ago
  • Updated 4 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Approximate Nearest Neighbors in C++/Python optimized for memory usage and loading/saving to disk

Annoy

image

Annoy (Approximate Nearest Neighbors Oh Yeah) is a C++ library with Python bindings to search for points in space that are close to a given query point. It also creates large read-only file-based data structures that are mmapped into memory so that many processes may share the same data.

Install

To install, simply do pip install --user annoy to pull down the latest version from PyPI.

For the C++ version, just clone the repo and #include "annoylib.h".

Background

There are some other libraries to do nearest neighbor search. Annoy is almost as fast as the fastest libraries, (see below), but there is actually another feature that really sets Annoy apart: it has the ability to use static files as indexes. In particular, this means you can share index across processes. Annoy also decouples creating indexes from loading them, so you can pass around indexes as files and map them into memory quickly. Another nice thing of Annoy is that it tries to minimize memory footprint so the indexes are quite small.

Why is this useful? If you want to find nearest neighbors and you have many CPU's, you only need to build the index once. You can also pass around and distribute static files to use in production environment, in Hadoop jobs, etc. Any process will be able to load (mmap) the index into memory and will be able to do lookups immediately.

We use it at Spotify for music recommendations. After running matrix factorization algorithms, every user/item can be represented as a vector in f-dimensional space. This library helps us search for similar users/items. We have many millions of tracks in a high-dimensional space, so memory usage is a prime concern.

Annoy was built by Erik Bernhardsson in a couple of afternoons during Hack Week.

Summary of features

  • Euclidean distance, Manhattan distance, cosine distance, Hamming distance, or Dot (Inner) Product distance
  • Cosine distance is equivalent to Euclidean distance of normalized vectors = sqrt(2-2*cos(u, v))
  • Works better if you don't have too many dimensions (like <100) but seems to perform surprisingly well even up to 1,000 dimensions
  • Small memory usage
  • Lets you share memory between multiple processes
  • Index creation is separate from lookup (in particular you can not add more items once the tree has been created)
  • Native Python support, tested with 2.7, 3.6, and 3.7.
  • Build index on disk to enable indexing big datasets that won't fit into memory (contributed by Rene Hollander)

Python code example

from annoy import AnnoyIndex
import random

f = 40  # Length of item vector that will be indexed

t = AnnoyIndex(f, 'angular')
for i in range(1000):
    v = [random.gauss(0, 1) for z in range(f)]
    t.add_item(i, v)

t.build(10) # 10 trees
t.save('test.ann')

# ...

u = AnnoyIndex(f, 'angular')
u.load('test.ann') # super fast, will just mmap the file
print(u.get_nns_by_item(0, 1000)) # will find the 1000 nearest neighbors

Right now it only accepts integers as identifiers for items. Note that it will allocate memory for max(id)+1 items because it assumes your items are numbered 0 … n-1. If you need other id's, you will have to keep track of a map yourself.

Full Python API

  • AnnoyIndex(f, metric) returns a new index that's read-write and stores vector of f dimensions. Metric can be "angular", "euclidean", "manhattan", "hamming", or "dot".
  • a.add_item(i, v) adds item i (any nonnegative integer) with vector v. Note that it will allocate memory for max(i)+1 items.
  • a.build(n_trees, n_jobs=-1) builds a forest of n_trees trees. More trees gives higher precision when querying. After calling build, no more items can be added. n_jobs specifies the number of threads used to build the trees. n_jobs=-1 uses all available CPU cores.
  • a.save(fn, prefault=False) saves the index to disk and loads it (see next function). After saving, no more items can be added.
  • a.load(fn, prefault=False) loads (mmaps) an index from disk. If prefault is set to True, it will pre-read the entire file into memory (using mmap with MAP_POPULATE). Default is False.
  • a.unload() unloads.
  • a.get_nns_by_item(i, n, search_k=-1, include_distances=False) returns the n closest items. During the query it will inspect up to search_k nodes which defaults to n_trees * n if not provided. search_k gives you a run-time tradeoff between better accuracy and speed. If you set include_distances to True, it will return a 2 element tuple with two lists in it: the second one containing all corresponding distances.
  • a.get_nns_by_vector(v, n, search_k=-1, include_distances=False) same but query by vector v.
  • a.get_item_vector(i) returns the vector for item i that was previously added.
  • a.get_distance(i, j) returns the distance between items i and j. NOTE: this used to return the squared distance, but has been changed as of Aug 2016.
  • a.get_n_items() returns the number of items in the index.
  • a.get_n_trees() returns the number of trees in the index.
  • a.on_disk_build(fn) prepares annoy to build the index in the specified file instead of RAM (execute before adding items, no need to save after build)
  • a.set_seed(seed) will initialize the random number generator with the given seed. Only used for building up the tree, i. e. only necessary to pass this before adding the items. Will have no effect after calling a.build(n_trees) or a.load(fn).

Notes:

  • There's no bounds checking performed on the values so be careful.
  • Annoy uses Euclidean distance of normalized vectors for its angular distance, which for two vectors u,v is equal to sqrt(2(1-cos(u,v)))

The C++ API is very similar: just #include "annoylib.h" to get access to it.

Tradeoffs

There are just two main parameters needed to tune Annoy: the number of trees n_trees and the number of nodes to inspect during searching search_k.

  • n_trees is provided during build time and affects the build time and the index size. A larger value will give more accurate results, but larger indexes.
  • search_k is provided in runtime and affects the search performance. A larger value will give more accurate results, but will take longer time to return.

If search_k is not provided, it will default to n * n_trees where n is the number of approximate nearest neighbors. Otherwise, search_k and n_trees are roughly independent, i.e. the value of n_trees will not affect search time if search_k is held constant and vice versa. Basically it's recommended to set n_trees as large as possible given the amount of memory you can afford, and it's recommended to set search_k as large as possible given the time constraints you have for the queries.

You can also accept slower search times in favour of reduced loading times, memory usage, and disk IO. On supported platforms the index is prefaulted during load and save, causing the file to be pre-emptively read from disk into memory. If you set prefault to False, pages of the mmapped index are instead read from disk and cached in memory on-demand, as necessary for a search to complete. This can significantly increase early search times but may be better suited for systems with low memory compared to index size, when few queries are executed against a loaded index, and/or when large areas of the index are unlikely to be relevant to search queries.

How does it work

Using random projections and by building up a tree. At every intermediate node in the tree, a random hyperplane is chosen, which divides the space into two subspaces. This hyperplane is chosen by sampling two points from the subset and taking the hyperplane equidistant from them.

We do this k times so that we get a forest of trees. k has to be tuned to your need, by looking at what tradeoff you have between precision and performance.

Hamming distance (contributed by Martin Aumüller) packs the data into 64-bit integers under the hood and uses built-in bit count primitives so it could be quite fast. All splits are axis-aligned.

Dot Product distance (contributed by Peter Sobot and Pavel Korobov) reduces the provided vectors from dot (or "inner-product") space to a more query-friendly cosine space using a method by Bachrach et al., at Microsoft Research, published in 2014.

More info

Source code

It's all written in C++ with a handful of ugly optimizations for performance and memory usage. You have been warned :)

The code should support Windows, thanks to Qiang Kou and Timothy Riley.

To run the tests, execute python setup.py nosetests. The test suite includes a big real world dataset that is downloaded from the internet, so it will take a few minutes to execute.

Discuss

Feel free to post any questions or comments to the annoy-user group. I'm @fulhack on Twitter.

More Repositories

1

luigi

Luigi is a Python module that helps you build complex pipelines of batch jobs. It handles dependency resolution, workflow management, visualization etc. It also comes with Hadoop support built in.
Python
17,340
star
2

docker-gc

INACTIVE: Docker garbage collection of containers and images
Shell
5,068
star
3

pedalboard

🎛 🔊 A Python library for audio.
C++
4,907
star
4

chartify

Python library that makes it easy for data scientists to create charts.
Python
3,486
star
5

basic-pitch

A lightweight yet powerful audio-to-MIDI converter with pitch bend detection
Python
2,972
star
6

dockerfile-maven

MATURE: A set of Maven tools for dealing with Dockerfiles
Java
2,737
star
7

docker-maven-plugin

INACTIVE: A maven plugin for Docker
Java
2,652
star
8

scio

A Scala API for Apache Beam and Google Cloud Dataflow.
Scala
2,485
star
9

helios

Docker container orchestration platform
Java
2,097
star
10

web-api-examples

Basic examples to authenticate and fetch data using the Spotify Web API
HTML
1,889
star
11

HubFramework

DEPRECATED – Spotify’s component-driven UI framework for iOS
Objective-C
1,863
star
12

apollo

Java libraries for writing composable microservices
Java
1,648
star
13

dh-virtualenv

Python virtualenvs in Debian packages
Python
1,601
star
14

docker-client

INACTIVE: A simple docker client for the JVM
Java
1,426
star
15

docker-kafka

Kafka (and Zookeeper) in Docker
Shell
1,401
star
16

SPTPersistentCache

Everyone tries to implement a cache at some point in their iOS app’s lifecycle, and this is ours.
Objective-C
1,243
star
17

mobius

A functional reactive framework for managing state evolution and side-effects.
Java
1,213
star
18

voyager

🛰️ An approximate nearest-neighbor search library for Python and Java with a focus on ease of use, simplicity, and deployability.
C++
1,175
star
19

sparkey

Simple constant key/value storage library, for read-heavy systems with infrequent large bulk inserts.
C
1,149
star
20

ruler

Gradle plugin which helps you analyze the size of your Android apps.
Kotlin
1,116
star
21

XCMetrics

XCMetrics is the easiest way to collect Xcode build metrics and improve developer productivity.
Swift
1,089
star
22

web-api

This issue tracker is no longer used. Join us in the Spotify for Developers forum for support with the Spotify Web API ➡️ https://community.spotify.com/t5/Spotify-for-Developers/bd-p/Spotify_Developer
RAML
981
star
23

echoprint-codegen

Codegen for Echoprint
C++
948
star
24

snakebite

A pure python HDFS client
Python
858
star
25

heroic

The Heroic Time Series Database
Java
843
star
26

klio

Smarter data pipelines for audio.
Python
831
star
27

XCRemoteCache

Swift
824
star
28

ios-sdk

Spotify SDK for iOS
Objective-C
627
star
29

apps-tutorial

A Spotify App that contains working examples of the use of Spotify Apps API
627
star
30

SPTDataLoader

The HTTP library used by the Spotify iOS client
Objective-C
626
star
31

postgresql-metrics

Tool that extracts and provides metrics on your PostgreSQL database
Python
588
star
32

JniHelpers

Tools for writing great JNI code
C++
587
star
33

Mobius.swift

A functional reactive framework for managing state evolution and side-effects [Swift implementation]
Swift
552
star
34

reactochart

📈 React chart component library 📉
JavaScript
548
star
35

dockerfile-mode

An emacs mode for handling Dockerfiles
Emacs Lisp
525
star
36

threaddump-analyzer

A JVM threaddump analyzer
JavaScript
483
star
37

featran

A Scala feature transformation library for data science and machine learning
Scala
465
star
38

android-sdk

Spotify SDK for Android
HTML
449
star
39

echoprint-server

Server for the Echoprint audio fingerprint system
Java
396
star
40

completable-futures

Utilities for working with futures in Java 8
Java
382
star
41

web-scripts

DEPRECATED: A collection of base configs and CLI wrappers used to speed up development @ Spotify.
TypeScript
381
star
42

SpotifyLogin

Swift framework for authenticating with the Spotify API
Swift
346
star
43

ratatool

A tool for data sampling, data generation, and data diffing
Scala
337
star
44

fmt-maven-plugin

Opinionated Maven Plugin that formats your Java code.
Java
309
star
45

spotify-web-api-ts-sdk

A Typescript SDK for the Spotify Web API with types for returned data.
TypeScript
290
star
46

big-data-rosetta-code

Code snippets for solving common big data problems in various platforms. Inspired by Rosetta Code
Scala
287
star
47

trickle

A small library for composing asynchronous code
Java
284
star
48

coordinator

A visual interface for turning an SVG into XY coördinates.
HTML
283
star
49

pythonflow

🐍 Dataflow programming for python.
Python
281
star
50

styx

"The path to execution", Styx is a service that schedules batch data processing jobs in Docker containers on Kubernetes.
Java
266
star
51

cstar

Apache Cassandra cluster orchestration tool for the command line
Python
254
star
52

netty-zmtp

A Netty implementation of ZMTP, the ZeroMQ Message Transport Protocol.
Java
242
star
53

ios-style

Guidelines for iOS development in use at Spotify
241
star
54

confidence

Python
238
star
55

cassandra-reaper

Software to run automated repairs of cassandra
235
star
56

docker-cassandra

Cassandra in Docker with fast startup
Shell
219
star
57

terraform-gke-kubeflow-cluster

Terraform module for creating GKE clusters to run Kubeflow
HCL
209
star
58

basic-pitch-ts

A lightweight yet powerful audio-to-MIDI converter with pitch bend detection.
TypeScript
206
star
59

dns-java

DNS wrapper library that provides SRV lookup functionality
Java
204
star
60

linux

Spotify's Linux kernel for Debian-based systems
C
204
star
61

git-test

test your commits
Shell
202
star
62

SPStackedNav

[DEPRECATED] Navigation controller which represents its content in stacks of panes, rather than one at a time
Objective-C
195
star
63

quickstart

A CommonJS module resolver, loader and compiler for node.js and browsers.
JavaScript
193
star
64

spotify-json

Fast and nice to use C++ JSON library.
C++
191
star
65

dbeam

DBeam exports SQL tables into Avro files using JDBC and Apache Beam
Java
188
star
66

flink-on-k8s-operator

Kubernetes operator for managing the lifecycle of Apache Flink and Beam applications.
Go
180
star
67

lingon

A user friendly tool for building single-page JavaScript applications
JavaScript
162
star
68

bazel-tools

Tools for dealing with very large Bazel-managed repositories
Java
162
star
69

dataenum

Algebraic data types in Java.
Java
161
star
70

magnolify

A collection of Magnolia add-on modules
Scala
158
star
71

async-google-pubsub-client

[SUNSET] Async Google Pubsub Client
Java
157
star
72

gcp-audit

A tool for auditing security properties of GCP projects.
Python
156
star
73

spark-bigquery

Google BigQuery support for Spark, SQL, and DataFrames
Scala
155
star
74

should-up

Remove most of the "should" noise from your tests
JavaScript
150
star
75

flo

A lightweight workflow definition library
Java
146
star
76

folsom

An asynchronous memcache client for Java
Java
145
star
77

missinglink

Build time tool for detecting link problems in java projects
Java
142
star
78

android-auth

Spotify authentication and authorization for Android. Part of the Spotify Android SDK.
HTML
140
star
79

proto-registry

An implementation of the Protobuf Registry API
TypeScript
140
star
80

zoltar

Common library for serving TensorFlow, XGBoost and scikit-learn models in production.
Java
138
star
81

futures-extra

Java library for working with Guava futures
Java
135
star
82

annoy-java

Approximate nearest neighbors in Java
Java
134
star
83

spydra

Ephemeral Hadoop clusters using Google Compute Platform
Java
133
star
84

spotify-web-playback-sdk-example

React based example app that creates a new player in Spotify Connect to play music from in the browse using Spotify Web Playback SDK.
JavaScript
129
star
85

docker-stress

Simple docker stress test and monitoring tools
Python
125
star
86

spotify-tensorflow

Provides Spotify-specific TensorFlow helpers
Python
124
star
87

crtauth

a public key backed client/server authentication system
Python
118
star
88

redux-location-state

Utilities for reading & writing Redux store state to & from the URL
JavaScript
118
star
89

sparkey-java

Java implementation of the Sparkey key value store
Java
117
star
90

github-java-client

A Java client to Github API
Java
114
star
91

realbook

Easier audio-based machine learning with TensorFlow.
Python
109
star
92

rspec-dns

Easily test your DNS with RSpec
Ruby
107
star
93

web-playback-sdk

This issue tracker is no longer used. Join us in the Spotify for Developers forum for support with the Spotify Web Playback SDK ➡️ https://community.spotify.com/t5/Spotify-for-Developers/bd-p/Spotify_Developer
107
star
94

ffwd-ruby

An event and metrics fast-forwarding agent.
Ruby
106
star
95

gimme

Creating time bound IAM Conditions with ease and flair
Python
103
star
96

super-smash-brogp

Sends and withdraws BGP prefixes for fun.
Python
98
star
97

lighthouse-audit-service

TypeScript
93
star
98

noether

Scala Aggregators used for ML Model metrics monitoring
Scala
91
star
99

python-graphwalker

Python re-implementation of the graphwalker testing tool
Python
91
star
100

spotify.github.io

Showcase site for hand-picked open-source projects by Spotify
HTML
88
star