misi: a Metric Inverted Sample Index 待解读
新用户看这篇论文该怎么开始
- 先点「赞助解读」，AI 会把论文转成可直接执行的行动清单。
- 看完“可执行改进行动”后，可快速决定是否值得立项。
- 用上面的卡片内容直接发给团队，减少重复阅读。
摘要
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.
分析报告
暂无报告。点击“分析”开始生成。
个性化解读 与社区共享解读不同
用自己的话告诉 AI 你想要什么样的解读（比如"用大白话讲给非专业人士听"、"重点分析对我们团队 RAG 系统的可迁移性"），生成一份只属于你自己的版本；生成后也可以选择设为"愿意共享"，被更多人看到、点赞。