Skip to content
Preprint

misi: a Metric Inverted Sample Index

Aug 2026 · 1 citation · 16 references
Computer Science

TL;DR

Misi is presented, an inverted index for approximate nearest-neighbor search over general metric spaces whose vocabulary is a random sample of the database, of size proportional to $n, whose design's strengths are structural and structural.

Abstract

We present misi, an inverted index for approximate nearest-neighbor search over general metric spaces whose vocabulary is a random sample of the database, of size proportional to $n$. Each object is represented by its $k_b$ nearest sample points, found by a pluggable inner index over the sample; queries are answered by an idf-weighted shared-neighbor vote followed by exact verification of $C$ candidates. The construction generalizes the NAPP index from a constant number of pivots to a linear-size vocabulary, which keeps posting lists at constant expected length $\rho = k_b/\alpha$ as $n$ grows and turns the index into a combinator: any high-recall index on $\alpha n$ points yields an index on $n$ points, for any metric. A probabilistic model gives a recall guarantee -- $k_b$ logarithmic in $n$ over the overlap gap suffices, with a verification budget the index itself estimates -- and a matching limit: the vote cannot resolve overlap differences below order $1/\sqrt{k_b}$. The design's strengths are structural: construction is $n$ independent searches -- embarrassingly parallel, deterministic, $5{,}250$ s for $10^8$ vectors on 64 cores, $3.7\times$ faster than a matched-recall graph build -- it streams under an enforced 3 GiB cap, and the portable artifact serves $10^8$ vectors from NVMe within an enforced 8 GB budget, below the working floor of the SSD-graph baseline. Its cost is query-time work: saturated graph baselines answer $6$-$16\times$ faster in RAM, and the verification budget for 0.99 recall grows as $n^{0.30}$. All results carry seeds, saturation sweeps and full configurations, are generated from run manifests, and include measured negative results. The intended applications weight construction cost, determinism, memory footprint, or black-box metrics over peak throughput: frequently rebuilt corpora, batch similarity workloads, constrained-memory serving.

View source

Similar papers

Preprint Oct 2026

SOLO: Certified-Recall Metric Similarity Search with Scan-Only Sampled Inverted Lists

In every fast nearest-neighbor index, recall is measured, never predicted: each operating point is tuned by serving it against ground truth. SOLO is an index whose recall is computed from the index itself, before any query is served. SOLO is an inverted file whose vocabulary is a random sample of the database. Each obj...

Edgar Chávez · 0 citations
Preprint Sep 2026

Transposition achieves OPT$+O(1)$ in polynomial time for IID list update

It is proved that, for arbitrary $p and arbitrary initial orderings $\sigma$ and arbitrary initial orderings $\sigma$, after polynomially many queries in the number of items, the expected cost of a query is at most $\mathsf{OPT} + O(1)$.

Clayton Mizgerd · 0 citations
Preprint Aug 2026

Sorting from Counterexamples

The optimal query complexity up to constant factors is determined: while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$.

Noga Alon, Shay Moran, S. Moran · 0 citations
Sep 2026

Matrix-Vector Complexity of Low-Rank Approximation

The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint.

Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 1 citation
Preprint Sep 2026

ZigZag Trie: A Novel Index for Contextual Queries

There is increasing interest in queries about the context of a string $P$ in a longer text $T$, i.e., the set of all string pairs $(L,R)$, with $|L|=|R|=q$, for a given $q$, such that the string $LPR$ occurs in $T$. Such contextual queries are important in several domains but are challenging to answer efficiently. This...

Ling Li, D. Gibney, S. V. Thankachan et al. · 0 citations
Preprint Aug 2026

Keeping the Index Open: The Recommendation-Side Cost of Shared Search and Recommendation

A shared search-and-recommendation index must score new items from features alone because search has no exploration slot. In a public log covering both surfaces over one catalog, $38.6\%$ of held-out query-search impressions show an item never previously shown or visited. For user-cold engagements, the feature-based to...

Theodore Rogers, Joseph Standerfer, D. Timoshenko et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.