EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
Listen
Radio episode about this paper
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
The Chinese University of Hong Kong, Shenzhen · Microsoft Research · The Chinese University of Hong Kong
cs.DB
Submitted: 2026-05-30
Updated: 2026-11-05
Comments: 13 pages, 9 figures
Code: https://github.com/lmccccc/EMA
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 98/100
The gist: Filtering Approximate Nearest Neighbor (FANN) search is a critical and emerging task for strengthening the query capability of vector databases…
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
Summary
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. p. 0 hk
Chenhao Ma∗
The Chinese University of Hong Kong, Shenzhen
Shenzhen, China
machenhao@cuhk. cn
ABSTRACT
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. 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.Where the paper says it
Where the paper says it
Problem Motivation
Embedding-based representations have become widely adopted in applications such as retrieval-augmented generation (RAG) [8, 45, 54] <ref:2606.00734#pg2>. However, ANN search based solely on vector distance does not always meet practical application requirements <ref:2606. p. 0 XX
vector datasets, Approximate Nearest Neighbor (ANN) search has
emerged as a critical technique and has been rapidly advancing in
recent years. However, ANN search based solely on vector distance does not
always meet practical application requirements. As vector datasets
grow to millions or even billions of items, semantically similar embeddings may originate from different timestamps, data versions, or
data domains. This motivates the need for Filtering ANN (FANN)
search, which augments vector similarity search with predicate
constraints over structured attributes, ensuring that retrieved results are not only semantically relevant but also satisfy required
attribute conditions. For example, in legal document retrieval, multiple versions of a statute may be highly similar in embedding space
but apply to different effective periods; a valid retrieval must therefore select the semantically relevant provision whose effective date
attribute satisfies the temporal constraint of the case. As the predominant foundation for FANN search, modern largescale ANN systems overwhelmingly adopt graph-based indices [6,
18, 21, 27], such as HNSW [28], due to their superior recall–latency
trade-offs in high-dimensional spaces. As a result, most recent efforts on
FANN search are built upon graph-based ANN indices. Based on the types of supported predicates, existing approaches
can be broadly categorized into range-based [9, 26, 48, 55], labelbased [15, 43], and general arbitrary filtering methods [34, 39, 42].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
EMA Core Mechanism
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 <ref:2606.00734#pg2>. During query processing, EMA performs Marker-augmented joint search with a bounded edge recovery mechanism enabling efficient filtering while preserving graph navigability <ref:2606. p. 0 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. 1 Core Abstractions: Marker and Codebook
To support efficient joint search under general attribute filtering,
EMA introduces two core abstractions: the Marker and the Codebook. Together, they provide a compact and conservative edgecentric, hop-agnostic representation of predicate-relevant attribute
information associated with local graph neighborhoods, enabling
predicate prechecking during search without introducing extra
false negatives.Where the paper says it
Where the paper says it
Robustness Enhancements
To improve robustness under low-selectivity and off-cluster queries (OCQ), EMA designs a diversity-aware pruning strategy during index construction and an edge recovery mechanism at query time preserving graph navigability when predicatesatisfying points are sparse or unevenly distributed <ref:2606.00734#pg2>. The diversity-aware pruning encourages the retention of neighbors with diverse attribute values during graph construction, thereby improving graph connectivity and navigability under selective attribute filtering <ref:2606. p. 4 Motivated by this observation and prior findings that neighbor diversity is critical to graph-based ANN performance [44], we
introduce diversity-aware pruning. The core idea is to explicitly
encourage the retention of neighbors with diverse attribute values
during graph construction, thereby improving graph connectivity
and navigability under selective attribute filtering. EMA jointly leverages Marker checking and bounded edge recovery to expand the reachable search region during traversal. Markers
steer exploration toward predicate-compatible directions, while
edge recovery maintains sufficient local connectivity to enable traversal beyond the reach of post-filtering and two-hop expansion.Where the paper says it
Where the paper says it
Theoretical Guarantees
EMA preserves the asymptotic time and space complexity of the underlying HNSW index <ref:2606.00734#pg2>. The theoretical analysis derives bounds on false positives arising from dominance-based aggregation (Case 1) and codebook granularity (Case 2) <ref:2606. p. 7 These theorems establish the computational and theoretical foundations of EMA. We analyze the index construction time and space
complexity of EMA, and provide a principled characterization of
false positives arising from dominance-based aggregation (Case 1)
and codebook granularity (Case 2). and admits the upper bound that depends only on 𝜇:
FPRcase1 ≤ (1 − sel) · 1 − (1 − sel)
𝜇
. Using the average-size approximation with |𝐷(𝑒)| ≈ 𝜇,
when the dominated-set size is small (typically 𝜇 = 2–3 in practice),
the Case-(1) false positive rate remains limited. Consider a conjunctive predicate 𝑅 =
Ó𝑚
𝑗=1 𝑅𝑗 on 𝑚
attributes, and assume each 𝑅𝑗 (𝐴
(𝑗)
) is a 1D range predicate under a
contiguous Codebook partition, so that 𝑏𝑗 ≤ 2. Then Í𝑚
𝑗=1
𝑏𝑗 ≤ 2𝑚,
and Theorem 4. Discussion. The bound highlights that controlling Case-(2) false
positives mainly requires sufficient Codebook resolution when the
effective selectivity is low.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Experimental Results
Extensive experiments demonstrate that EMA achieves 1.68×–12.25× speedup over state-of-the-art general filtering ANN methods across diverse workloads <ref:2606. p. 0 Extensive experiments demonstrate that EMA
achieves 1. 25× speedup over state-of-the-art general filtering ANN methods across diverse workloads. Figure 5 reports QPS at 95%
recall with the selectivity levels ranging from 1% to 10% under
label+range queries. At low selectivity, EMA maintains stable and consistently high
throughput across all datasets, demonstrating strong robustness
when filtering predicates are highly restrictive. 25×, as shown in Table 3. • The performance gains of EMA mainly come from the combined effect of Marker checking and edge recovery, enabling
early elimination while preserving efficient graph traversal. EMA supports multi-predicate queries with both range and label constraints and achieves consistently strong performance across
a wide range of selectivities, including challenging low-selectivity
and OCQ scenarios. Moreover, EMA supports dynamic updates
with scale-aware maintenance strategies. Similar to Fresh
DiskANN [40], deleted nodes are first marked without immediate
structural updates. When deletions accumulate beyond a threshold,
EMA triggers batched patch operations to repair the graph. When only
a small fraction of the dataset satisfies the predicate constraints,
valid points become sparse, weakening local connectivity in graphbased ANN indices. As a result, many joint filtering methods fail
to maintain sufficient navigability, leading to degraded recall or
excessive search cost.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
In this paper, EMA proposes a general attribute-filtering ANN indexing framework that supports both range and label predicates with arbitrary combinations <ref:2606.00734#pg2>. EMA introduces an edge-centric, hopagnostic Marker as a compact attribute collector enabling efficient predicate-aware navigation under joint filtering <ref:2606. p. 1 At its core,
EMA introduces Marker, a compact edge-centric and geometryaware summary that enables efficient joint filtering during
graph traversal without false negatives at the Marker level. • To improve robustness under low-selectivity and off-cluster
queries, we design a diversity-aware pruning strategy during index construction and an edge recovery mechanism at
query time, preserving graph navigability when predicatesatisfying points are sparse or unevenly distributed. • The performance gains of EMA mainly come from the combined effect of Marker checking and edge recovery, enabling
early elimination while preserving efficient graph traversal. • Although false positives are allowed during Marker checking, EMA maintains a well-controlled false positive rate. • To improve robustness under low-selectivity and off-cluster
queries, we design a diversity-aware pruning strategy during index construction and an edge recovery mechanism at
query time, preserving graph navigability when predicatesatisfying points are sparse or unevenly distributed. • We design dynamic maintenance strategies for EMA, including incremental insertions, lightweight attribute updates,
and a query-guided patch mechanism that records invalid
edges encountered during traversal and repairs the graph
locally without frequent full rebuilds. 5 EXPERIMENTS
We conduct extensive experiments to evaluate the performance
of EMA under a wide range of query selectivities, predicate sizes,
attribute types, and datasets. Major results include:
• EMA achieves consistent QPS speedups ranging from 1. As the predominant foundation for FANN search, modern largescale ANN systems overwhelmingly adopt graph-based indices [6,
18, 21, 27], such as HNSW [28], due to their superior recall–latency
trade-offs in high-dimensional spaces. In contrast, tree-based [2, 4,
12, 17, 51], hashing-based [13, 19, 20] and IVF-based [7] methods
rely on explicit space partitioning and suffer from the curse of
dimensionality, while quantization-based approaches [14, 16, 23]
often trade accuracy for efficiency.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
REFERENCES
[1] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms <ref:2606. p. 0 EMA: Approximate Nearest Neighbor Search with General
Attribute Filtering and Dynamic Updates
Mocheng Li
mochengli1@link. cn
The Chinese University of Hong Kong, Shenzhen
Shenzhen, China
Baotong Lu
Microsoft Research
Beijing, China
baotonglu@microsoft.Where the paper says it
[2] Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching <ref:2606. p. 9 ACORN relies on two-hop pruning rather than RNG-style pruning,
leading to less effective searching in high-selectivity settings. VBase
adopts a relaxed monotonicity post-filtering strategy; however, its
search parameters are not configurable, and it does not consistently
achieve the 95% recall across all datasets.Where the paper says it
[3] Angela Bonifati, Wim Martens, and Thomas Timm. 2017. An analytical study of large SPARQL query logs <ref:2606.00734#pg2>
[4] Lawrence Cayton. 2008. Fast nearest neighbor retrieval for bregman divergences <ref:2606. p. 0 hk
Chenhao Ma∗
The Chinese University of Hong Kong, Shenzhen
Shenzhen, China
machenhao@cuhk. cn
ABSTRACT
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.Where the paper says it
[5] Karan Desai, Gaurav Kaul, Zubin Aysola, and Justin Johnson. 2021. Redcaps: Web-curated image-text data created by the people, for the people <ref:2606. p. 8 We sample 10M vectors from SIFT-1B and assign synthetic
numerical and categorical attributes for range and label queries. RedCaps [5] is a large-scale image–text dataset collected from
Reddit, where each data point is represented by precomputed CLIP
1https://research.Where the paper says it
[6] Wei Dong. 2011. Kgraph: A library for approximate nearest neighbor search <ref:2606. p. 0 EMA: Approximate Nearest Neighbor Search with General
Attribute Filtering and Dynamic Updates
Mocheng Li
mochengli1@link. cn
The Chinese University of Hong Kong, Shenzhen
Shenzhen, China
Baotong Lu
Microsoft Research
Beijing, China
baotonglu@microsoft.Where the paper says it
[7] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The faiss library <ref:2606. p. 0 Table 1 summarizes representative FANN approaches across different filtering stages. Pre-filtering methods,
such as iRangeGraph [48], achieve high efficiency when predicates
can be tightly embedded into the index structure, but their applicability is limited to specific attribute types or restricted predicate
arXiv:2606.Where the paper says it
[8] Darren Edge, Ha Trinh, Newman Cheng, Joshua Bradley, Alex Chao, Apurva Mody, Steven Truitt, Dasha Metropolitansky, Robert Osazuwa Ness, and Jonathan Larson. 2024. From local to global: A graph rag approach to query-focused summarization <ref:2606. p. 6 Together, these query-guided and locality-preserving updates
enable efficient graph repair while maintaining index quality. When
the deletion ratio becomes large, EMA performs a full rebuild to
restore global consistency.Where the paper says it
[9] Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters <ref:2606. p. 0 EMA: Approximate Nearest Neighbor Search with General
Attribute Filtering and Dynamic Updates
Mocheng Li
mochengli1@link. cn
The Chinese University of Hong Kong, Shenzhen
Shenzhen, China
Baotong Lu
Microsoft Research
Beijing, China
baotonglu@microsoft.Where the paper says it
[10] Mocheng Li et al. 2026. EMA: Appendix <ref:2606. p. 7 • Although false positives are allowed during Marker checking, EMA maintains a well-controlled false positive rate. More experiments are available in our appendix [10].Where the paper says it
[11] Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Salihoğlu. 2023. Kùzu graph database management system <ref:2606. p. 8 We include the following 6 baselines in our experiments:
Milvus [42] is a widely used vector database system that supports predicate filtering. It employs data partitioning to accelerate
filtered ANN search.Where the paper says it
[12] Jerome H Friedman, Jon Louis Bentley, and Raphael Ari Finkel. 1977. An algorithm for finding best matches in logarithmic expected time <ref:2606.00734#pg2>
[13] Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-sensitive hashing scheme based on dynamic collision counting <ref:2606.00734#pg2>
[14] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization <ref:2606. p. 0 As the predominant foundation for FANN search, modern largescale ANN systems overwhelmingly adopt graph-based indices [6,
18, 21, 27], such as HNSW [28], due to their superior recall–latency
trade-offs in high-dimensional spaces. In contrast, tree-based [2, 4,
12, 17, 51], hashing-based [13, 19, 20] and IVF-based [7] methods
rely on explicit space partitioning and suffer from the curse of
dimensionality, while quantization-based approaches [14, 16, 23]
often trade accuracy for efficiency.Where the paper says it
[15] Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan et al. 2023. Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters <ref:2606. p. 2 2 Graph-based ANN and RNG Pruning
Graph-based approximate nearest neighbor (ANN) methods organize data points into a proximity graph and perform greedy graph
traversal during search, achieving strong performance in highdimensional spaces. Representative systems include HNSW [28],
DiskANN [21], and FANNG [18].Where the paper says it
[16] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization <ref:2606. p. 6 EMA performs a search and updates the FT of reverse edges within
one-hop neighbors by merging the new attribute information via a
lightweight OR operation. For joint vector and attribute modifications,
EMA adopts a delete-and-insert procedure, combined with batched
patching and periodic rebuilding under large-scale updates.Where the paper says it
[17] Antonin Guttman. 1984. R-trees: A dynamic index structure for spatial searching <ref:2606. p. 0 Table 1 summarizes representative FANN approaches across different filtering stages. Pre-filtering methods,
such as iRangeGraph [48], achieve high efficiency when predicates
can be tightly embedded into the index structure, but their applicability is limited to specific attribute types or restricted predicate
arXiv:2606.Where the paper says it
[18] Ben Harwood and Tom Drummond. 2016. Fanng: Fast approximate nearest neighbour graphs <ref:2606. p. 2 2 Graph-based ANN and RNG Pruning
Graph-based approximate nearest neighbor (ANN) methods organize data points into a proximity graph and perform greedy graph
traversal during search, achieving strong performance in highdimensional spaces. Representative systems include HNSW [28],
DiskANN [21], and FANNG [18].Where the paper says it
[19] Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015. Query-aware locality-sensitive hashing for approximate nearest neighbor search <ref:2606. p. 3 3 EMA
This section presents the design of EMA, a graph-based index for
filtering-aware approximate nearest neighbor search. EMA extends
RNG-style pruning with a compact Marker that encodes predicaterelevant neighborhood information on each edge, enabling efficient
joint navigation under attribute filtering.Where the paper says it
[20] Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality <ref:2606. p. 0 As the predominant foundation for FANN search, modern largescale ANN systems overwhelmingly adopt graph-based indices [6,
18, 21, 27], such as HNSW [28], due to their superior recall–latency
trade-offs in high-dimensional spaces. In contrast, tree-based [2, 4,
12, 17, 51], hashing-based [13, 19, 20] and IVF-based [7] methods
rely on explicit space partitioning and suffer from the curse of
dimensionality, while quantization-based approaches [14, 16, 23]
often trade accuracy for efficiency.Where the paper says it
[21] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. Diskann: Fast accurate billion-point nearest neighbor search on a single node <ref:2606. p. 2 2 Graph-based ANN and RNG Pruning
Graph-based approximate nearest neighbor (ANN) methods organize data points into a proximity graph and perform greedy graph
traversal during search, achieving strong performance in highdimensional spaces. Representative systems include HNSW [28],
DiskANN [21], and FANNG [18].Where the paper says it
[22] Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011. Searching in one billion vectors: re-rank with source coding <ref:2606. p. 9 Milvus partitions the index into multiple sub-indexes, reducing its
effectiveness when a large fraction of vectors satisfy the predicates. ACORN relies on two-hop pruning rather than RNG-style pruning,
leading to less effective searching in high-selectivity settings.Where the paper says it
[23] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs <ref:2606. p. 0 As vector datasets
grow to millions or even billions of items, semantically similar embeddings may originate from different timestamps, data versions, or
data domains. This motivates the need for Filtering ANN (FANN)
search, which augments vector similarity search with predicate
constraints over structured attributes, ensuring that retrieved results are not only semantically relevant but also satisfy required
attribute conditions.Where the paper says it
[24] Andrew Kane. n.d. PGVector <ref:2606. p. 0 Table 1 summarizes representative FANN approaches across different filtering stages. Pre-filtering methods,
such as iRangeGraph [48], achieve high efficiency when predicates
can be tightly embedded into the index structure, but their applicability is limited to specific attribute types or restricted predicate
arXiv:2606.Where the paper says it
[25] Philip M Lankford. 1968. Regionalization, Theory and alternative algorithms <ref:2606. p. 1 Table 1: Comparison of FANN algorithms. Filtering Stage Algorithm Range Label Multi-predicate Low selectivity OCQ Dynamic Efficiency
Pre-filtering iRangeGraph [48] ✓ × △ ✓ ✓ × High↑
Milvus [42] ✓ ✓ ✓ △ △ ✓ Low↓
Post-filtering NHQ [43] × △ × × × × Moderate→
VBase [52] ✓ ✓ ✓ △ △ △ Low↓
Joint filtering
SeRF [55] ✓ × × × × × Moderate→
Filtered DiskANN [15] × ✓ × × × ✓ Moderate→
ACORN [34] ✓ ✓ ✓ × × △ Low↓
NaviX [39] ✓ ✓ ✓ △ △ △ Moderate→
EMA(Ours) ✓ ✓ ✓ ✓ ✓ ✓ High↑
△ indicates limited or non-robust support.Where the paper says it
[26] Anqi Liang, Pengcheng Zhang, Bin Yao, Zhongpu Chen, Yitong Song, and Guangxu Cheng. 2024. UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search <ref:2606. p. 1 Taken together, these observations reveal a
fundamental gap in existing FANN designs: there is no unified
solution for selectivity-robust approximate nearest neighbor search
with general attribute filtering. Addressing this challenge requires
an index design that 1 supports expressive, mixed predicates, 2
remains robust under extreme predicate selectivity, 3 preserves
graph navigability even when predicate-satisfying points are locally
sparse, as in OCQ scenarios, and 4 supports efficient dynamic
updates without frequent index reconstruction.Where the paper says it
[27] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs <ref:2606. p. 1 Moreover, EMA supports dynamic updates
with scale-aware maintenance strategies. Our main contributions are summarized as follows:
• We propose EMA, a filtering approximate nearest neighbor
(FANN) algorithm for expressive multi-predicate queries
over both numerical and categorical attributes.Where the paper says it
[28] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs <ref:2606. p. 1 Taken together, these observations reveal a
fundamental gap in existing FANN designs: there is no unified
solution for selectivity-robust approximate nearest neighbor search
with general attribute filtering. Addressing this challenge requires
an index design that 1 supports expressive, mixed predicates, 2
remains robust under extreme predicate selectivity, 3 preserves
graph navigability even when predicate-satisfying points are locally
sparse, as in OCQ scenarios, and 4 supports efficient dynamic
updates without frequent index reconstruction.Where the paper says it
[29] Yusuke Matsui, Ryota Hinami, and Shin’ichi Satoh. 2018. Reconfigurable Inverted Index <ref:2606. p. 0 Table 1 summarizes representative FANN approaches across different filtering stages. Pre-filtering methods,
such as iRangeGraph [48], achieve high efficiency when predicates
can be tightly embedded into the index structure, but their applicability is limited to specific attribute types or restricted predicate
arXiv:2606.Where the paper says it
[30] Yitong Meng, Xinyan Dai, Xiao Yan, James Cheng, Weiwen Liu, Jun Guo, Benben Liao, and Guangyong Chen. 2020. Pmd: An optimal transportation-based user distance for recommender systems <ref:2606. p. 0 com/lmccccc/EMA. 1 INTRODUCTION
Embedding-based representations have become widely adopted in
applications such as retrieval-augmented generation (RAG) [8, 45,
54], recommendation systems [30, 32, 35], and semantic search [33].Where the paper says it
[31] Thomas Neumann and Guido Moerkotte. 2011. Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins <ref:2606.00734#pg2>
[32] Shumpei Okura, Yukihiro Tagami, Shingo Ono, and Akira Tajima. 2017. Embedding-based news recommendation for millions of users <ref:2606. p. 0 com/lmccccc/EMA. 1 INTRODUCTION
Embedding-based representations have become widely adopted in
applications such as retrieval-augmented generation (RAG) [8, 45,
54], recommendation systems [30, 32, 35], and semantic search [33].Where the paper says it
[33] Liana Patel, Siddharth Jha, Carlos Guestrin, and Matei Zaharia. 2024. Lotus: Enabling semantic queries with llms over tables of unstructured and structured data <ref:2606. p. 0 As vector datasets
grow to millions or even billions of items, semantically similar embeddings may originate from different timestamps, data versions, or
data domains. This motivates the need for Filtering ANN (FANN)
search, which augments vector similarity search with predicate
constraints over structured attributes, ensuring that retrieved results are not only semantically relevant but also satisfy required
attribute conditions.Where the paper says it
[34] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. Acorn: Performant and predicate-agnostic search over vector embeddings and structured data <ref:2606. p. 0 As vector datasets
grow to millions or even billions of items, semantically similar embeddings may originate from different timestamps, data versions, or
data domains. This motivates the need for Filtering ANN (FANN)
search, which augments vector similarity search with predicate
constraints over structured attributes, ensuring that retrieved results are not only semantically relevant but also satisfy required
attribute conditions.Where the paper says it
[35] Arkadiusz Paterek. 2007. Improving regularized singular value decomposition for collaborative filtering <ref:2606. p. 0 Table 1 summarizes representative FANN approaches across different filtering stages. Pre-filtering methods,
such as iRangeGraph [48], achieve high efficiency when predicates
can be tightly embedded into the index structure, but their applicability is limited to specific attribute types or restricted predicate
arXiv:2606.Where the paper says it
[36] Zhencan Peng, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. [n.d.]. Dynamic Range-Filtering Approximate Nearest Neighbor Search <ref:2606. p. 0 EMA: Approximate Nearest Neighbor Search with General
Attribute Filtering and Dynamic Updates
Mocheng Li
mochengli1@link. cn
The Chinese University of Hong Kong, Shenzhen
Shenzhen, China
Baotong Lu
Microsoft Research
Beijing, China
baotonglu@microsoft. EMA: Approximate Nearest Neighbor Search with General
Attribute Filtering and Dynamic Updates
Mocheng Li
mochengli1@link. cn
The Chinese University of Hong Kong, Shenzhen
Shenzhen, China
Baotong Lu
Microsoft Research
Beijing, China
baotonglu@microsoft.Where the paper says it
Where the paper says it
[37] Zhencan Peng, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2025. Dynamic Range-Filtering Approximate Nearest Neighbor Search <ref:2606.00734#pg2>
[38] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark et al. 2021. Learning transferable visual models from natural language supervision <ref:2606. p. 0 Table 1 summarizes representative FANN approaches across different filtering stages. Pre-filtering methods,
such as iRangeGraph [48], achieve high efficiency when predicates
can be tightly embedded into the index structure, but their applicability is limited to specific attribute types or restricted predicate
arXiv:2606.Where the paper says it
[39] Gaurav Sehgal and Semih Salihoglu. 2025. NaviX: A Native Vector Index Design for Graph DBMSs With Robust Predicate-Agnostic Search Performance <ref:2606. p. 1 Taken together, these observations reveal a
fundamental gap in existing FANN designs: there is no unified
solution for selectivity-robust approximate nearest neighbor search
with general attribute filtering. Addressing this challenge requires
an index design that 1 supports expressive, mixed predicates, 2
remains robust under extreme predicate selectivity, 3 preserves
graph navigability even when predicate-satisfying points are locally
sparse, as in OCQ scenarios, and 4 supports efficient dynamic
updates without frequent index reconstruction.Where the paper says it
[40] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. 2021. Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search <ref:2606. p. 5 3 Joint Search in EMA
EMA adopts a two-stage graph search strategy. The upper layer
supports fast navigation based solely on vector distance without
attribute filtering, while the bottom layer integrates distance evaluation with attribute filtering to enable efficient joint search.Where the paper says it
[41] Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set <ref:2606. p. 2 Despite differences in index construction and search strategies, these methods share a common
structural principle: maintaining a sparse yet navigable graph through
carefully designed neighbor pruning rules. A widely adopted pruning strategy is inspired by the Relative
Neighborhood Graph (RNG) [25, 41], which promotes structural
diversity by removing neighbors that are dominated by closer ones.Where the paper says it
[42] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li et al. 2021. Milvus: A purpose-built vector data management system <ref:2606. p. 8 We include the following 6 baselines in our experiments:
Milvus [42] is a widely used vector database system that supports predicate filtering. It employs data partitioning to accelerate
filtered ANN search.Where the paper says it
[43] Mengzhao Wang, Lingwei Lv, Xiaoliang Xu, Yuxiang Wang, Qiang Yue, and Jiongkang Ni. 2024. An efficient and robust framework for approximate nearest neighbor search with attribute constraint <ref:2606. p. 1 Taken together, these observations reveal a
fundamental gap in existing FANN designs: there is no unified
solution for selectivity-robust approximate nearest neighbor search
with general attribute filtering. Addressing this challenge requires
an index design that 1 supports expressive, mixed predicates, 2
remains robust under extreme predicate selectivity, 3 preserves
graph navigability even when predicate-satisfying points are locally
sparse, as in OCQ scenarios, and 4 supports efficient dynamic
updates without frequent index reconstruction.Where the paper says it
[44] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search <ref:2606. p. 2 Table 2 summarizes the frequent notations used throughout this
paper. 2 Graph-based ANN and RNG Pruning
Graph-based approximate nearest neighbor (ANN) methods organize data points into a proximity graph and perform greedy graph
traversal during search, achieving strong performance in highdimensional spaces.Where the paper says it
[45] Shu Wang, Yixiang Fang, Yingli Zhou, Xilin Liu, and Yuchi Ma. 2025. ArchRAG: Attributed Community-based Hierarchical Retrieval-Augmented Generation <ref:2606. p. 0 com/lmccccc/EMA. 1 INTRODUCTION
Embedding-based representations have become widely adopted in
applications such as retrieval-augmented generation (RAG) [8, 45,
54], recommendation systems [30, 32, 35], and semantic search [33].Where the paper says it
[46] Weaviate. 2024. Weaviate <ref:2606. p. 0 Table 1 summarizes representative FANN approaches across different filtering stages. Pre-filtering methods,
such as iRangeGraph [48], achieve high efficiency when predicates
can be tightly embedded into the index structure, but their applicability is limited to specific attribute types or restricted predicate
arXiv:2606.Where the paper says it
[47] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: a hybrid analytical engine towards query fusion for structured and unstructured data <ref:2606. p. 0 As vector datasets
grow to millions or even billions of items, semantically similar embeddings may originate from different timestamps, data versions, or
data domains. This motivates the need for Filtering ANN (FANN)
search, which augments vector similarity search with predicate
constraints over structured attributes, ensuring that retrieved results are not only semantically relevant but also satisfy required
attribute conditions.Where the paper says it
[48] Yuexuan Xu, Jianyang Gao, Yutong Gou, Cheng Long, and Christian S Jensen. 2024. irangegraph: Improvising range-dedicated graphs for range-filtering nearest neighbor search <ref:2606. p. 0 cn
ABSTRACT
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.Where the paper says it
[49] Mingyu Yang, Wentao Li, Zhitao Shen, Chuan Xiao, and Wei Wang. 2025. ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search <ref:2606. p. 0 cn
ABSTRACT
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.Where the paper says it
[50] Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. Pase: Postgresql ultra-highdimensional approximate nearest neighbor search extension <ref:2606. p. 2 Table 2 summarizes the frequent notations used throughout this
paper. 2 Graph-based ANN and RNG Pruning
Graph-based approximate nearest neighbor (ANN) methods organize data points into a proximity graph and perform greedy graph
traversal during search, achieving strong performance in highdimensional spaces.Where the paper says it
[51] Peter Yianilos. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces <ref:2606. p. 2 Table 2 summarizes the frequent notations used throughout this
paper. 2 Graph-based ANN and RNG Pruning
Graph-based approximate nearest neighbor (ANN) methods organize data points into a proximity graph and perform greedy graph
traversal during search, achieving strong performance in highdimensional spaces.Where the paper says it
[52] Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang et al. 2023. VBASE: Unifying online vector similarity search and relational queries via relaxed monotonicity <ref:2606. p. 9 ACORN relies on two-hop pruning rather than RNG-style pruning,
leading to less effective searching in high-selectivity settings. VBase
adopts a relaxed monotonicity post-filtering strategy; however, its
search parameters are not configurable, and it does not consistently
achieve the 95% recall across all datasets.Where the paper says it
[53] Weijie Zhao, Shulong Tan, and Ping Li. 2022. Constrained approximate similarity search on proximity graph <ref:2606. p. 2 Table 2 summarizes the frequent notations used throughout this
paper. 2 Graph-based ANN and RNG Pruning
Graph-based approximate nearest neighbor (ANN) methods organize data points into a proximity graph and perform greedy graph
traversal during search, achieving strong performance in highdimensional spaces.Where the paper says it
[54] Yingli Zhou, Yaodong Su, Youran Sun, Shu Wang, Taotao Wang, Runyuan He et al. 2025. In-depth Analysis of Graph-based RAG in a Unified Framework <ref:2606. p. 1 • We design dynamic maintenance strategies for EMA, including incremental insertions, lightweight attribute updates,
and a query-guided patch mechanism that records invalid
edges encountered during traversal and repairs the graph
locally without frequent full rebuilds. • We provide a complexity analysis of EMA index construction and storage, and present a theoretical characterization
of Marker-induced false positives, clarifying when and why
Marker-based pruning remains effective.Where the paper says it
[55] Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: segment graph for range-filtering approximate nearest neighbor search <ref:2606. p. 0 cn
ABSTRACT
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.Where the paper says it
Table 3: Average speedup of EMA over the best baseline <ref:2606.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Edge Marker mechanism enables attribute-aware navigation by
encoding predicate-relevant information on each edge, providing conservative predicate- and geometric-aware guidance with zero false negatives at the Marker level.
This allows for efficient joint filtering during graph traversal without introducing false negatives at the Marker level. -
Diversity aware pruning improves graph connectivity under sparse queries by explicitly encouraging the
retention of neighbors with diverse attribute values during graph construction, thereby improving graph connectivity and navigability under selective attribute filtering.
This addresses the failure of existing methods whenpredicates satisfying points are sparse or unevenly distributed.
-
Dynamic maintenance strategies support efficient dynamic updates, including a
query-guided patch mechanism that records invalid edges encountered during traversal and repairs the graph locally without frequent full rebuilds.
This allows for efficient graph repair while maintaining index quality under dynamic workloads. -
The system can perform expressive multi-predicate queries over both numerical and categorical attributes by generalizing the aggregation of Markers from conjunctive to Boolean evaluation, enabling
flexible predicate composition with minimal changes to the framework.
This makes the system insensitive to the structure of AND/OR expressions in complex predicate combinations. -
The AI system achieves speedups ranging from 1.68x to 12.25x over state-of-the-art FANN methods across diverse workloads, demonstrating strong performance both under high selectivity and low selectivity conditions.
Abstract
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.
Sources
- 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
Related papers
- Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search
- Open Biomedical Knowledge Graphs at Scale: Construction, Federation, and AI Agent Access with Samyama Graph Database
- Samyama: A Unified Graph-Vector Database with In-Database Optimization, Agentic Enrichment, and Hardware Acceleration
- GenTUS: Table Union Search via Constrained Generation of Semantic Table Identifiers
- Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs
- SAGA: Synthetic Agentic Graph Architecture for Temporal Benchmark Generation