# EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Vector search and ANN indexes, one of 15 directions in Retrieval-augmented generation.
- Builds on 12 of its 47 references that are in the map.
- First posted on arXiv 30 May 2026.

## Placed in

- Retrieval-augmented generation / [Vector search and ANN indexes](https://mlsanity.com/rag/vector-search-and-ann-indexes/)

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [In-depth Analysis of Graph-based RAG in a Unified Framework](https://mlsanity.com/paper/2503.04338/) (2025)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data](https://mlsanity.com/paper/2403.04871/) (2024)
- [An Analytical Study of Large SPARQL Query Logs](https://mlsanity.com/paper/1708.00363/) (2017)
- [Approximate Nearest Neighbor Search with Window Filters](https://mlsanity.com/paper/2402.00943/) (2024)
- [UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search](https://mlsanity.com/paper/2412.02448/) (2024)
- [NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance](https://mlsanity.com/paper/2506.23397/) (2025)

## Abstract (arXiv)

Filtering Approximate Nearest Neighbor (FANN) search is a critical and emerging task for strengthening the query capability of vector databases, supporting applications such as recommendation systems, retrieval-augmented generation (RAG), and agent memory. However, most existing methods are limited to range or label filtering, often incurring unacceptable index construction time and memory overhead. Predicate-agnostic approaches further struggle to handle a wide range of predicate selectivities effectively. In this paper, we propose EMA, a filtering ANN algorithm that supports multi-predicate queries over mixed numerical and categorical attributes, and efficient dynamic updates. EMA introduces Markers as compact summaries attached to graph edges, providing conservative predicate- and geometric-aware guidance with zero false negatives at the Marker level. During query processing, EMA performs Marker-augmented joint search with a bounded edge recovery mechanism, enabling efficient filtering while preserving graph navigability. Extensive experiments demonstrate that EMA achieves 1.68x--12.25x speedup over state-of-the-art general filtering ANN methods across diverse workloads.