misi: a Metric Inverted Sample Index

• URL: http://arxiv.org/abs/2608.27422v1
• Date: Thu, 27 Aug 2026 17:48:22 GMT
• Title: misi: a Metric Inverted Sample Index
• Abstract summary: misi is an inverted index for approximate nearest-neighbor search over general metric spaces.<n>Each object is represented by its $k_b$ nearest sample points, found by a pluggable inner index over the sample.<n> queries are answered by an idf-weighted shared-neighbor vote followed by exact verification of $C$ candidates.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $ρ= k_b/α$ as $n$ grows and turns the index into a combinator: any high-recall index on $α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.

Related papers

• A Spectral Phase Diagram for Binary Few-Shot Classification: Intrinsic Dimensionality, Geometric Saturation, and Representational Diagnosis [0.0]
  The saturation index $S(K) = operatornameerank(widehat_W(K)) / K$ measures the ratio of the effective rank of the pooled within-class sample covariance to the shot count.<n>The index is computable in $O(d3)$ time from support features alone, requiring no test labels or trained classifier.
  arXiv  Detail & Related papers  (2026-06-12T16:46:24Z)
• Neural Scalable Symbolic Search Framework for Complex Logical Queries with Multiple Free Variables [55.952069550106906]
  Complex Query Answering (CQA) is a fundamental knowledge representation and reasoning task over incomplete knowledge graphs (KGs)<n>It requires ranking answers in $mathcalEk$, where $mathcalEk$ denotes the entity set of a KG.<n>Existing benchmarks and methods rely on marginal rankings over individual variables; however, marginal rankings are a poor proxy for the true joint ranking of variables.<n>We propose Neural Scalable Symbolic Search (NS3), a framework that approximates joint ranking without enumerating $mathcalEk$.
  arXiv  Detail & Related papers  (2026-05-25T16:04:57Z)
• Represented Is Not Computed: A Causal Test of Candidate Algorithmic Intermediates in a Transformer [0.0]
  A Transformer trained on base-digit extraction is shown to reach 99.83% exact-answer accuracy on held-out number-base intersections.<n>A sparse circuit search finds mostly separate $N$, $B$, and $D$ routes that combine late rather than the staged route suggested by the probes.
  arXiv  Detail & Related papers  (2026-05-21T13:43:25Z)
• The Library Theorem: How External Organization Governs Agentic Reasoning Capacity [0.0]
  We formalize the transformer context window as an I/O page.<n>We prove that tool-augmented agents with indexed external memory achieve exponentially lower retrieval cost than agents restricted to sequential scanning.
  arXiv  Detail & Related papers  (2026-03-22T15:02:56Z)
• Prune, Don't Rebuild: Efficiently Tuning $α$-Reachable Graphs for Nearest Neighbor Search [7.168741876130465]
  We propose RP-Tuning to adjust the $$ parameter without reconstructing the full index.<n>We show that RP-Tuning accelerates DiskANN tuning on four public datasets by up to $43times$ with negligible overhead.
  arXiv  Detail & Related papers  (2026-02-08T19:34:38Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
  arXiv  Detail & Related papers  (2025-06-30T13:27:39Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring.<n>We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• Data Structures for Density Estimation [66.36971978162461]
  Given a sublinear (in $n$) number of samples from $p$, our main result is the first data structure that identifies $v_i$ in time sublinear in $k$. We also give an improved version of the algorithm of Acharya et al. that reports $v_i$ in time linear in $k$.
  arXiv  Detail & Related papers  (2023-06-20T06:13:56Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  We study the fundamental task of list-decodable mean estimation in high dimensions. Our algorithm runs in time $widetildeO(ndk)$ for all $k = O(sqrtd) cup Omega(d)$, where $n$ is the size of the dataset. A variant of our algorithm has runtime $widetildeO(ndk)$ for all $k$, at the expense of an $O(sqrtlog k)$ factor in the recovery guarantee
  arXiv  Detail & Related papers  (2020-11-19T17:21:37Z)
• Deep Learning Meets Projective Clustering [66.726500395069]
  A common approach for compressing NLP networks is to encode the embedding layer as a matrix $AinmathbbRntimes d$. Inspired by emphprojective clustering from computational geometry, we suggest replacing this subspace by a set of $k$ subspaces.
  arXiv  Detail & Related papers  (2020-10-08T22:47:48Z)
• Faster DBSCAN via subsampled similarity queries [42.93847281082316]
  DBSCAN is a popular density-based clustering algorithm. We propose SNG-DBSCAN, which clusters based on a subsampled $epsilon$-neighborhood graph.
  arXiv  Detail & Related papers  (2020-06-11T18:57:54Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.