Bug: MultiIndex returns strange search results

USearch

Smaller & Faster Single-File
Similarity Search Engine for Vectors & 🔜 Texts

Spatial • Binary • Probabilistic • User-Defined Metrics
C++ 11 • Python 3 • JavaScript • Java • Rust • C 99 • Objective-C • Swift • C# • GoLang • Wolfram
Linux • MacOS • Windows • iOS • WebAssembly • SQLite3

✅ 10x faster HNSW implementation than FAISS.
✅ Simple and extensible single C++11 header library.
✅ Trusted by giants like Google and databases like ClickHouse.
✅ SIMD-optimized and user-defined metrics with JIT compilation.
✅ Hardware-agnostic f16 & i8 - half-precision & quarter-precision support.
✅ View large indexes from disk without loading into RAM.
✅ Heterogeneous lookups, renaming/relabeling, and on-the-fly deletions.
✅ Binary Tanimoto and Sorensen coefficients for Genomics and Chemistry applications.
✅ Space-efficient point-clouds with uint40_t, accommodating 4B+ size.
✅ Compatible with OpenMP and custom "executors" for fine-grained parallelism.
✅ Semantic Search and Joins.
🔄 Near-real-time clustering and sub-clustering for Tens or Millions of clusters.

Technical Insights and related articles:

Comparison with FAISS

FAISS is a widely recognized standard for high-performance vector search engines. USearch and FAISS both employ the same HNSW algorithm, but they differ significantly in their design principles. USearch is compact and broadly compatible without sacrificing performance, primarily focusing on user-defined metrics and fewer dependencies.

	FAISS	USearch	Improvement
Indexing time ⁰
100 Million 96d `f32`, `f16`, `i8` vectors	2.6 · 2.6 · 2.6 h	0.3 · 0.2 · 0.2 h	9.6 · 10.4 · 10.7 x
100 Million 1536d `f32`, `f16`, `i8` vectors	5.0 · 4.1 · 3.8 h	2.1 · 1.1 · 0.8 h	2.3 · 3.6 · 4.4 x

Codebase length ¹	84 K SLOC	3 K SLOC	maintainable
Supported metrics ²	9 fixed metrics	any metric	extendible
Supported languages ³	C++, Python	10 languages	portable
Supported ID types ⁴	32-bit, 64-bit	32-bit, 40-bit, 64-bit	efficient
Filtering ⁵	ban-lists	any predicates	composable
Required dependencies ⁶	BLAS, OpenMP	-	light-weight
Bindings ⁷	SWIG	Native	low-latency
Python binding size ⁸	~ 10 MB	< 1 MB	deployable

⁰ Tested on Intel Sapphire Rapids, with the simplest inner-product distance, equivalent recall, and memory consumption while also providing far superior search speed. ¹ A shorter codebase of usearch/ over faiss/ makes the project easier to maintain and audit. ² User-defined metrics allow you to customize your search for various applications, from GIS to creating custom metrics for composite embeddings from multiple AI models or hybrid full-text and semantic search. ³ With USearch, you can reuse the same preconstructed index in various programming languages. ⁴ The 40-bit integer allows you to store 4B+ vectors without allocating 8 bytes for every neighbor reference in the proximity graph. ⁵ With USearch the index can be combined with arbitrary external containers, like Bloom filters or third-party databases, to filter out irrelevant keys during index traversal. ⁶ Lack of obligatory dependencies makes USearch much more portable. ⁷ Native bindings introduce lower call latencies than more straightforward approaches. ⁸ Lighter bindings make downloads and deployments faster.

Base functionality is identical to FAISS, and the interface must be familiar if you have ever investigated Approximate Nearest Neighbors search:

$ pip install numpy usearch

import numpy as np
from usearch.index import Index

index = Index(ndim=3)

vector = np.array([0.2, 0.6, 0.4])
index.add(42, vector)

matches = index.search(vector, 10)

assert matches[0].key == 42
assert matches[0].distance <= 0.001
assert np.allclose(index[42], vector, atol=0.1) # Ensure high tolerance in mixed-precision comparisons

More settings are always available, and the API is designed to be as flexible as possible.

index = Index(
    ndim=3, # Define the number of dimensions in input vectors
    metric='cos', # Choose 'l2sq', 'haversine' or other metric, default = 'ip'
    dtype='f32', # Quantize to 'f16' or 'i8' if needed, default = 'f32'
    connectivity=16, # Optional: Limit number of neighbors per graph node
    expansion_add=128, # Optional: Control the recall of indexing
    expansion_search=64, # Optional: Control the quality of the search
    multi=False, # Optional: Allow multiple vectors per key, default = False
)

Serialization & Serving `Index` from Disk

USearch supports multiple forms of serialization:

Into a file defined with a path.
Into a stream defined with a callback, serializing or reconstructing incrementally.
Into a buffer of fixed length or a memory-mapped file that supports random access.

The latter allows you to serve indexes from external memory, enabling you to optimize your server choices for indexing speed and serving costs. This can result in 20x cost reduction on AWS and other public clouds.

index.save("index.usearch")

loaded_copy = index.load("index.usearch")
view = Index.restore("index.usearch", view=True)

other_view = Index(ndim=..., metric=...)
other_view.view("index.usearch")

Exact vs. Approximate Search

Approximate search methods, such as HNSW, are predominantly used when an exact brute-force search becomes too resource-intensive. This typically occurs when you have millions of entries in a collection. For smaller collections, we offer a more direct approach with the search method.

from usearch.index import search, MetricKind, Matches, BatchMatches
import numpy as np

# Generate 10'000 random vectors with 1024 dimensions
vectors = np.random.rand(10_000, 1024).astype(np.float32)
vector = np.random.rand(1024).astype(np.float32)

one_in_many: Matches = search(vectors, vector, 50, MetricKind.L2sq, exact=True)
many_in_many: BatchMatches = search(vectors, vectors, 50, MetricKind.L2sq, exact=True)

If you pass the exact=True argument, the system bypasses indexing altogether and performs a brute-force search through the entire dataset using SIMD-optimized similarity metrics from SimSIMD. When compared to FAISS's IndexFlatL2 in Google Colab, USearch may offer up to a 20x performance improvement:

faiss.IndexFlatL2: 55.3 ms.
usearch.index.search: 2.54 ms.

User-Defined Metrics

While most vector search packages concentrate on just two metrics, "Inner Product distance" and "Euclidean distance", USearch allows arbitrary user-defined metrics. This flexibility allows you to customize your search for various applications, from computing geospatial coordinates with the rare Haversine distance to creating custom metrics for composite embeddings from multiple AI models, like joint image-text embeddings. You can use Numba, Cppyy, or PeachPy to define your custom metric even in Python:

from numba import cfunc, types, carray
from usearch.index import Index, MetricKind, MetricSignature, CompiledMetric

@cfunc(types.float32(types.CPointer(types.float32), types.CPointer(types.float32)))
def python_inner_product(a, b):
    a_array = carray(a, ndim)
    b_array = carray(b, ndim)
    c = 0.0
    for i in range(ndim):
        c += a_array[i] * b_array[i]
    return 1 - c

metric = CompiledMetric(pointer=python_inner_product.address, kind=MetricKind.IP, signature=MetricSignature.ArrayArray)
index = Index(ndim=ndim, metric=metric, dtype=np.float32)

Similar effect is even easier to achieve in C, C++, and Rust interfaces. Moreover, unlike older approaches indexing high-dimensional spaces, like KD-Trees and Locality Sensitive Hashing, HNSW doesn't require vectors to be identical in length. They only have to be comparable. So you can apply it in obscure applications, like searching for similar sets or fuzzy text matching, using GZip compression-ratio as a distance function.

Filtering and Predicate Functions

Sometimes you may want to cross-reference search-results against some external database or filter them based on some criteria. In most engines, you'd have to manually perform paging requests, successively filtering the results. In USearch you can simply pass a predicate function to the search method, which will be applied directly during graph traversal. In Rust that would look like this:

let is_odd = |key: Key| key % 2 == 1;
let query = vec![0.2, 0.1, 0.2, 0.1, 0.3];
let results = index.filtered_search(&query, 10, is_odd).unwrap();
assert!(
    results.keys.iter().all(|&key| key % 2 == 1),
    "All keys must be odd"
);

Memory Efficiency, Downcasting, and Quantization

Training a quantization model and dimension-reduction is a common approach to accelerate vector search. Those, however, are only sometimes reliable, can significantly affect the statistical properties of your data, and require regular adjustments if your distribution shifts. Instead, we have focused on high-precision arithmetic over low-precision downcasted vectors. The same index, and add and search operations will automatically down-cast or up-cast between f64_t, f32_t, f16_t, i8_t, and single-bit representations. You can use the following command to check, if hardware acceleration is enabled:

$ python -c 'from usearch.index import Index; print(Index(ndim=768, metric="cos", dtype="f16").hardware_acceleration)'
> sapphire
$ python -c 'from usearch.index import Index; print(Index(ndim=166, metric="tanimoto").hardware_acceleration)'
> ice

Using smaller numeric types will save you RAM needed to store the vectors, but you can also compress the neighbors lists forming our proximity graphs. By default, 32-bit uint32_t is used to enumerate those, which is not enough if you need to address over 4 Billion entries. For such cases we provide a custom uint40_t type, that will still be 37.5% more space-efficient than the commonly used 8-byte integers, and will scale up to 1 Trillion entries.

`Indexes` for Multi-Index Lookups

For larger workloads targeting billions or even trillions of vectors, parallel multi-index lookups become invaluable. Instead of constructing one extensive index, you can build multiple smaller ones and view them together.

from usearch.index import Indexes

multi_index = Indexes(
    indexes: Iterable[usearch.index.Index] = [...],
    paths: Iterable[os.PathLike] = [...],
    view: bool = False,
    threads: int = 0,
)
multi_index.search(...)

Clustering

Once the index is constructed, USearch can perform K-Nearest Neighbors Clustering much faster than standalone clustering libraries, like SciPy, UMap, and tSNE. Same for dimensionality reduction with PCA. Essentially, the Index itself can be seen as a clustering, allowing iterative deepening.

clustering = index.cluster(
    min_count=10, # Optional
    max_count=15, # Optional
    threads=..., # Optional
)

# Get the clusters and their sizes
centroid_keys, sizes = clustering.centroids_popularity

# Use Matplotlib to draw a histogram
clustering.plot_centroids_popularity()

# Export a NetworkX graph of the clusters
g = clustering.network

# Get members of a specific cluster
first_members = clustering.members_of(centroid_keys[0])

# Deepen into that cluster, splitting it into more parts, all the same arguments supported
sub_clustering = clustering.subcluster(min_count=..., max_count=...)

The resulting clustering isn't identical to K-Means or other conventional approaches but serves the same purpose. Alternatively, using Scikit-Learn on a 1 Million point dataset, one may expect queries to take anywhere from minutes to hours, depending on the number of clusters you want to highlight. For 50'000 clusters, the performance difference between USearch and conventional clustering methods may easily reach 100x.

Joins, One-to-One, One-to-Many, and Many-to-Many Mappings

One of the big questions these days is how AI will change the world of databases and data management. Most databases are still struggling to implement high-quality fuzzy search, and the only kind of joins they know are deterministic. A join differs from searching for every entry, requiring a one-to-one mapping banning collisions among separate search results.

Exact Search	Fuzzy Search	Semantic Search ?
Exact Join	Fuzzy Join ?	Semantic Join ??

Using USearch, one can implement sub-quadratic complexity approximate, fuzzy, and semantic joins. This can be useful in any fuzzy-matching tasks common to Database Management Software.

men = Index(...)
women = Index(...)
pairs: dict = men.join(women, max_proposals=0, exact=False)

Read more in the post: Combinatorial Stable Marriages for Semantic Search 💍

Functionality

By now, the core functionality is supported across all bindings. Broader functionality is ported per request. In some cases, like Batch operations, feature parity is meaningless, as the host language has full multi-threading capabilities and the USearch index structure is concurrent by design, so the users can implement batching/scheduling/load-balancing in the most optimal way for their applications.

	C++ 11	Python 3	C 99	Java	JavaScript	Rust	GoLang	Swift
Add, search, remove	✅	✅	✅	✅	✅	✅	✅	✅
Save, load, view	✅	✅	✅	✅	✅	✅	✅	✅
User-defined metrics	✅	✅	✅	❌	❌	❌	❌	❌
Batch operations	❌	✅	❌	❌	✅	❌	❌	❌
Filter predicates	✅	❌	✅	❌	❌	✅	❌	❌
Joins	✅	✅	❌	❌	❌	❌	❌	❌
Variable-length vectors	✅	❌	❌	❌	❌	❌	❌	❌
4B+ capacities	✅	❌	❌	❌	❌	❌	❌	❌

Application Examples

USearch + AI = Multi-Modal Semantic Search

AI has a growing number of applications, but one of the coolest classic ideas is to use it for Semantic Search. One can take an encoder model, like the multi-modal UForm, and a web-programming framework, like UCall, and build a text-to-image search platform in just 20 lines of Python.

import ucall
import uform
import usearch

import numpy as np
import PIL as pil

server = ucall.Server()
model = uform.get_model('unum-cloud/uform-vl-multilingual')
index = usearch.index.Index(ndim=256)

@server
def add(key: int, photo: pil.Image.Image):
    image = model.preprocess_image(photo)
    vector = model.encode_image(image).detach().numpy()
    index.add(key, vector.flatten(), copy=True)

@server
def search(query: str) -> np.ndarray:
    tokens = model.preprocess_text(query)
    vector = model.encode_text(tokens).detach().numpy()
    matches = index.search(vector.flatten(), 3)
    return matches.keys

server.run()

A more complete demo with Streamlit is available on GitHub. We have pre-processed some commonly used datasets, cleaned the images, produced the vectors, and pre-built the index.

Dataset	Modalities	Images	Download
Unsplash	Images & Descriptions	25 K	HuggingFace / Unum
Conceptual Captions	Images & Descriptions	3 M	HuggingFace / Unum
Arxiv	Titles & Abstracts	2 M	HuggingFace / Unum

USearch + RDKit = Molecular Search

Comparing molecule graphs and searching for similar structures is expensive and slow. It can be seen as a special case of the NP-Complete Subgraph Isomorphism problem. Luckily, domain-specific approximate methods exist. The one commonly used in Chemistry is to generate structures from SMILES and later hash them into binary fingerprints. The latter are searchable with binary similarity metrics, like the Tanimoto coefficient. Below is an example using the RDKit package.

from usearch.index import Index, MetricKind
from rdkit import Chem
from rdkit.Chem import AllChem

import numpy as np

molecules = [Chem.MolFromSmiles('CCOC'), Chem.MolFromSmiles('CCO')]
encoder = AllChem.GetRDKitFPGenerator()

fingerprints = np.vstack([encoder.GetFingerprint(x) for x in molecules])
fingerprints = np.packbits(fingerprints, axis=1)

index = Index(ndim=2048, metric=MetricKind.Tanimoto)
keys = np.arange(len(molecules))

index.add(keys, fingerprints)
matches = index.search(fingerprints, 10)

That method was used to build the "USearch Molecules", one of the largest Chem-Informatics datasets, containing 7 billion small molecules and 28 billion fingerprints.

USearch + POI Coordinates = GIS Applications... on iOS?

With Objective-C and Swift iOS bindings, USearch can be easily used in mobile applications. The SwiftVectorSearch project illustrates how to build a dynamic, real-time search system on iOS. In this example, we use 2-dimensional vectors—encoded as latitude and longitude—to find the closest Points of Interest (POIs) on a map. The search is based on the Haversine distance metric but can easily be extended to support high-dimensional vectors.

Integrations

Citations

@software{Vardanian_USearch_2023,
doi = {10.5281/zenodo.7949416},
author = {Vardanian, Ash},
title = {{USearch by Unum Cloud}},
url = {https://github.com/unum-cloud/usearch},
version = {2.11.7},
year = {2023},
month = oct,
}

	#if !defined(USEARCH_USE_NATIVE_F16)
	#if defined(__AVX512F__)
	#define USEARCH_USE_NATIVE_F16 1
	#elif defined(USEARCH_DEFINED_ARM)
	#define USEARCH_USE_NATIVE_F16 1
	#else
	#define USEARCH_USE_NATIVE_F16 0
	#include <fp16/fp16.h>
	#endif
	#else
	#define USEARCH_USE_NATIVE_F16 0
	#include <fp16/fp16.h>
	#endif

	def metadata(path: os.PathLike) -> Optional[dict]:
	if not os.path.exists(path):
	return None
	try:
	return _index_dense_metadata(path)
	except Exception:
	return None

	func (index *Index) Load(path string) error {
	if index.opaque_handle == nil {
	panic("Index is uninitialized")
	}

	c_path := C.CString(path)
	defer C.free(unsafe.Pointer(c_path))

	var errorMessage *C.char
	C.usearch_load((C.usearch_index_t)(unsafe.Pointer(index.opaque_handle)), c_path, (*C.usearch_error_t)(&errorMessage))
	if errorMessage != nil {
	return errors.New(C.GoString(errorMessage))
	}
	return nil
	}

unum-cloud / usearch Goto Github PK

usearch's Introduction

USearch

Smaller & Faster Single-File Similarity Search Engine for Vectors & 🔜 Texts

Comparison with FAISS

Serialization & Serving Index from Disk

Exact vs. Approximate Search

User-Defined Metrics

Filtering and Predicate Functions

Memory Efficiency, Downcasting, and Quantization

Indexes for Multi-Index Lookups

Clustering

Joins, One-to-One, One-to-Many, and Many-to-Many Mappings

Functionality

Application Examples

USearch + AI = Multi-Modal Semantic Search

USearch + RDKit = Molecular Search

USearch + POI Coordinates = GIS Applications... on iOS?

Integrations

Citations

usearch's People

Contributors

Stargazers

Watchers

Forkers

usearch's Issues

Describe the bug

Steps to reproduce

Expected behavior

USearch version

Operating System

Hardware architecture

Which interface are you using?

Contact Details

Is there an existing issue for this?

Code of Conduct

Describe the bug

Steps to reproduce

Expected behavior

USearch version

Operating System

Hardware architecture

Which interface are you using?

Contact Details

Is there an existing issue for this?

Code of Conduct

Describe the bug

Steps to reproduce

Expected behavior

USearch version

Operating System

Hardware architecture

Which interface are you using?

Contact Details

Is there an existing issue for this?

Code of Conduct

Describe the bug

Steps to reproduce

Expected behavior

USearch version

Operating System

Hardware architecture

Which interface are you using?

Contact Details

Is there an existing issue for this?

Code of Conduct

Describe the bug

Steps to reproduce

Expected behavior

USearch version

Operating System

Hardware architecture

Which interface are you using?

Contact Details

Is there an existing issue for this?

Code of Conduct

Describe what you are looking for

Can you contribute to the implementation?

Is your feature request specific to a certain interface?

Contact Details

Smaller & Faster Single-File
Similarity Search Engine for Vectors & 🔜 Texts

Serialization & Serving `Index` from Disk

`Indexes` for Multi-Index Lookups