pynsg 0.1.2

Python bindings for Navigating Spreading-Out Graph (NSG)

PyNSG

Python bindings for Navigating Spreading-Out Graph (NSG) - a fast and memory-efficient approximate nearest neighbor search algorithm.

About NSG

NSG is a graph-based approximate nearest neighbor search algorithm that provides excellent search performance with low memory overhead. This library provides Python bindings for the original C++ implementation.

Original Paper: Fast Approximate Nearest Neighbor Search with Navigating Spreading-out Graph by Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai.

Credits

This package provides Python bindings for the original NSG implementation:

• Original NSG Repository: ZJULearning/nsg
• Original Authors: Cong Fu, Chao Xiang, Changxu Wang, Deng Cai
• Python Bindings: Created to enable easy integration with Python-based machine learning workflows (such as the ANN benchmarks)

Hardware Requirements

The underlying CPP implementation of NSG requires both OpenMP and AVX2.

Installation

The knn extension requires faiss but provides an easy means of generating a knn graph in python.

pip install pynsg
pip install pynsg[knn]

Quick Start

from pynsg import NSG, Metric

nsg = NSG(dimension=128, num_points=1000, metric=Metric.L2)

# Build the index (requires a k-NN graph file - see below)
nsg.build_index(data, "knn_graph.graph", L=40, R=50, C=500)
k = 10
results = nsg.search(queries, data, k, search_L=100)

# Save and load index
nsg.save_index("my_index.nsg")
nsg2 = NSG(128, 1000, Metric.L2)
nsg2.load_index("my_index.nsg")

Optimized Search

The normal search functions above are recommended for low memory scenarios. The latter search yields better performance.

import numpy as np
from pynsg import NSG, Metric

nsg = NSG(dimension=base_data.shape[1], 
          num_points=len(base_data), 
          metric=Metric.FAST_L2)

nsg.build_index(base_data, "knn_graph.graph", L=40, R=50, C=500)
nsg.optimize_graph(base_data)
k = 10
results = nsg.search_opt(queries, k, search_L=100)

API Reference

NSG Class

NSG(dimension, num_points, metric)

Parameters:

• dimension (int): Dimensionality of the vectors
• num_points (int): Number of points in the dataset
• metric (Metric): Distance metric (L2, FAST_L2, etc.)

Methods:

• build_index(data, knn_graph_path, L, R, C): Build the NSG index
• search(queries, data, k, search_L): Search for k nearest neighbors
• search_opt(queries, k, search_L): Optimized search (requires optimize_graph)
• optimize_graph(data): Optimize the graph structure for faster search
• save_index(path): Save the index to disk
• load_index(path): Load an index from disk

Metrics

Available distance metrics:

• Metric.L2: Standard L2 (Euclidean) distance
• Metric.FAST_L2: Optimized L2 distance computation
• Metric.IP: Inner Product. If you want cosine similarity, normalize first and use IP.

Requirements

• Python 3.6+
• NumPy >= 1.16.0
• A k-NN graph file (can be generated using tools like FAISS or other ANN libraries)

Generating k-NN Graphs

NSG requires an approximate k-NN graph written to a file in a specific format as input for building the index. There are a number of ways to obtain such a graph, for example using efanna_graph (recommended by the authors of the paper), which is only available in cpp. In python, you can use faiss, or another algorithm of your choice. For convenience, if you install the extension of this package using pip install pynsg[knn], faiss will be installed and you can use the function create_graph_file that uses faiss' hnsw index to quickly build an approximate knn graph. It uses OpenMP.

This function is also exposed as a command line utility nsg-build-knn.

from pynsg import create_graph_file

create_graph_file(filename="test200.graph", x=X, k=200, use_omp=True) 

License

PyNSG is MIT-licensed. The original NSG algorithm and implementation are credited to the authors of the ZJULearning/nsg repository.

Citation

If you use this library in your research, please cite the original NSG paper:

@article{FuNSG17,
  author    = {Cong Fu and Chao Xiang and Changxu Wang and Deng Cai},
  title     = {Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphs},
  journal   = {{PVLDB}},
  volume    = {12},
  number    = {5},
  pages     = {461 - 474},
  year      = {2019},
  url       = {http://www.vldb.org/pvldb/vol12/p461-fu.pdf},
  doi       = {10.14778/3303753.3303754}
}