qhjqhj00 big-ann-competition-eval
Results of the Big ANN: NeurIPS'23 competition — Simhadri et al. (2024) (arXiv:2409.17424, 2024)
What this evaluates
Evaluates approximate nearest neighbor (ANN) indexing methods across four realistic, constrained workloads: filtered search, out-of-distribution data, sparse vectors, and streaming updates. It probes the trade-off between search accuracy (recall) and query throughput under strict memory and time constraints.
Datasets
- Big ANN Challenge Datasets — total ?; splits: test (-1)
Metrics
10-recall@10(primary) — range: [0, 1]- For a query q, recall is |X ∩ G| / k, where G is the ground truth top-k neighbors and X is the predicted top-k neighbors. The metric reports the average recall over all queries in the workload.
throughput— range: other- Number of queries per second (QPS), calculated as total queries divided by the wall-clock time from vector ingestion to the output of all results.
Input / output format
Input: Dataset vectors X (optionally with tags for filtered track or as CSR matrices for sparse track) for index building; batch of query vectors Y (optionally with tags) for search.
Output: Set of indices and distances for the top-10 approximate nearest neighbors for each query in Y, along with build and search timing information.
Scoring recipe
def compute_metrics(predictions, gold, track_type):
recalls = []
for q in queries:
G = gold[q] # ground truth top-10
X = predictions[q] # predicted top-10
recalls.append(len(set(X) & set(G)) / 10)
avg_recall = sum(recalls) / len(recalls)
qps = total_queries / wall_clock_time
if track_type == 'streaming':
return avg_recall # ranked by max recall within 1hr window
else:
return qps if avg_recall >= 0.9 else None # max qps at >=90% recall
Common pitfalls
- The final leaderboard for filtered and sparse tracks uses a private query workload, so public leaderboard results may not reflect final rankings.
- Throughput is measured as wall-clock time from ingestion to final output, meaning index construction time heavily impacts the score.
- Streaming track runs are strictly limited to a 1-hour execution window; any run exceeding this is disqualified from scoring.
Evidence (verbatim from paper)
We measures 10-recall@10, with $k=k^{\prime}=10$, where recall is defined as follow.
Definition 1.
For a query vector $q$ over dataset $P$, suppose that (a) $G\subseteq P$ is the set of actual $k$ nearest neighbors in $P$, and (b) $X\subseteq P$ is the output of a $k^{\prime}$-ANNS query to an index for $k^{\prime}\geq k$ nearest neighbors. Then the ${k}$-recall$@{k^{\prime}}$ for the index for query $q$ is $\frac{|X\cap G|}{k}$. Recall for a set of queries refers to the average recall over all queries.
Throughput. We measured the overall query throughput on the standardized machine. All queries are provided at once, and the entry could use all the threads available to batch process the queries We measured the wall clock time between the ingestion of the vectors and when all the results are output. The resulting measure is the number of queries per second (QPS).
Scoring. For filtered, out-of-distribution, and sparse tasks, we measured the query throughput of each configuration, and picked the highest throughput that achieved at least 90% ${10}$-recall$@{10}$.
Citation
@misc{simhadri2024bigann,
title={Results of the Big ANN: NeurIPS'23 competition},
author={Simhadri et al. (2024)},
year={2024},
note={arXiv:2409.17424}
}
- arXiv: 2409.17424