mlsanityData to 7 Oct 2026

Approximate Nearest Neighbor Search with Window Filters

arXiv 2402.00943 ↗First posted 1 Feb 2024cs.DS cs.IR cs.LGcited by 11

Not on the map. Why?

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.

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

Builds on

13 of 34 references.

References · 13

  1. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,456
  2. 2023GPT-4 Technical Reportcited by 18,132
  3. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
  4. 2023Check Your Facts and Try Again: Improving Large Language Models with External Knowledge and Automated Feedbackcited by 351
  5. 2021RedCaps: web-curated image-text data created by the people, for the peoplecited by 175
  6. 2018ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithmscited by 130
  7. 2023ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithmscited by 24
  8. 2023Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitationscited by 20
  9. 2018Hardness of Approximate Nearest Neighbor Searchcited by 19
  10. 2019Graph-based Nearest Neighbor Search: From Practice to Theorycited by 19
  11. 2023PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Searchcited by 3
  12. 2023Faster Parallel Exact Density Peaks Clusteringcited by 2
1 more
  1. 2020Practical Trade-Offs for the Prefix-Sum Problemcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 7.

11 papers.

  1. 2025Advancing Decoding Strategies: Enhancements in Locally Typical Sampling for LLMscited by 4
  2. 2025Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectorscited by 2
  3. 2026Opal: Private Memory for Personal AIcited by 1
  4. 2025Text2VectorSQL: Towards a Unified Interface for Vector Search and SQL Queriescited by 0
  5. 2025Breaking the Curse of Dimensionality: On the Stability of Modern Vector Retrievalcited by 0
  6. 2026CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Datacited by 0
  7. 2026FAVOR: Efficient Filter-Agnostic Vector ANNS Based on Selectivity-Aware Exclusion Distancescited by 0
  8. 2026EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updatescited by 0
  9. 2026Query-aware Routing for Filtered Approximate Nearest Neighbors Searchcited by 0
  10. 2026ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Searchcited by 0
  11. 2026A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrievalcited by 0