# CAPS: A Practical Partition Index for Filtered Similarity Search

arXiv: https://arxiv.org/abs/2308.15014 · HTML: https://mlsanity.com/paper/2308.15014/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2023.

## Built on by (most cited first, 8 of 8)

- [PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2312.03940/) (2023)
- [SQUASH: Serverless and Distributed Quantization-based Attributed Vector Similarity Search](https://mlsanity.com/paper/2502.01528/) (2025)
- [Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors](https://mlsanity.com/paper/2507.21989/) (2025)
- [Opal: Private Memory for Personal AI](https://mlsanity.com/paper/2604.02522/) (2026)
- [Text2VectorSQL: Towards a Unified Interface for Vector Search and SQL Queries](https://mlsanity.com/paper/2506.23071/) (2025)
- [Learning Filter-Aware Distance Metrics for Nearest Neighbor Search with Multiple Filters](https://mlsanity.com/paper/2511.04073/) (2025)
- [Breaking the Curse of Dimensionality: On the Stability of Modern Vector Retrieval](https://mlsanity.com/paper/2512.12458/) (2025)
- [FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances](https://mlsanity.com/paper/2605.07770/) (2026)

## Abstract (arXiv)

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.