Annoy (Approximate Nearest Neighbors Oh Yeah)

Annoy performance and accuracy are controlled by two main parameters:

1. n_trees (Build-time): Affects build time and index size. More trees increase precision but result in larger indexes.
2. search_k (Runtime): Affects search speed. A larger search_k increases accuracy but increases query time. If not provided, it defaults to n * n_trees.

Recommendation: Set n_trees as large as your memory allows, and search_k as large as your latency constraints allow. These two parameters are roughly independent.

When loading an index via a.load(fn, prefault=False), you can control how memory is allocated:

• prefault=True: Pre-reads the entire file into memory (using mmap with MAP_POPULATE). This increases initial loading time but makes subsequent searches faster.
• prefault=False (Default): Pages are read from disk and cached in memory on-demand. This is better for systems with low memory or when only small, specific parts of a large index are frequently queried.

To run the Annoy Lua tests, you need the Busted testing framework.

1. Install busted via luarocks:

   luarocks install busted

2. Execute the tests using the busted command:

   busted test/annoy_test.lua

To install the Go bindings for Annoy, you must have Swig installed (tested with Swig 4.2.1 on Ubuntu 24.04). Follow these steps to generate the bindings and set up the Go module in your GOPATH:

1. Generate the Go module using Swig: swig -go -intgosize 64 -cgo -c++ src/annoygomodule.i
2. Create the directory in your GOPATH: mkdir -p $(go env GOPATH)/src/annoy
3. Copy the necessary source files to the GOPATH: cp src/annoygomodule_wrap.cxx src/annoy.go src/annoygomodule.h src/annoylib.h src/kissrandom.h test/annoy_test.go $(go env GOPATH)/src/annoy
4. Initialize and tidy the Go module: cd $(go env GOPATH)/src/annoy go mod init github.com/spotify/annoy go mod tidy
5. Run tests to verify installation: go test

To install Annoy for Lua, you need Lua (binary and library) and LuaRocks.

If you have Python and Pip, you can use hererocks to set up a local Lua environment:

1. Install hererocks via pip:

   pip install hererocks

2. Use hererocks to install Lua 5.1 and LuaRocks 2.2 into a local directory named here:

   hererocks here --lua 5.1 --luarocks 2.2

3. Add the local bin directory to your PATH to use lua and luarocks:

   export PATH="$(pwd)/here/bin/:$PATH"

4. Build and install annoy using luarocks:

   luarocks make

To install the Python bindings, use pip. For C++ development, clone the repository and include annoylib.h in your project.

pip install --user annoy

Users should be aware that memory leaks may occur if incorrect inputs are provided.

Some functions allocate stack objects that call Lua functions which might throw Lua errors (e.g., luaL_checkinteger). Depending on the Lua implementation and the platform, a Lua error during stack unwinding might omit calling C++ destructors.

This example demonstrates the full lifecycle of an Annoy index: initializing with a dimension and metric, adding items, building the forest, saving to disk, and loading the index for fast lookups via memory mapping.

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

The Lua API for Annoy closely resembles the Python API. You can create an index, add items (vectors), build the trees, save the index to a file, and then load it back for fast querying using mmap.

Note: The Lua binding does not support multithreaded builds.

local annoy = require "annoy"

local f = 3
local t = annoy.AnnoyIndex(f) -- Length of item vector that will be indexed
for i = 0, 999 do
  local v = {math.random(), math.random(), math.random()}
  t:add_item(i, v)
end

t:build(10) -- 10 trees
t:save('test.ann')

-- ...

local u = annoy.AnnoyIndex(f)
u:load('test.ann') -- super fast, will just mmap the file

-- find the 10 nearest neighbors
local neighbors = u:get_nns_by_item(0, 10)
for rank, i in ipairs(neighbors) do
  print("neighbor", rank, "is", i)
end

The following methods are available on an AnnoyIndex instance:

• addItem(int item, const float* w): Adds an item with ID item and vector w.
• build(int q): Builds the index using q trees.
• save(const char* filename, bool prefault) or save(const char* filename): Saves the index to disk. Default prefault is true.
• load(const char* filename, bool prefault) or load(const char* filename): Loads an index from disk.
• unload(): Unloads the index.
• getNItems(): Returns the total number of items in the index.
• getDistance(int i, int j): Returns the distance between item i and item j.
• getItem(int item, AnnoyVectorFloat *v): Retrieves the vector for a specific item and fills v.
• onDiskBuild(const char* filename): Performs an on-disk build.