Graph-Based Nearest-Neighbor Search with Recall Guarantees Using Graph Spanners

arXiv:2607.02338 · cs.DB, cs.CL, cs.IR, cs.LG · Submitted 2026-07-02 · Read on arXiv

cs.DB, cs.CL, cs.IR, cs.LG

Submitted: 2026-07-02

Updated: 2026-11-11

Code: https://github.com/ming-afk/recall_certify_hnsw

Terminology

Sources

Related papers