# Approximate Nearest Neighbor Search with Window Filters

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 34 references that are in the map.
- First posted on arXiv 1 Feb 2024.

## Builds on (most cited first, 13 of 13)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Check Your Facts and Try Again: Improving Large Language Models with External Knowledge and Automated Feedback](https://mlsanity.com/paper/2302.12813/) (2023)
- [RedCaps: web-curated image-text data created by the people, for the people](https://mlsanity.com/paper/2111.11431/) (2021)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Hardness of Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1803.00904/) (2018)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2312.03940/) (2023)
- [Faster Parallel Exact Density Peaks Clustering](https://mlsanity.com/paper/2305.11335/) (2023)
- [Practical Trade-Offs for the Prefix-Sum Problem](https://mlsanity.com/paper/2006.14552/) (2020)

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

- [Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMs](https://mlsanity.com/paper/2506.05387/) (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)
- [Breaking the Curse of Dimensionality: On the Stability of Modern Vector Retrieval](https://mlsanity.com/paper/2512.12458/) (2025)
- [CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data](https://mlsanity.com/paper/2604.06616/) (2026)
- [FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distances](https://mlsanity.com/paper/2605.07770/) (2026)
- [EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates](https://mlsanity.com/paper/2606.00734/) (2026)
- [Query-aware Routing for Filtered Approximate Nearest Neighbors Search](https://mlsanity.com/paper/2606.19898/) (2026)
- [ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2607.17582/) (2026)
- [A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval](https://mlsanity.com/paper/2609.19855/) (2026)

## Abstract (arXiv)

We define and investigate the problem of textitc-approximate window search: approximate nearest neighbor search where each point in the dataset has a numeric label, and the goal is to find nearest neighbors to queries within arbitrary label ranges. Many semantic search problems, such as image and document search with timestamp filters, or product search with cost filters, are natural examples of this problem. We propose and theoretically analyze a modular tree-based framework for transforming an index that solves the traditional c-approximate nearest neighbor problem into a data structure that solves window search. On standard nearest neighbor benchmark datasets equipped with random label values, adversarially constructed embeddings, and image search embeddings with real timestamps, we obtain up to a 75× speedup over existing solutions at the same level of recall.