CAPS: A Practical Partition Index for Filtered Similarity Search
read the original abstract
With the surging popularity of approximate near-neighbor search (ANNS), driven by advances in neural representation learning, the ability to serve queries accompanied by a set of constraints has become an area of intense interest. While the community has recently proposed several algorithms for constrained ANNS, almost all of these methods focus on integration with graph-based indexes, the predominant class of algorithms achieving state-of-the-art performance in latency-recall tradeoffs. In this work, we take a different approach and focus on developing a constrained ANNS algorithm via space partitioning as opposed to graphs. To that end, we introduce Constrained Approximate Partitioned Search (CAPS), an index for ANNS with filters via space partitions that not only retains the benefits of a partition-based algorithm but also outperforms state-of-the-art graph-based constrained search techniques in recall-latency tradeoffs, with only 10% of the index size.
This paper has not been read by Pith yet.
Forward citations
Cited by 4 Pith papers
-
Query-aware Routing for Filtered Approximate Nearest Neighbors Search
A machine-learned router predicts per-query recall for filtered ANN methods and selects the recall-QPS optimal one, outperforming fixed baselines on five unseen datasets.
-
Efficient Graph Indexing for Interval-Aware Vector Search
URNG and UG enable a single graph index for diverse interval-aware ANN queries by preserving monotonic searchability and structural heredity.
-
FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances
FAVOR achieves 1.3-5x higher QPS at 95% Recall@10 for arbitrary filtered ANNS by combining exclusion-distance reshaping in HNSW graphs with a selectivity-driven router that switches between brute-force and optimized search.
-
Opal: Private Memory for Personal AI
Opal enables private long-term memory for personal AI by decoupling reasoning to a trusted enclave with a lightweight knowledge graph and piggybacking reindexing on ORAM accesses.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.