Prépublication · 2026
CapCover Filter: Semantic Approximate Membership Queries over Embeddings
Dvir David Biton, Shay Hahiashvili et al. — Monde
Source : arXiv
Résumé
Determining whether an embedding is sufficiently similar to any vector in a vector store without performing a nearest-neighbor search can substantially improve query throughput in vector-store systems. We study Semantic Approximate Membership Queries (SAMQs), which allow queries to be rejected when no indexed vector meets the requested similarity threshold, while guaranteeing no false negatives. We introduce CapCover Filter, a geometric data structure that summarizes a set of embeddings using spherical caps. Its representation is independent of the query threshold, allowing a single filter to…