repository·master·Indexed 26 days ago
https://github.com/nmslib/hnswlibA lightweight, header-only C++ implementation of Hierarchical Navigable Small World (HNSW) graphs for fast approximate nearest neighbor search. It features high-performance Python bindings and supports incremental index construction, updates, deletions, and serialization. Supported distance metrics include Squared L2, Inner product, and Cosine distance.
You can install the Python bindings using pip:
pip install hnswlibAlternatively, you can install from source:
apt-get install -y python-setuptools python-pip
git clone https://github.com/nmslib/hnswlib.git
cd hnswlib
pip install .pip install hnswlibYou can persist the index to disk or use Python's pickle module.
save_index(path_to_index): Saves the index to a file.load_index(path_to_index, max_elements=0, allow_replace_deleted=False): Loads an index from a file into an uninitialized index.pickle: Index objects are picklable.WARNING: Serialization via pickle.dumps(p) or p.__getstate__() is NOT thread-safe if p.add_items is being called simultaneously.
Hnswlib supports marking elements as deleted so they are omitted from search results without immediate removal from memory.
mark_deleted(label): Marks an element as deleted. Throws an exception if the element is already deleted.unmark_deleted(label): Restores a deleted element to the search results.replace_deleted=True (in add_items): If the index was initialized with allow_replace_deleted=True, new insertions can reuse the slots of deleted elements to save memory.The ef parameter controls the trade-off between query time and accuracy. A higher ef leads to better accuracy but slower search.
Note: The ef parameter is included in serialization, but it is not automatically saved with the index via save_index. You must manually call set_ef(ef) after loading an index.
p.set_ef(50) # ef should always be > kYou can control the recall (accuracy) of an HNSW index at search time by setting the ef parameter using set_ef(ef).
ef: Leads to better accuracy (higher recall) but results in slower search performance.ef: Results in faster search performance but lower accuracy.Use add_items(data, ids, num_threads=-1, replace_deleted=False) to insert vectors.
data: A numpy array of vectors with shape (N, dim).ids: (Optional) A numpy array of integer labels for the elements. If an ID already exists, the features will be updated.num_threads: Number of CPU threads to use (-1 for default).replace_deleted: If True, replaces elements marked as deleted (requires allow_replace_deleted=True in init_index).Thread Safety: add_items is thread-safe with other add_items calls, but not thread-safe with knn_query.
p.add_items(data, ids)Use knn_query(data, k=1, num_threads=-1, filter=None) to find the k closest elements for each vector in data (shape N, dim).
k: Number of closest elements to return.filter: Filters elements by their labels. Note: Search with a filter in Python is slow in multithreaded mode; it is recommended to set num_threads=1 when using a filter.Returns: Two numpy arrays (labels and distances) of shape (N, k).
Thread Safety: knn_query is thread-safe with other knn_query calls, but not thread-safe with add_items.
labels, distances = p.knn_query(data, k=1)Use hnswlib.Index(space, dim) to create a non-initialized index. Then, call init_index to prepare it for data insertion. You must specify the maximum number of elements beforehand.
Parameters for init_index:
max_elements: Maximum number of elements the structure can store (can be increased/shrunk via resize_index).M: Maximum number of outgoing connections in the graph.ef_construction: Construction time/accuracy trade-off.random_seed: Seed for the random number generator.allow_replace_deleted: If True, enables replacing deleted elements with new ones to control index size.import hnswlib
import numpy as np
dim = 128
num_elements = 10000
p = hnswlib.Index(space='l2', dim=dim)
p.init_index(max_elements=num_elements, ef_construction=200, M=16)To evaluate the quality (recall) of an HNSW index, you can compare its results against a BFIndex (Brute Force Index). The BFIndex stores vectors as-is and performs an exhaustive search, providing the ground truth for the actual k nearest neighbors.
Initialization:
Use hnswlib.BFIndex(space, dim) to create a non-initialized index. space can be 'l2', 'cosine', or 'ip'.
Key Methods:
init_index(max_elements): Initializes the index. max_elements defines the capacity; exceeding this during insertion will throw an exception.add_items(data, ids=None): Inserts data (numpy array of shape N*dim). ids is an optional numpy array of integer labels.delete_vector(label): Removes the element associated with the given label from search results.knn_query(data, k=1): Performs a batch query for the k closest elements for each vector in data (shape N*dim). Returns a numpy array of shape (N, k) containing labels.save_index(path_to_index): Saves the index to disk.load_index(path_to_index, max_elements=0): Loads an index from disk into an uninitialized index.import hnswlib
import numpy as np
dim = 32
num_elements = 100000
k = 10
nun_queries = 10
# Generating sample data
data = np.float32(np.random.random((num_elements, dim)))
# Declaring index
hnsw_index = hnswlib.Index(space='l2', dim=dim)
bf_index = hnswlib.BFIndex(space='l2', dim=dim)
# Initing both hnsw and brute force indices
hnsw_index.init_index(max_elements=num_elements, ef_construction=200, M=16)
bf_index.init_index(max_elements=num_elements)
# Controlling the recall for hnsw by setting ef:
hnsw_index.set_ef(200)
# Set number of threads used during batch search/construction
hnsw_index.set_num_threads(1)
hnsw_index.add_items(data)
bf_index.add_items(data)
# Generating query data
query_data = np.float32(np.random.random((nun_queries, dim)))
# Query the elements and measure recall:
labels_hnsw, distances_hnsw = hnsw_index.knn_query(query_data, k)
labels_bf, distances_bf = bf_index.knn_query(query_data, k)
# Measure recall
correct = 0
for i in range(nun_queries):
for label in labels_hnsw[i]:
for correct_label in labels_bf[i]:
if label == correct_label:
correct += 1
break
print("recall is :", float(correct)/(k*nun_queries))Use the following methods to inspect the index contents:
get_items(ids, return_type='numpy'): Returns vectors for the specified ids. If return_type='list', returns a list of lists. For cosine space, it returns normalized vectors.get_ids_list(): Returns a list of all element IDs currently in the index.get_max_elements(): Returns the current capacity of the index.get_current_count(): Returns the number of elements currently stored.When building the HNSW index, use these parameters to control memory usage, build time, and index quality:
M: The number of bi-directional links created for every new element.M improves performance on high-dimensional datasets or when high recall is required, but increases memory consumption (roughly M * 8-10 bytes per stored element).dim=4 random vectors, M≈6 is optimal. For high-dimensional data like word embeddings, use M=48-64.ef_construction: Controls index-time accuracy.ef_construction leads to longer construction times but higher index quality.ef_construction is sufficient, measure recall for an M-nearest neighbor search where ef = ef_construction. If recall is below 0.9, consider increasing ef_construction.num_elements: Defines the maximum number of elements allowed in the index. The index can be extended by saving and loading it using the load_index function with a new maximum element parameter.When initializing an hnswlib.Index, you can specify one of the following distance spaces:
| Distance | parameter | Equation |
|---|---|---|
| Squared L2 | 'l2' | d = sum((Ai-Bi)^2) |
| Inner product | 'ip' | d = 1.0 - sum(Ai*Bi) |
| Cosine distance | 'cosine' | d = 1.0 - sum(Ai*Bi) / sqrt(sum(Ai*Ai) * sum(Bi*Bi)) |
Note: Inner product is not an actual metric. For other spaces, use the nmslib library.