Hann is a high-performance approximate nearest neighbor search (ANN) library for Go. It provides a collection of index data structures for efficient similarity search in high-dimensional spaces. Currently, supported indexes include Hierarchical Navigable Small World (HNSW), Product Quantization Inverted File (PQIVF), and Random Projection Tree (RPT).

Hann can be seen as a core component of a vector database (like Milvus, Pinecone, Weaviate, Qdrant, etc.). It can be used to add fast in-memory similarity search capabilities to your Go applications.

• Unified interface for different indexes (see core/index.go)
• Support for indexing and searching vectors of arbitrary dimension
• Fast distance computation using SIMD (AVX) instructions (see core/simd_distance.c)
• Support for bulk insertion, deletion, and update of vectors
• Support for saving indexes to disk and loading them back

• $n$: number of vectors
• $d$: number of dimensions (vector length)
• $M$: links per node (HNSW)
• $k$: number of clusters (PQIVF)
• $i$: iterations for clustering (PQIVF)

The HNSW index supports the use of Euclidean, squared Euclidean, Manhattan, and cosine distances. If cosine distance is used, the vectors are normalized on read (before they are used in the index or for search). Note that squared Euclidean distance is slightly faster to compute than Euclidean distance and gives the same order of closest vectors as Euclidean distance. It can be used in place of Euclidean distance if only the order of closest vectors to query vector is needed, not the actual distances.

The PQIVF and RPT indexes support Euclidean distance only.

Hann can be installed as a typical Go module using the following command:

go get github.com/habedi/hann@main

Hann requires Go 1.21 or later, a C (or C++) compiler, and a CPU that supports AVX instructions.

Use the following commands to download the datasets used in the examples:

# Only needed to run the examples that use large datasets
make download-data-large

Note that to run the examples using large datasets, possibly a machine with large amounts of memory is needed like 32 GB or more.

Check the data directory for information about the datasets.

The detailed documentation for Hann packages is available on pkg.go.dev.

The hnsw package provides an implementation of the HNSW graph index introduced by Malkov and Yashunin (2016). HNSW organizes data into multiple layers of a proximity graph, which allows fast approximate nearest neighbor searches by greedily traversing the graph from top to bottom.

The index has the following parameters:

• M: Controls the maximum number of neighbor connections per node. Higher values improve accuracy but increase memory and indexing time (typical range: 5–48).
• Ef: Defines search breadth during insertion and searching. Higher values improve accuracy but increase computational cost (typical range: 10–200).

The pqivf package provides an implementation of the PQIVF index introduced by Jegou et al. (2011). PQIVF first clusters data into coarse groups (inverted lists), then compresses vectors in each cluster using product quantization. This allows fast approximate nearest neighbor searches by limiting queries to relevant clusters and efficiently comparing compressed vectors, which reduces search time and storage requirements.

The index has the following parameters:

• coarseK: Controls the number of coarse clusters for initial quantization. Higher values improve search performance but increase indexing time (typical range: 50–4096).
• numSubquantizers: Determines the number of subspaces for product quantization. More subquantizers improve compression and accuracy at the cost of increased indexing time (typical range: 4–16).
• pqK: Sets the number of codewords per subquantizer. Higher values increase accuracy and storage usage (typical value: 256).
• kMeansIters: Number of iterations used to train the product quantization codebooks (recommended value: 25).

The rpt package provides an implementation of the RPT index introduced by Dasgupta and Freund (2008). RPT recursively partitions data using randomly generated hyperplanes to build a tree structure, which allows efficient approximate nearest neighbor searches through a tree traversal process.

The index has the following parameters:

• leafCapacity: Controls the maximum number of vectors stored in each leaf node. Lower values increase tree depth, improving search speed but slightly increasing indexing time (typical range: 5–50).
• candidateProjections: Number of random projections considered at each tree split. Higher values improve split quality at the cost of increased indexing time (typical range: 1–10).
• parallelThreshold: Minimum number of vectors in a subtree to trigger parallel construction. Higher values lead to better concurrency during indexing but use more memory (typical value: 100).
• probeMargin: Margin used to determine additional branches probed during searches. Higher values improve recall but increase search overhead because of additional distance computations (typical range: 0.1–0.5).

The verbosity level of logs produced by Hann can be controlled using the HANN_LOG environment variable. Possible values include:

• 0, false, or off to disable logging altogether;
• full or all to enable full logging (DEBUG level);
• Use any other value (including not setting the HANN_LOG environment variable) to enable basic logging (INFO level; default behavior).

For more consistent indexing and search results across different runs, set the HANN_SEED environment variable to an integer. This will initialize the random number generator, but some variations are still possible (for example, due to multithreading).

See CONTRIBUTING.md for details on how to make a contribution.

The logo is named the "Hiking Gopher" and was created by Egon Elbre.

Hann is licensed under the MIT License (LICENSE).