EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
summary
The gist
Filtering Approximate Nearest Neighbor (FANN) search is a critical and emerging task for strengthening the query capability of vector databases…
In short
EMA proposes a Filtering Approximate Nearest Neighbor (FANN) algorithm to enhance vector database query capability by supporting multi-predicate searches over mixed numerical and categorical attributes. It achieves this using 'Markers' attached to graph edges for efficient, conservative filtering while maintaining fast graph navigation and supporting dynamic updates.
Key concepts
- Filtering ANN (FANN)
- A search technique that combines vector similarity search with constraints on structured data attributes. Instead of searching all vectors, it filters the candidates based on specific criteria like numerical ranges or categorical labels before performing the final distance calculation, improving relevance.
- Markers
- Compact summaries attached to graph edges that provide conservative guidance regarding attribute predicates and geometric location. These markers allow the system to efficiently filter potential neighbors during query processing without needing to examine every single node.
- Edge Recovery Mechanism
- A feature designed to restore local connectivity during query time, especially when points satisfying the predicates are sparse. This mechanism ensures that even after filtering, the search can still traverse the graph effectively, preventing loss of navigability.
Terminology used across episodes
This episode discusses
- EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates · Paper Radio
- An Analytical Study of Large SPARQL Query Logs
- RedCaps: web-curated image-text data created by the people, for the people
- The Faiss library
- From Local to Global: A Graph RAG Approach to Query-Focused Summarization
- Approximate Nearest Neighbor Search with Window Filters
- UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search
- NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance
- FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search
- A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
- ArchRAG: Attributed Community-based Hierarchical Retrieval-Augmented Generation
- ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search
- Constrained Approximate Similarity Search on Proximity Graph
- In-depth Analysis of Graph-based RAG in a Unified Framework
The paper
EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates · Read on arXiv
The Chinese University of Hong Kong, Shenzhen · Microsoft Research · The Chinese University of Hong Kong
Filtering approximate nearest neighbor search (Filtering ANNS) retrieves approximate nearest neighbors subject to attribute constraints in applications such as recommendation, retrieval-augmented generation (RAG), and LLM agent memory. However, predicate-specialized methods target either range or label filtering and can incur substantial index construction time, whereas predicate-agnostic methods support arbitrary predicates but struggle to sustain throughput and recall across a wide range of selectivities. In this paper, we propose EMA, a Filtering ANNS algorithm that supports multi-predicate queries over mixed numerical and categorical attributes as well as efficient dynamic updates. EMA attaches compact summaries, called Markers, to graph edges to record the attributes of candidates removed by geometric pruning. During query processing, EMA performs Marker-guided joint search with bounded edge recovery, enabling efficient filtering while preserving graph navigability. On multi-predicate workloads, EMA achieves 1.20x-28.18x the query throughput of the best competing baseline at comparable recall. In our complete-record replacement experiment, EMA retains approximately 98% of its initial query throughput without rebuilding the graph.
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates".
Jane: Here's the gist of the paper. 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 <ref:2606.00734#pg2>.
Tom: In this paper, EMA proposes a filtering ANN algorithm that supports multi-predicate queries over mixed numerical and categorical attributes and efficient dynamic updates <ref:2606.00734#pg2>.
Jane: Problem Motivation Embedding-based representations have become widely adopted in applications such as retrieval-augmented generation (RAG)
8, 45, 54: <ref:2606.00734#pg2>.
Tom: However, ANN search based solely on vector distance does not always meet practical application requirements <ref:2606.00734#pg2>.
Paper summary: Tom: So we’ve covered the high-level idea behind EMA, and now I want to focus on what they are actually claiming in this paper called EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates. They're proposing a filtering ANN algorithm designed to handle multi-predicate queries over mixed numerical and categorical attributes efficiently.
Jane: So, when we look at the abstract and the summary, what is their main thesis? What are they trying to prove about this EMA approach compared to existing methods like range or label filtering?
Tom: Their main claim is that existing methods are limited because they either take too long to build the index or use too much memory, and predicate agnostic approaches struggle when you have a wide range of attribute selectivity. EMA aims to solve this by introducing Markers as compact summaries attached to graph edges that provide conservative guidance about both predicates and geometry.
Lu: So what exactly are these markers? Are they just simple metadata tags, or something more structured that guides the search?
Jane: They are described as compact summaries attached to graph edges that offer conservative guidance with zero false negatives at the Marker level > They aren't just simple tags; they are meant to be a way to encode attribute information locally around where you are in the graph structure.
Meng: How does this change how we think about indexing? Are we moving from building one massive, dense graph to something more specialized for filtering?
Tom: It’s about integrating predicate checks directly into the graph traversal process, which they call joint filtering methods, rather than doing a separate filtering step after the search. This should strike a better balance between generality and efficiency compared to post-filtering systems like VBase or Faiss-HNSW >
Lalam: That sounds like they are trying to integrate the attribute checks into the graph traversal itself, which is where they feel it strikes a better balance between generality and efficiency >
Jane: So, what about the results mentioned in Table one <ref:2606.00734#pg1>? What does that comparison tell us about EMA's performance across different filtering stages?
Tom: Table one shows that for low selectivity queries and off cluster queries, methods like NaviX or ACORN perform poorly because they have limited support for general predicates > But EMA’s performance under those challenging query types remains non robust, while its joint filtering methods like ACORN and NaviX strike a better balance between generality and efficiency > <ref:2606.00734#pg1>
Lu: So the observation from Table one is that while some joint filtering methods are good in theory, they degrade when you push the selectivity hard enough, which is something we need to consider when designing systems > <ref:2606.00734#pg1>
Meng: That makes sense. If we're building a system for production, and we know our queries will be highly selective most of the time, then EMA seems like the way to go because it maintains its performance under those conditions >
Tom: Exactly. The paper argues that EMA provides a method to handle multi-predicate queries over mixed numerical and categorical attributes with efficiency while supporting efficient dynamic updates > It’s about getting high performance without sacrificing the ability to query complex constraints or keep the system updated easily.
Jane: So, what's the core message for us as listeners? What does this paper ultimately suggest about how we should be building these next-generation vector search tools?
Lu: The implication is that future systems need to move beyond just distance metrics and incorporate structured attribute knowledge directly into the way they navigate their graphs using mechanisms like Markers > It suggests that local neighborhood information can carry predicate relevance, which is a key direction for representation learning.
Meng: So, in simple terms, it means the next generation of AI search tools needs to be smarter about what attributes are relevant at any given point in the graph > It's not just about finding vectors close to you; it’s also about knowing if they match your rules >
Lalam: I’m pretty sure the conclusion is that EMA provides a filtering ANN indexing framework that supports both range and label predicates with arbitrary combinations while introducing an edge centric, hop agnostic Marker as a compact attribute collector > It really is about making the search more powerful and versatile.
Conclusion: Tom: To wrap up this discussion on EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates, the authors are presenting a general attribute-filtering ANN indexing framework. They’ve introduced Markers as an edge centric, hop agnostic collector for attributes that allows for efficient predicate aware navigation during joint filtering.
Jane: So what’s the final thought on the implications of this work? What should we be taking
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game