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

arXiv:2606.00734 · cs.DB · Submitted 2026-05-30 · Read on arXiv

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

Where the paper says it

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.

00734#pg2>. 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. p. 0
Where the paper says it

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.

00734#pg2>.

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

Where the paper says it

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.

00734#pg2>. This motivates the need for Filtering ANN (FANN) search, which augments vector similarity search with predicate constraints over structured attributes <ref:2606. p. 0
Where the paper says it

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.

00734#pg2>. Modern largescale ANN systems overwhelmingly adopt graph-based indices [6, 18, 21, 27] due to their superior recall–latency trade-offs in high-dimensional spaces <ref:2606. p. 0
Where the paper says it

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.

00734#pg2>. Existing approaches can be broadly categorized into range-based [9, 26, 48, 55], labelbased [15, 43], and general arbitrary filtering methods [34, 39, 42] <ref:2606. p. 0
Where the paper says it

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].

00734#pg2>.

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

Where the paper says it

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.

00734#pg2>. The core abstractions are the Marker and the Codebook, which provide a compact and conservative edgecentric, hop-agnostic representation of predicate-relevant attribute information associated with local graph neighborhoods <ref:2606. p. 3
Where the paper says it

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.

00734#pg2>.

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

Where the paper says it

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.

00734#pg2>. Furthermore, EMA incorporates a lightweight edge recovery mechanism to restore sufficient local connectivity to enable traversal beyond the reach of post-filtering and two-hop expansion <ref:2606. p. 5
Where the paper says it

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.

00734#pg2>.

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

Where the paper says it

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).

00734#pg2>. Theorem 4.5 provides an upper bound for the expected Case-(1) false positive rate based only on the average dominated-set size <ref:2606. p. 7
Where the paper says it

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.

00734#pg2>. Similarly, Theorem 4. p. 7
Where the paper says it

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.

6 establishes a sufficient condition for bounding Case-(2) false positives by controlling Codebook resolution <ref:2606. p. 7
Where the paper says it

Discussion. The bound highlights that controlling Case-(2) false positives mainly requires sufficient Codebook resolution when the effective selectivity is low.

00734#pg2>.

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

Where the paper says it

Extensive experiments demonstrate that EMA achieves 1. 25× speedup over state-of-the-art general filtering ANN methods across diverse workloads.

00734#pg2>. EMA consistently achieves the highest QPS across all datasets under high selectivity, and maintains stable and consistently high throughput across all datasets at low selectivity <ref:2606. p. 9
Where the paper says it

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.

00734#pg2>. The performance gains mainly come from the combined effect of Marker checking and edge recovery enabling early elimination while preserving efficient graph traversal <ref:2606. p. 7
Where the paper says it

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.

00734#pg2>. EMA also supports dynamic updates with low overhead, requiring only 1. p. 1
Where the paper says it

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.

3 s and 2.5 s per 1M operations for deletions and attribute-only updates <ref:2606. p. 6
Where the paper says it

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.

00734#pg2>. EMA consistently satisfies the recall requirement under off-clustering query conditions where other methods fail to reach the target recall <ref:2606. p. 1
Where the paper says it

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.

00734#pg2>.

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

Where the paper says it

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.

00734#pg2>. The Marker construction is theoretically guaranteed to avoid introducing false negatives during Marker checking while bounding the false positive rate <ref:2606. p. 7
Where the paper says it

• 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.

00734#pg2>. To further enhance graph connectivity EMA incorporates an edge recovery mechanism supporting patch for dynamic updates and delays costly reconstruction while maintaining stable performance <ref:2606. p. 1
Where the paper says it

• 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.

00734#pg2>. Extensive experiments demonstrate that EMA consistently delivers strong performance across a wide range of workloads achieving speedups of 1. p. 7
Where the paper says it

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.

68×–12.25× over existing methods while maintaining high recall <ref:2606. p. 0
Where the paper says it

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.

00734#pg2>.

REFERENCES

[1] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANNBenchmarks: A benchmarking tool for approximate nearest neighbor algorithms <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[2] Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching <ref:2606. p. 9

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[6] Wei Dong. 2011. Kgraph: A library for approximate nearest neighbor search <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[9] Joshua Engels, Benjamin Landrum, Shangdi Yu, Laxman Dhulipala, and Julian Shun. 2024. Approximate Nearest Neighbor Search with Window Filters <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[10] Mocheng Li et al. 2026. EMA: Appendix <ref:2606. p. 7

Where the paper says it

• Although false positives are allowed during Marker checking, EMA maintains a well-controlled false positive rate. More experiments are available in our appendix [10].

00734#pg2>

[11] Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Salihoğlu. 2023. Kùzu graph database management system <ref:2606. p. 8

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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].

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[17] Antonin Guttman. 1984. R-trees: A dynamic index structure for spatial searching <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[18] Ben Harwood and Tom Drummond. 2016. Fanng: Fast approximate nearest neighbour graphs <ref:2606. p. 2

Where the paper says it

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].

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[20] Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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].

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[23] Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with GPUs <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[24] Andrew Kane. n.d. PGVector <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[25] Philip M Lankford. 1968. Regionalization, Theory and alternative algorithms <ref:2606. p. 1

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[29] Yusuke Matsui, Ryota Hinami, and Shin’ichi Satoh. 2018. Reconfigurable Inverted Index <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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].

00734#pg2>

[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

Where the paper says it

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].

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[35] Arkadiusz Paterek. 2007. Improving regularized singular value decomposition for collaborative filtering <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

p. 0
Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[41] Godfried T Toussaint. 1980. The relative neighbourhood graph of a finite planar set <ref:2606. p. 2

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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].

00734#pg2>

[46] Weaviate. 2024. Weaviate <ref:2606. p. 0

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[50] Wen Yang, Tao Li, Gai Fang, and Hong Wei. 2020. Pase: Postgresql ultra-highdimensional approximate nearest neighbor search extension <ref:2606. p. 2

Where the paper says it

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.

00734#pg2>

[51] Peter Yianilos. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces <ref:2606. p. 2

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

[53] Weijie Zhao, Shulong Tan, and Ping Li. 2022. Constrained approximate similarity search on proximity graph <ref:2606. p. 2

Where the paper says it

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.

00734#pg2>

[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

Where the paper says it

• 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.

00734#pg2>

[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

Where the paper says it

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.

00734#pg2>

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

  1. 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.

  2. 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 when predicates satisfying points are sparse or unevenly distributed.

  3. 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.

  4. 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.

  5. 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

Related papers