Home

Neighborhood Graph and Tree for Indexing High-dimensional Data

NGT provides commands and a library for performing high-speed approximate nearest neighbor searches against a large volume of data (several million to several 10 million items of data) in high dimensional vector data space.

Key Features

• Supported operating systems: Linux and macOS
• Object additional registration and removal are available.
• Objects beyond the memory size can be handled using the shared memory (memory mapped file) option.
• Supported distance functions: L1, L2, Cosine similarity, Angular, Hamming, and Jaccard
• Data Types: 4 byte floating point number and 1 byte unsigned integer (binary data)
• Supported languages: Python, Ruby, Rust, Go, C++, and C
• Distributed servers: ngtd and vald
• NGTQ can handle billions of objects.

Utilities

• Command : ngt and ngtq
• Server : ngtd and vald

Supported Programming Languages

• Python
• Ruby (Thanks Andrew!)
• Rust (Thanks Romain!)
• Go
• C++ (sample code)
• C (C APIs)

Index Structure

Search Flow

1. Seeds Acquisition

2. Graph Exploration

Publications

ONNG

• Iwasaki, M., Miyazaki, D.: Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity. arXiv:1810.07355 [cs] (2018). (pdf)

PANNG

• Iwasaki, M.: Pruned Bi-directed K-nearest Neighbor Graph for Proximity Search. Proc. of SISAP2016 (2016) 20-33. (pdf)
• Sugawara, K., Kobayashi, H. and Iwasaki, M.: On Approximately Searching for Similar Word Embeddings. Proc. of ACL2016 (2016) 2265-2275. (pdf)

ANNGT

• Iwasaki, M.: Applying a Graph-Structured Index to Product Image Search (in Japanese). IIEEJ Journal 42(5) (2013) 633-641. (pdf)
• Iwasaki, M.: Proximity search using approximate k nearest neighbor graph with a tree structured index (in Japanese). IPSJ Journal 52(2) (2011) 817-828. (pdf)

ANNG

• Iwasaki, M.: Proximity search in metric spaces using approximate k nearest neighbor graph (in Japanese). IPSJ Trans. on Database 3(1) (2010) 18-28. (pdf)