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...