Pith. sign in

REVIEW 4 cited by

CAPS: A Practical Partition Index for Filtered Similarity Search

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2308.15014 v1 pith:SKF73KXG submitted 2023-08-29 cs.IR

Gaurav Gupta , Jonah Yi , Benjamin Coleman , Chen Luo , Vihan Lakshman , Anshumali Shrivastava This is my paper · ORCID
classification cs.IR
keywords annsconstrainedsearchindexalgorithmalgorithmsapproximatecaps
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Filtered Vector Search in a Disaggregated Lakehouse: Composing Table-Format Pruning with Per-File ANN

    cs.DB 2026-08 conditional novelty 6.0 of 10

    Per-file IVF indexes inside Parquet footers, combined with Iceberg file pruning, provide fast filtered ANN search in a disaggregated lakehouse when the filter column is file-local.

  2. SIEVE: Effective Filtered Vector Search with Collection of Indexes

    cs.DB 2025-07 conditional novelty 6.0 of 10

    SIEVE builds a workload-aware collection of small HNSW subindexes and uses a cost model to pick the best one per query, speeding up filtered vector search up to 8.06x versus prior graph-based methods.

  3. Simple and Fast Algorithm for Graph-based Filtered Approximate Nearest Neighbor Search (Full Version)

    cs.DB 2026-07 conditional novelty 5.0 of 10

    A labeled flat proximity graph built from full- and single-attribute partitions supports arbitrary filtered ANNS and beats UNG on 1–2 attribute queries at similar recall.

  4. Filtered Approximate Nearest Neighbor Search: A Unified Benchmark and Systematic Experimental Study [Experiment, Analysis & Benchmark]

    cs.DB 2025-09 conditional novelty 5.0 of 10

    A systematic benchmark of filtered nearest-neighbor search algorithms shows no single winner: filter-then-search methods excel at containment and equality filters, while hybrid methods dominate overlap filters.

Pith tools