NMSLIB (Non-Metric Space Library) Overview

• Repository: https://github.com/nmslib/nmslib
• Language: C++ (Python/Java/Go bindings available; Python bindings are mature, Java/Go are community-maintained)

Purpose & Use Cases

NMSLIB is a flexible, high-performance vector similarity search library focused on metric/non-metric space search for high-dimensional data. Its core design prioritizes query speed and support for non-standard similarity measures, with limited semi-real-time incremental insertion (no real-time optimization). It is NOT engineered for fully online real-time workloads (high-frequency insertion/deletion) and is suitable for:

• Approximate nearest neighbor (ANN) search over large, static/low-churn high-dimensional vector datasets.
• Scenarios where batch index building/periodic incremental updates (hourly/daily) are acceptable.
• Non-metric space search requirements (a key differentiator vs pure metric-focused engines like FAISS/NGT).

Typical applications include:

• Offline embedding retrieval for recommendation systems (precomputed user/item embeddings).
• High-dimensional feature search for image/text analytics pipelines (batch processing).
• Research/prototyping of non-metric similarity search (e.g., Jaccard for set-based features).

Algorithms Supported

• Hierarchical Navigable Small Worlds (HNSW) – core algorithm for high-speed ANN search (most widely used, metric/non-metric compatible).
• Brute-force search – baseline comparison (full vector scan, all distance types supported).
• VP-trees (Vantage Point trees) – optimized for low-dimensional data and some non-metric spaces (slower than HNSW for high-dim data).
• SW-graphs (Small World graphs) – lightweight alternative to HNSW for small datasets (<1M vectors).

Core Technical Specifications

1. Supported Metric/Non-Metric Spaces (Official Implementation Only)

NMSLIB supports a targeted set of metric/non-metric spaces (not all listed previously), with support varying by algorithm (HNSW has stricter limits than VP-tree/brute-force):

Space Type	Distance Measure	Full Name	Supported Algorithms	Use Case Scenarios
Metric	L2	Euclidean Distance	All (HNSW/VP-tree/SW-graph/brute)	General numerical vectors (image embeddings, dense float features).
Metric	L1	Manhattan Distance	VP-tree/brute-force (not HNSW)	Sparse vectors, tabular data feature comparison.
Metric	Cosine	Cosine Similarity/Distance	All (HNSW/VP-tree/SW-graph/brute)	Text embeddings, direction-based vector comparison.
Non-Metric	Jaccard	Jaccard Similarity/Distance	VP-tree/brute-force (not HNSW)	Set-based vectors (boolean/sparse features, e.g., bag-of-words).
Non-Metric	Hamming	Hamming Distance	VP-tree/brute-force (not HNSW)	Binary vectors (bitwise features, hash-based retrieval).
Custom	User-Defined	Custom Distance Functions	Brute-force/VP-tree (limited HNSW)	Domain-specific similarity (e.g., time-series via C++ custom code).

Critical Notes:

1. HNSW (NMSLIB’s core fast algorithm) ONLY supports L2/Cosine – no L1/Jaccard/Hamming (this is the most common misperception).
2. L∞ (Chebyshev)、Inner Product、Edit Distance are NOT natively supported – Inner Product can be simulated via L2 after normalization, Edit Distance requires full custom implementation.
3. Python bindings only expose L2/Cosine/Jaccard/Hamming (L1 is C++-only), custom distance functions are C++-only.

2. Supported Data Types (Official Implementation Only)

NMSLIB has narrow data type support (no official Float16/Int64 support), with optimization focused on 32-bit floats:

Data Type	Precision	C++ Type	Python Binding Mapping	Support Status	Use Case
Float32	32-bit	float	numpy.float32	Fully supported (optimal performance)	Default – balance of speed/memory/precision.
Float64 (Double)	64-bit	double	numpy.float64	Fully supported (slower than Float32)	High-precision scientific computing vectors.
Float16 (FP16)	16-bit	-	numpy.float16	Not supported (no official code)	Manual conversion to Float32 is possible but has no memory/performance benefit.
Int32	32-bit	int32_t	numpy.int32	Limited support (only L1/L2 distance)	Discrete count-based vectors (e.g., sparse features).
Int64	64-bit	int64_t	numpy.int64	Not supported (no official implementation)	No native handling – requires custom C++ wrapping.
Binary	Bit-level	uint8_t (packed)	numpy.uint8 (bitpacked)	Supported (only Hamming distance)	Binary vectors (bitwise features, e.g., bloom filters).

Key Notes:

1. Float16: NMSLIB has no native FP16 computation/storage – earlier "FP16 support" was incorrect (community hacks are unmaintained and not production-grade).
2. Binary vectors: Only work with Hamming distance, require explicit bitpacking via NMSLIB’s BinaryVector utility (Python bindings have helper functions).
3. Python bindings enforce Float32/Float64/Int32/Binary – other types throw type errors.

3. Real-Time Data Insertion/Deletion Support

NMSLIB’s dynamic update capabilities are semi-supported for low-frequency workloads but fundamentally unsuitable for strict online real-time scenarios (consistent with official limitations):

Operation	Support Level	Details & Constraints
Incremental Insertion	Partial support (semi-real-time, HNSW only)	- HNSW index supports incremental insertion, but each insertion requires graph rebalancing (latency: ~0.1ms/vector for small indexes → 10ms+/vector for 100M+ vectors). - No batch async insertion API – high-frequency single inserts trigger lock contention. - Maximum sustainable write QPS: ~500 (vs 10k+ for real-time engines like Milvus).
Real-Time Deletion	Minimal support (non-production grade)	- No native deletion API for any index type – users must mark vectors as "deleted" and filter results post-query. - Physical removal of deleted vectors requires full index rebuild (no incremental cleanup). - Deleted vectors bloat index memory and slow query performance by 30%+ over time.
Vector Modification	No direct support	- Modification requires deleting the original vector (mark as invalid) and re-inserting the updated version – inherits all deletion/insertion latency constraints.

Critical Note: NMSLIB’s incremental insertion is functional but not optimized for real-time use – it lacks core real-time features like in-memory write buffers, asynchronous index flushing, or distributed write handling.

Characteristics

Feature	Description
Incremental Updates	Partial incremental insertion (HNSW only); deletion/modification not supported (mark-only).
Query Speed	Industry-leading for static indexes (HNSW is 2-5x faster than basic NSW; Float32 > Float64); non-metric search is slower than metric.
Index Type	Hybrid (graph-based: HNSW/SW-graph; tree-based: VP-trees; brute-force).
Scalability	Handles 100M+ vectors with disk-backed storage (memory footprint ~50% lower than NGT for Float32 vectors).
Language Bindings	C++ (full feature set), Python (mature, limited to L2/Cosine/Jaccard/Hamming), Java/Go (community-maintained, minimal functionality).
Non-Metric Support	Native support for Jaccard/Hamming (VP-tree/brute-force only) – unique vs NGT/FAISS/HNSWLIB.

Notes

• NMSLIB is optimized for offline/static workloads – its strength is fast query performance on pre-built indexes and non-metric space support, not dynamic real-time updates.
• For semi-real-time use cases (hourly batch updates), HNSW incremental insertion is usable but requires limiting index size to <10M vectors to avoid latency spikes.
• HNSW (NMSLIB’s fastest algorithm) only supports L2/Cosine – use VP-tree/brute-force if Jaccard/Hamming is required (tradeoff: slower query speed).
• Float32 is the only type for optimal performance – Float64 is 2-3x slower with no meaningful precision gain for most embeddings.
• Real-time alternative: For dynamic workloads requiring fast queries + real-time writes, pair NMSLIB (static historical data) with Milvus/PGVector (real-time hot data) or switch to FAISS with IVF-HNSW.
• Limitations: No distributed mode (single-node only), poor production documentation, limited community maintenance (last major update in 2022), Python bindings lack custom distance support.