← 研踪 PaperTrailarXiv:2606.00734 · v2
EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
首次提交 2026-05-30 21:56
版本更新 2026-11-05 11:27
雷达观测 2026-11-06 11:06
摘要
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.
作者备注：13 pages, 9 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-05 11:27 · 最新观测版本
EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
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.
查看此版本解读 →查看此版本原文 ↗