Solo builds a fast memory-efficient tool for accurate nearest-neighbor search
SOLO: Certified-Recall Metric Similarity Search with Scan-Only Sampled Inverted Lists
DatabasesInformation Retrieval
Summary
Large databases often require finding items that are closest or most similar to a given query quickly. The authors introduce SOLO, a new method that avoids complicated ranking steps and still guarantees highly accurate recall by scanning selected samples. SOLO organizes data so that searching does not need guessing or approximations, making the results provably correct when measured on stored samples. The paper shows SOLO performs well on massive datasets, using less memory while matching or exceeding speed compared to popular previous tools.
What this means in practice
- •For search engine developers: Integrate SOLO to improve memory usage and recall accuracy for large-scale similarity search in recommendation and search services.
- •For database engineers: Use SOLO to enable efficient inserts and deletes while maintaining high recall on metric space queries in large data environments.
Authors
Édgar Chávez
Abstract
We present SOLO, an index for approximate nearest-neighbor search in general metric spaces whose serving path contains no ranking heuristic of any kind: a query is routed to the $k_s$ nearest points of a random sample of the database, and every object in the touched posting lists is evaluated with the true distance. Because nothing must outrank anything, recall equals a coverage probability computable from the stored index: one ground-truth pass over a query sample certifies every operating point at once, without serving any of them -- a recall certificate, and for a navigable graph no analogous object exists at any price. The whole index is one recursive rule -- sample the collection, post each object to its $b$ nearest sample points, split any list that outgrows a bound, always scan the leaves -- and its operating surface obeys an equal-work law, recall $\approx f(b \cdot k_s)$, whose level is a one-scalar signature of the dataset. The same scan-only structure gives a serving floor no graph architecture reaches once the router is itself indexed by the same rule: Deep-100M served at recall 0.9977 from 1 GB of resident memory (enforced cap, 10.7 bytes per object) and at 0.9964 from 256 MB, Deep-1B at recall 0.9925 from 512 MB (and from 96 MB at depth 3), inserts that are one search, and deletes that are exact. Throughput is competitive where the hardware allows it -- up to $1.8\times$ a tuned HNSW at $10^8$ on a two-socket 32-core server, with operating points to the right of where that graph saturates -- and the tables report it against HNSW, DiskANN, GRAFT, NAPP, misi, and SPANN's assignment rule on the same hardware and ground truth.