Simple and Fast Algorithm for Graph-based Filtered Approximate Nearest Neighbor Search (Full Version) Reon Uemura1[0009−0004−2563−5720] , Keito Kido1[0009−0007−8550−3844] , and Daichi Amagata1[0000−0001−8571−4931]
arXiv:2607.24173v1 [cs.DB] 27 Jul 2026
The University of Osaka, Osaka, Japan {uemura.reon, kido.keito, amagata.daichi}@ist.osaka-u.ac.jp
Abstract. It has been common to represent many objects as highdimensional vectors due to the proliferation of machine learning-based embedding techniques. One of the most important functions for analyzing high-dimensional vectors is approximate nearest neighbor search, which, given a query vector, retrieves the vector that is approximately the most similar to the query vector. In many real-world applications, such as e-commerce, objects have not only vectors but also attributes, e.g., category, color, and brand, and they require a scenario where users can specify a query vector and a value for each attribute of interest. This problem, called filtered approximate nearest neighbor search, retrieves approximate nearest neighbors from a set of objects that have the specified attribute values. Efficiently solving this problem is challenging because it has to accept arbitrary query vectors and attribute values, which are not known in advance. Existing techniques suffer from slow search performance and difficulty in dealing with arbitrary combinations of attributes. This work overcomes these challenges and proposes a new algorithm for this problem. We conduct extensive experiments, and the results demonstrate the efficiency of our algorithm. Keywords: Approximate nearest neighbor search · attribute filter · approximation algorithm.
1
Introduction
Because of the proliferation of machine learning-based embedding techniques, many objects, e.g., images and documents, are usually represented as highdimensional vectors. Along with this observation, vector database management systems, such as Milvus [28], are becoming more important. One of the most important functions in these systems is approximate k nearest neighbor search (AkNNS), which, given a query vector q, a result size k, and a set X of vectors, retrieves k vectors ∈ X that are approximately the most similar to q. As the AkNNS problem finds many real-world applications, such as clustering [1], EMST [14], and RAG, existing works have studied efficient algorithms. It
2
Uemura et al.
is well known that obtaining the exact nearest neighbor in high dimensions is time-consuming [16], so they focus on approximate answers. In some real-world applications, more complex retrieval scenarios are required [5,11,15,20,25,26,30]. A typical setting is attribute filtering. Each object is associated with a vector and attributes, and a filtered AkNNS retrieves k objects such that their vectors are approximately the most similar to q among a set of objects that have the specified attribute values. For example, in e-commerce applications, users want to search for products that are similar to their query and have a specific color and size [12]. Motivation: challenges in existing techniques. Standard baseline algorithms for the filtered AkNNS problem are Pre-filter [28], Post-filter [34], and Inline processing [11]. Pre-filter first retrieves all objects that have the specified attribute values and then computes the k nearest neighbors among them. Although Pre-filter can obtain the exact answer, it is efficient only when the number of objects with the specified attribute values is small. Post-filter builds a vanilla ANNS index offline, and given a query vector q and k, it runs an AkNNS algorithm on the index. If some objects in the result do not have the specified attribute values, Post-filter increases k and re-runs AkNNS, which is repeated until k objects having the attribute values are obtained. This approach may run AkNNS many times, which incurs a substantial computational cost. To alleviate this cost, Inline processing computes the distance between q and x only when x has the specified attribute values. Inline processing, however, still accesses many unnecessary objects, thus its improvement is limited. Another approach to removing this concern is to build an index for each possible combination of attribute values, but it consumes an infeasible space and is impractical. Some existing works improve the performance of filtered ANNS against the above baselines. CAPS [12] employs a hybrid approach of Pre-filter and Inlineprocessing. Its building block is a decision tree based on the frequency of attribute values. NHQ [30] defines a distance between attributes and combines it with the distance between vectors. A proximity graph is built based on this fused distance. However, their applications are limited because they assume that queries always specify one value for every attribute. This assumption is usually not the case because, for example, users typically specify only size and color for the attribute constraint, although objects often have additional attributes (such as brand and price). FilteredVamana [11] is a variant of Vamana [23] that considers the attribute values of each object. In FilteredVamana, two objects (or vectors) are connected if they are similar and share at least one attribute value. FilteredVamana implicitly assumes that each object has a single attribute, as its original implementation suggests. When each object has multiple attributes, the above connection approach does not guarantee that a given query can traverse a path (i.e., a set of objects) that has the specified attribute values. Acorn [20] and HQANN [31] also have this drawback. The current state-of-the-art algorithm, UNG [5], removes the above limitations and outperforms them. UNG builds (i) a trie tree based on attributes and (ii) a proximity graph for each object set with the same attribute values. Then,
Simple and Fast Algorithm for Graph-based Filtered ANNS
3
based on the connections in the trie tree, traversing between proximity graphs is enabled. When the number of specified attributes is large, UNG traverses only some proximity graphs, so its search performance is good. However, when the number of specified attributes is small, which is a typical case in practice, UNG needs to traverse many proximity graphs, degrading the search performance. Contribution. This work overcomes the above limitations so that arbitrary filtered ANNS can be done efficiently, and we make the following contributions. – We propose a novel framework for filtered ANNS. This framework allows for an arbitrary flat proximity graph (e.g., KNN graph [7] and NSW [19]) as an index. The proximity graph in this framework is carefully built while considering attributes and can deal with any query attributes. – We conduct experiments on public datasets to evaluate our framework. Our experimental results show the efficiency of our algorithm. This is a full version of [27].
2
Preliminary
Let X be a set of n objects, and each x ∈ X is associated with a d-dimensional vector ∈ Rd and m attribute (integer) values. (As with existing works listed in [22,15], we assume that X is static, and its dynamic update (like [33]) is beyond the scope of this paper.) For example, when m = 3, the n objects have attribute values regarding category, color, and size. Note that d = O(1) and d is large, i.e., each vector is a high-dimensional one. We use xi .v to denote the vector of xi . Similarly, we use xi .A to denote the attribute list of xi , and xi .A[j] is the value of the j-th attribute of xi . For ease of explanation, we first define the exact filtered k nearest neighbor search problem. Definition 1. Consider X and a list of query attributes q.A = [q.A[1], ..., q.A[m]]. This list is called a query filter. If q.A[j] is null, the j-th attribute has no filter. Then, X(q.A) is defined as: X(q.A) = {x ∈ X | (x.A[i] = q.A[i]) ∧ (q.A[i] ̸= null) ∀i ∈ [1, m]}.
(1)
That is, X(q.A) ⊆ X is a set of objects ∈ X that satisfy the query filter. Definition 2 (Filtered kNNS). Given X, a query vector q.v, a query filter q.A, and a result size k, filtered kNNS returns S ∗ , such that |S ∗ | = k and ∀x ∈ S ∗ , ∀x′ ∈ X(q.A)\S ∗ , dist(x.v, q.v) ≤ dist(x′ .v, q.v), where dist(·, ·) is the Euclidean distance between two input vectors. Ties are broken arbitrarily. When |X(q.A)| ≤ k, this problem returns X(q.A). Problem definition. This paper considers an approximation version of Definition 2. The problem of filtered approximate kNNS (AkNNS) returns S ⊆ X(q.A) and, we may have S ̸= S ∗ . To measure the accuracy of S, as with existing ANNS ∗ | . works, we use recall@k, which is defined as recall@k = |S∩S k
4
Uemura et al.
3
Related Work
The exact kNNS algorithms typically rely on tree-based indices. They do not function in high-dimensional spaces due to the curse of dimensionality. This paper, hence, does not consider the exact algorithms. The AkNNS problem has three main approaches: hashing, space partitioning, and proximity graphs. It is well known that proximity graphs outperform other approaches. AkNNS. In a proximity graph, each node corresponds to a vector, and two similar vectors (nodes) have an edge. To traverse a proximity graph, greedy search is typically employed. From a start node, this greedy search computes the distance between a given query vector and each of the neighbor nodes. Then, it traverses the neighbor with the smallest distance, which is repeated until no closer nodes are found. This approach yields a more accurate result with faster time than hashing and space partitioning approaches [16]. To shorten the search path in the search, existing works designed diverse graph indices [4]. In a KGraph [7], each vector is connected to its approximate K nearest neighbor vectors. This graph index is built by NNDescent and in O(n) time if K = O(1) [2,3]. Navigable small world models, such as NSW [19] and HSNW [18], have both long and short edges, so that the number of hops to kNNs is minimized. Monotonic search networks [6] guarantee that any two nodes have a monotonic path, which is a path such that the distance to the target node becomes shorter as traversing to the next node in the path. Building a monotonic search network requires O(n3 ) time [6], so its approximate versions are considered in [9,10,21]. Relative neighborhood graphs [24] prune redundant edges, making a proximity graph sparser and alleviating unnecessary node traversals. Vamana [23] approximates the relative neighborhood graphs. Filtered AkNNS. Existing works consider matching filters [5,11,12,30,31] (i.e., objects have the same attribute values as the query filters) and range filters [36,8,13,32] (i.e., objects have an attribute value falling in the specified range). This paper focuses on the former case. NHQ [30] and HQANN [31] fuse the distance based on vector similarity and the one based on attribute similarity. ACORN [20] is essentially HNSW and employs Inline-processing. CAPS employs an IVF structure, and its clusters are built by a decision tree based on attribute values. UNG partitions X into disjoint subsets, and each subset has the same attribute values. A label navigation graph (LNG) is built based on a trie structure and attribute containment relationships. At the same time, for each subset, UNG builds a proximity graph. Then, based on LNG and a given query filter, UNG traverses necessary proximity graphs. According to the latest experimental study [22], UNG clearly outperforms the others, e.g., by at least an order of magnitude in QPS under the same recall, in our filter setting. We thereby use UNG as a baseline in our experiments. One important practical observation is that, as benchmark papers [15,22,35] suggest, the number of attributes specified by queries is usually one or two in practice. UNG does not care about this observation, and in such cases, it may need to traverse the graphs of many subsets, thereby degrading search performance.
Simple and Fast Algorithm for Graph-based Filtered ANNS
4
5
Proposed Algorithm
As mentioned earlier, proximity graphs have a better search-recall tradeoff than the other approaches. We therefore design a new proximity graph that considers attribute filters. Main idea. Let us consider the following three cases: Case 1. |q.A| = m, i.e., the query filter specifies all attributes. Case 2. |q.A| = 1, i.e., the query filter specifies one of m attributes. Case 3. 2 ≤ |q.A| < m, i.e., the other cases. Case 1. An intuitive approach to deal with case 1 is as follows. We partition X into disjoint subsets, such that the objects in a subset have the same attribute value for every attribute. Then, we build a proximity graph for each subset. Given a query vector q.v and a query filter q.A, we can use the proximity graph of q.A and run the greedy search on the graph. This approach is simple yet efficient. Furthermore, the total number of nodes is n, and if the number of edges is O(1), the space complexity is O(n), scaling well to large datasets. Case 2 can also employ a similar idea to the one above. Specifically, for the i-th attribute, we partition X into disjoint subsets based on the attribute values and build a proximity graph for each subset. This is applied for each i ∈ [1, m]. Because each object is involved in m proximity graphs, this approach consumes O(nm) space. As m is practically small (e.g., ≤ 3) [17], this approach is feasible. Case 3. For any query filter in case 1 or 2, the above approaches can find the graph index containing only objects that match the query filter. To achieve this for case 2, we have to enumerate all possible combinations of attribute values. This enumeration requires O(λm ) proximity graphs, where λ is the average number of distinct values in each attribute, and this is infeasible in practice. To address this issue, it is important to notice that case 3 is a subset (superset) of case 1 (2). Let Xa,b,...,c be a set of objects such that their 1st, 2nd, ..., and m-th attribute values are respectively, a, b, ..., and c. Similarly, let Ga,b,...,c be the graph index of Xa,b,...,c . Now assume that we are given a query filter q.A = [q.A[1] = a, q.A[2] = b, ..., q.A[m] = null]. It is easy to see that all objects in Xa,b,...,c satisfy q.A, so Ga,b,...,c is available. However, the objects in Xa,b,...,∗ , where ∗ is a wildcard, also have to be considered, so using only Ga,b,...,c may result in low recall. Our idea that overcomes this challenge: If there exist edges between Ga,b,...,c and Ga,b,...,∗ , we can traverse only nodes (objects or vectors) that satisfy q.A and are closer to q.v. This idea suggests that we do not have to traverse every Ga,b,...,∗ for q.A = [q.A[1] = a, q.A[2] = b, ..., q.A[m] = null]. To create such edges while minimizing space consumption, we add the edges made in case 2 to the graphs built in case 1. Let γ be the average degree of the graph indices in case 2, and each object eventually has O(mγ) edges on average. Note that some neighbors do not satisfy a given query filter, and we do not need to traverse them like Inline-processing.
6
Uemura et al.
4.1
Index Structure
Overview. Our new graph G = ⟨X, E⟩ is built by merging multiple graphs. Let Ga,b,...,c = ⟨Xa,b,...,c , Ea,b,...,c ⟩, where a, b, and c are variable, whereas Ea,b,...,c is a set of directed edges with labels. (We later define labels.) We build Ga,b,...,c for all Xa,b,...,c ⊂ X. Similarly, we build Ga,∗,...,∗ , G∗,b,...,∗ , ..., and G∗,∗,...,c for all Xa,∗,...,∗ , X∗,b,...,∗ , ..., and X∗,∗,...,c ⊂ X. Each object has edges generated in these graphs. Edge label. Consider two objects in G, and let l(x, x′ ) be the label of the directed edge (x, x′ ) ∈ E, i.e., x → x′ . It is defined as follows. ( ⊥ (if x.A = x′ .A) ′ (2) l(x, x ) = x′ .A (otherwise) Example 1. Assume that m = 3 and we have X1,1,1 and X1,3,2 . Then, X1,∗,∗ contains all objects in X1,1,1 and X1,3,2 . The top part of Figure 1 illustrates the graph indices of X1,1,1 , X1,3,2 , and X1,∗,∗ . We add edges of G1,∗,∗ to G1,1,1 and G1,3,2 . The bottom part of Figure 1 shows this edge addition. (For conciseness, not all are shown.) The labels of the blue edges are ⊥, whereas the label of edge (x10 , x16 ) is [1, 1, 1] because x16 ∈ X1,1,1 .
𝑮𝟏,𝟑,𝟐
𝑮𝟏,𝟏,𝟏 𝒙𝟏
𝒙𝟒
𝑮𝟏,∗,∗ 𝒙𝟏
𝒙𝟕
𝒙𝟔
𝒙𝟔
𝒙𝟏𝟎
𝒐𝟑𝟑
𝒙𝟑𝟑
𝒙𝟑𝟐
𝒙𝟏𝟕 𝒙𝟏𝟕
𝒙𝟏𝟔
𝒙𝟗
𝒙𝟐 𝒙𝟏𝟏
𝒙𝟑𝟐
𝒙𝟒 𝒐𝟕
𝒙𝟏𝟔
𝒙𝟗
𝒙𝟏𝟗
𝒙𝟐
𝒙𝟏𝟏 𝒙𝟏𝟗
𝒙𝟏𝟎
𝒙𝟐𝟑
𝒙𝟐𝟑
𝒙𝟏
𝒙𝟒 𝒙𝟕
𝒙𝟔
𝒙𝟏𝟔
𝒙𝟗 𝒙𝟑𝟑
𝒙𝟐
𝒙𝟏𝟏
𝒙𝟑𝟐 𝒙𝟏𝟕
[𝟏, 𝟏, 𝟏, ] 𝒙𝟏𝟎
𝒙𝟐𝟑
𝒙𝟏𝟗
Fig. 1. Example of our graph building
Which graph index is available in our algorithm? As seen in Figure 1, our graph index should be flat because of our edge addition strategy. An arbitrary flat graph index is available in our algorithm. In our experiments, we use NSW (with optimization in [18]) as our base graph index. Pre-processing algorithm. We build our graph index with Algorithm 1. This pre-processing is done only once, since our index is available for arbitrary queries.
Simple and Fast Algorithm for Graph-based Filtered ANNS
7
Algorithm 1: Pre-Processing Input: X, m, K (initial graph degree), K ′ (hyper-parameter) 1 G ←∅ 2 foreach Xa,b,...,c ⊆ X do 3 Ga,b,...,c ← Build-Graph(Xa,b,...,c , K) 4 G ← G ∪ Ga,b,...,c // ∀e ∈ E, l(e) =⊥ foreach x ∈ X do foreach i ∈ [1, m] do 7 X⟨i,x.A[i]⟩ ← X⟨i,x.A[i]⟩ ∪ {x}
5
6
foreach X⟨i,x.A[i]⟩ do G′ ← Build-Graph(X⟨i,x.A[i]⟩ , K ′ ) 10 foreach (x, x′ ) ∈ E ′ such that (x, x′ ) ∈ / E do 11 E ← E ∪ {(x, x′ )} with l(x, x′ ) = x′ .A 8
9
12
return G
To start with, for each Xa,b,...,c ⊆ X, we build a proximity graph Ga,b,...,c . In Algorithm 1, Build-Graph(·, ·) is the building algorithm of a given graph index structure. Since this graph contains only objects that share the same attribute values, the labels of its edges are ⊥. Next, for each x ∈ X, we assign it to m object sets. Specifically, let X⟨i,α⟩ = {x ∈ X : x.A[i] = α}, and for each i ∈ [1, m], we add x into X⟨i,x.A[i]⟩ . After we do this for every x ∈ X, we build a proximity graph for each X⟨i,x.A[i]⟩ and add its edges into G while making their labels based on Equation (2). Notice that G is considered to be a set of Ga,b,...,c with augmented edges from Ga,∗,...,∗ , G∗,b,...,∗ , ..., and G∗,∗,...,c . Time complexity. Let T (n) be the time of Build-Graph of n objects. Assuming that the graph degree is S O(1), the first for loop in Algorithm 1 requires P T (|Xa,b,...,c |) = T (n), since Xa,b,...,c =PX and Xa,b,...,c is disjoint. The second for loop trivially requires Θ(nm), as |X⟨i,x.A[i]⟩ | = nm. The last for loop involves nm objects, so T (nm) time is required. To summarize, the time complexity of Algorithm 1 is T (nm). Space complexity. As our index requires a flat graph structure, the number of nodes is n. Since each graph built in the first and last for loops has a constant degree, the number of edges is O(nm). Therefore, the space complexity of our index is O(nm). 4.2
Query Processing
Now we are ready to present our proposed algorithm, which is described in Algorithm 2. Note that ϵ is a parameter that controls the tradeoff between search time and recall. First, we determine the start node xs from G. If q.A has no null, xs is set as the medoid node of Gq.A (which is computed in pre-processing). On the other
8
Uemura et al.
Algorithm 2: Filtered ANNS Input: G, q.v, q.A, ϵ (≥ 1), and k /* Determining a start node */ 1 A ← q.A 2 for all i ∈ [1, m] such that q.A[i] = null do 3 Replace q.A[i] with a random value in the domain of the i-th attribute xs ← the medoid node in GA /* Traversing the graph from the start node 5 V ← {xs } // V is a set of visited nodes ′ ′ 6 P, P ← ⟨xs , dist(xs .v, q.v)⟩ // P and P are sorted by dist(·, q.v)) 7 τ ←∞ ′ 8 while P ̸= ∅ do 9 x ← the top element in P ′ 10 Pop P ′ 11 foreach x′ such that (x, x′ ) ∈ E and x′ ∈ / V do 12 V ← V ∪ {x′ } 13 if l(x, x′ ) =⊥ then 14 if dist(x′ .v, q.v) < τ then 15 Add ⟨x′ , dist(x′ .v, q.v)⟩ into P and P ′ 16 Update τ // the ϵ · k-th dist(·, q.v) in P 17 if |P | > ϵ · k then 18 Erase the last element in P 4
19 20 21
22
*/
else if x′ .A satisfies q.A then Run lines 14–18 return the first k elements in P
hand, if q.A has a null, we assign a random value in the domain for each null attribute in q.A. Then, xs is determined in the same way as the case where q.A has no null. Next, we run the greedy search from xs . In a nutshell, we traverse unvisited neighbors, which are then marked as visited and pushed into a priority queue based on the distance to q.v. Note that we visit only neighbors such that the labels of the corresponding edges are ⊥ or satisfy q.A. We repeat these operations until no closer objects are found.
5
Experiment
This section reports our experimental results. All experiments were conducted on a Ubuntu 24.04 LTS machine with an Intel Xeon Gold [email protected] CPU, and 768GB RAM. Dataset. We used SIFT, Deep, and GIST, which are commonly used in filtered ANNS works [11,12]. SIFT and Deep have 100 million vectors, while GIST has 1
Simple and Fast Algorithm for Graph-based Filtered ANNS SIFT1M - 1 attribute
GIST1M - 1 attribute
600
500
400
300
350 300 250
300
QPS
200
QPS
QPS
Deep10M - 1 attribute
350
250
400
9
150
100 100
100
50
0 0.8
0.85
0.9
Recall@10
(a) SIFT
0.95
1
200 150
200
50 0
0 0.7
0.75
0.8
0.85
Recall@10
0.9
0.95
1
0
0.2
(b) GIST
0.4
0.6
0.8
1
Recall@10
(c) Deep
Fig. 2. QPS vs. recall@10 for query filters with a single attribute. “×” shows Ours and “◦” shows UNG.
million vectors. By default, we used 1 and 10 million vectors for SIFT and Deep, respectively. (The full set is used in our scalability test.) We set m = 3, as in [5,12,29], so each object has three attributes. For each attribute, we employed the power law distribution, as used in [5], because it is commonly observed in real-world settings [12]. The first, second, and third attributes have 68, 10, and 12 distinct values, which is a more challenging setting than that in [5]. For each dataset, we used 1,000 queries obtained from the corresponding source. Their query filters also followed the same power law distribution. When a query filter specified a single attribute, a random attribute was chosen. Similarly, when a query filter specified two attributes, a random single attribute had a null value. We ran each query in single-thread mode. Algorithm. We compared our algorithm with UNG [5], a state-of-the-art filtered ANNS algorithm. We did not consider the other algorithms, because state-of-theart benchmarking works [5,15,22,35] demonstrate that UNG clearly outperforms them. For UNG, we used the original implementation1 with the default parameters. For our algorithm, K = K ′ = 16 (see Algorithm 1). They were implemented in C++ and compiled by g++ with -O3 optimization. SIMD instruction was enabled. Criteria. We measured the AkNNS performance tradeoff between QPS (query per second) and recall by varying ϵ. We set k = 10, as with existing works. Result. Figures 2, 3, and 4 exhibit the experimental results. Query filter of a single attribute case. Figure 2 shows the results when query filters have a single attribute. They demonstrate that our algorithm substantially outperforms UNG. In our graph index, each node has edges obtained from Ga,∗,∗ , G∗,b,∗ , and G∗,∗,c , so each node (object) has edges to similar objects “w.r.t. a given query filter.” On the other hand, UNG needs to traverse nodes based on the trie tree, i.e., an attribute-based relationship, which does not guarantee connecting similar objects. This property significantly degrades the ANNS performance when only a subset of m attributes is specified as a query filter. 1
https://github.com/YZ-Cai/Unified-Navigating-Graph
10
Uemura et al. SIFT1M - 2 attributes
Deep10M - 2 attributes
GIST1M - 2 attributes
1000
600
600
500
500
400
400
900 800
700
500
QPS
QPS
QPS
600 300
300
400 300 200
100 0 0.75
0.8
0.85
0.9
0.95
200
200
100
100
0 0.75
1
Recall@10
(a) SIFT
0 0.8
0.85
0.9
Recall@10
0.95
0.5
1
0.6
0.7
0.8
0.9
1
Recall@10
(b) GIST
(c) Deep
Fig. 3. QPS vs. recall@10 for query filters with two attributes. “×” shows Ours and “◦” shows UNG.
SIFT1M - 3 attributes
GIST1M - 3 attributes
60000
Deep10M - 3 attributes
16000
30000
14000
50000
25000
12000 20000
30000
QPS
10000
QPS
QPS
40000
8000 6000
20000
15000
10000
4000 10000
5000
2000 0 0.98
0.985
0.99
Recall@10
(a) SIFT
0.995
1
0 0.92
0.94
0.96
Recall@10
(b) GIST
0.98
1
0 0.94
0.95
0.96
0.97
0.98
0.99
1
Recall@10
(c) Deep
Fig. 4. QPS vs. recall@10 for query filters with three attributes. “×” shows Ours and “◦” shows UNG.
Query filter of two attributes case. Figure 3 describes the results when query filters have two attributes. Our algorithm consistently outperforms UNG on SIFT and Deep, whereas their performances are comparable on GIST. The effectiveness of our main idea is demonstrated in these results, as our algorithms do not build any proximity graphs for the case of two attributes. As mentioned in Section 3, the number of attributes specified by queries is usually one or two in practice. Our algorithm normally outperforms the state-of-the-art in this practical scenario. Query filter of three attributes case. Figure 4 shows the results when query filters have three (i.e., all) attributes. UNG yields a result comparable to ours, as UNG traverses only the graph consisting of objects that match a given query filter when |q.A| = m. Ours also has this property, so they share a similar result (although ours keeps outperforming UNG on Deep, a larger dataset than SIFT and GIST). Memory consumption. Table 1 shows the index sizes of ours and UNG. Although ours needs more space, the difference is negligible.
Simple and Fast Algorithm for Graph-based Filtered ANNS
11
Table 1. Index size [GB] Dataset Ours UNG SIFT 0.83 0.59 GIST 3.85 3.68 Deep 7.21 4.96
SIFT (1 attribute): recall@10 = 0.99
SIFT (2 attributes): recall@10 = 0.99
SIFT (3 attributes): recall@10 = 0.99
100
10
100000
QPS
1000
QPS
QPS
1000
100
10 1
10
100
10000
1000 1
Data size x106
10
100
1
Data size x106
(a) 1 attribute
10
100
Data size x106
(b) 2 attributes
(c) 3 attributes
Fig. 5. Impact of n on SIFT under recall@10 = 0.99
Deep (1 attribute): recall@10 = 0.99
Deep (2 attributes): recall@10 = 0.99
Deep (3 attributes): recall@10 = 0.99
100
10
100000
QPS
1000
QPS
QPS
1000
100
10 1
10
100
Data size x106
(a) 1 attribute
10000
1000 1
10
100
1
Data size x106
(b) 2 attributes
10
100
Data size x106
(c) 3 attributes
Fig. 6. Impact of n on Deep under recall@10 = 0.99
Scalability test. Last, we investigate the scalability of our algorithm by using 1, 10, and 100 million vectors. When scaling to 100M vectors, we were unable to run UNG successfully using the authors’ public implementation under our experimental setup. (It terminated with a runtime failure, i.e., a segmentation fault.) Hence, we only report the scalability results of our algorithm. Figure 5 (Figure 6) shows the QPS result on SIFT (Deep) under recall@10 = 0.99. As the dataset size, i.e., n, grows, QPS drops, which is quite a natural phenomenon. One important observation here is that QPS does not drop linearly with n but rather sublinearly. This result demonstrates that our algorithm scales well to n. As a reference, we note that the QPS of Pre-filter on SIFT 100M with a single-attribute query filter is 0.42. Ours achieves more than 100 times better QPS with recall@10 = 0.99 in the same setting.
12
Uemura et al.
6
Conclusion
This paper tackled the problem of filtered approximate k nearest neighbor search on high-dimensional data. Existing works do not fully address this problem and have critical drawbacks, such as handling only a single attribute, not supporting the specification of attribute subsets, and inefficiency in practical use cases. To remove these drawbacks, we proposed a new graph-based AkNNS algorithm. Our experimental results show that our algorithm usually outperforms the existing state-of-the-art UNG.
References 1. Amagata, D.: Scalable and accurate density-peaks clustering on fully dynamic data. In: IEEE Big Data. pp. 445–454 (2022) 2. Amagata, D., Onizuka, M., Hara, T.: Fast and exact outlier detection in metric spaces: A proximity graph-based approach. In: SIGMOD. pp. 36–48 (2021) 3. Amagata, D., Onizuka, M., Hara, T.: Fast, exact, and parallel-friendly outlier detection algorithms with proximity graph in metric spaces. The VLDB Journal 31(4), 797–821 (2022) 4. Azizi, I., Echihabi, K., Palpanas, T.: Graph-based vector search: An experimental evaluation of the state-of-the-art. Proceedings of the ACM on Management of Data 3(1), 1–31 (2025) 5. Cai, Y., Shi, J., Chen, Y., Zheng, W.: Navigating labels and vectors: A unified approach to filtered approximate nearest neighbor search. Proceedings of the ACM on Management of Data 2(6), 1–27 (2024) 6. Dearholt, D.W., Gonzales, N., Kurup, G.: Monotonic search networks for computer vision databases. In: Asilomar Conference on Signals, Systems and Computers. vol. 2, pp. 548–553 (1988) 7. Dong, W., Moses, C., Li, K.: Efficient k-nearest neighbor graph construction for generic similarity measures. In: World Wide Web. pp. 577–586 (2011) 8. Engels, J., Landrum, B., Yu, S., Dhulipala, L., Shun, J.: Approximate nearest neighbor search with window filters. In: ICML (2024) 9. Fu, C., Wang, C., Cai, D.: High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44(8), 4139–4150 (2021) 10. Fu, C., Xiang, C., Wang, C., Cai, D.: Fast approximate nearest neighbor search with the navigating spreading-out graph. Proceedings of the VLDB Endowment 12(5), 461–474 (2019) 11. Gollapudi, S., Karia, N., Sivashankar, V., Krishnaswamy, R., Begwani, N., Raz, S., Lin, Y., Zhang, Y., Mahapatro, N., Srinivasan, P., et al.: Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters. In: Web Conference. pp. 3406–3416 (2023) 12. Gupta, G., Yi, J., Coleman, B., Luo, C., Lakshman, V., Shrivastava, A.: Caps: A practical partition index for filtered similarity search. arXiv preprint arXiv:2308.15014 (2023) 13. Jiang, M., Yang, Z., Zhang, F., Hou, G., Shi, J., Zhou, W., Li, F., Wang, S.: Digra: A dynamic graph indexing for approximate nearest neighbor search with range filter. Proceedings of the ACM on Management of Data 3(3), 1–26 (2025)
Simple and Fast Algorithm for Graph-based Filtered ANNS
13
14. Kido, K., Amagata, D., Hara, T.: Fast approximation algorithm for euclidean minimum spanning tree building in high dimensions. In: PAKDD. pp. 432–443 (2025) 15. Li, M., Yan, X., Lu, B., Zhang, Y., Cheng, J., Ma, C.: Attribute filtering in approximate nearest neighbor search: An in-depth experimental study. Proceedings of the ACM on Management of Data 3(6), 1–26 (2025) 16. Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., Lin, X.: Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering 32(8), 1475–1488 (2019) 17. Lin, Y., Zhang, K., He, Z., Jing, Y., Wang, X.S.: Survey of filtered approximate nearest neighbor search over the vector-scalar hybrid data. arXiv preprint arXiv:2505.06501 (2025) 18. Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligencee 42(4), 824–836 (2018) 19. Malkov, Y., Ponomarenko, A., Logvinov, A., Krylov, V.: Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45, 61–68 (2014) 20. Patel, L., Kraft, P., Guestrin, C., Zaharia, M.: Acorn: Performant and predicateagnostic search over vector embeddings and structured data. Proceedings of the ACM on Management of Data 2(3), 1–27 (2024) 21. Peng, Y., Choi, B., Chan, T.N., Yang, J., Xu, J.: Efficient approximate nearest neighbor search in multi-dimensional databases. Proceedings of the ACM on Management of Data 1(1), 1–27 (2023) 22. Shi, J., Cai, Y., Zheng, W.: Filtered approximate nearest neighbor search: A unified benchmark and systematic experimental study [experiment, analysis & benchmark]. arXiv preprint arXiv:2509.07789 (2025) 23. Subramanya, S.J., Devvrit, Kadekodi, R., Krishaswamy, R., Simhadri, H.V.: Diskann: Fast accurate billion-point nearest neighbor search on a single node. In: NeurIPS. pp. 13766–13776 (2019) 24. Toussaint, G.T.: The relative neighbourhood graph of a finite planar set. Pattern Recognition 12(4), 261–268 (1980) 25. Uemura, R., Amagata, D.: Ivf++: A flexible and efficient algorithm for approximate nearest neighbor search under attribute constraint. In: IEEE International Conference on Big Data. pp. 7444–7451 (2025) 26. Uemura, R., Amagata, D., Hara, T.: An efficient framework for approximate nearest neighbor search on high-dimensional multi-metric data. In: SISAP (2024) 27. Uemura, R., Kido, K., Amagata, D.: Simple and fast algorithm for graph-based filtered approximate nearest neighbor search. In: SISAP (2026) 28. Wang, J., Yi, X., Guo, R., Jin, H., Xu, P., Li, S., Wang, X., Guo, X., Li, C., Xu, X., et al.: Milvus: A purpose-built vector data management system. In: SIGMOD. pp. 2614–2627 (2021) 29. Wang, M., Lv, L., Xu, X., Wang, Y., Yue, Q., Ni, J.: Navigable proximity graphdriven native hybrid queries with structured and unstructured constraints. arXiv preprint arXiv:2203.13601 (2022) 30. Wang, M., Lv, L., Xu, X., Wang, Y., Yue, Q., Ni, J.: An efficient and robust framework for approximate nearest neighbor search with attribute constraint. In: NeurIPS. pp. 15738–15751 (2023) 31. Wu, W., He, J., Qiao, Y., Fu, G., Liu, L., Yu, J.: Hqann: Efficient and robust similarity search for hybrid queries with structured and unstructured constraints. In: CIKM. pp. 4580–4584 (2022)
14
Uemura et al.
32. Xu, Y., Gao, J., Gou, Y., Long, C., Jensen, C.S.: irangegraph: Improvising rangededicated graphs for range-filtering nearest neighbor search. Proceedings of the ACM on Management of Data 2(6), 1–26 (2024) 33. Yamashita, T., Amagata, D., Matsui, Y.: How should we evaluate data deletion in graph-based ann indexes? arXiv preprint arXiv:2512.06200 (2025) 34. Yu, S., Engels, J., Huang, Y., Shun, J.: Pecann: Parallel efficient clustering with graph-based approximate nearest neighbor search. arXiv preprint arXiv:2312.03940 (2023) 35. Zhu, J., Yuan, J., Yang, K., Chen, X., Yu, S., Lv, H., Li, Y., Zheng, B.: An experimental evaluation of hybrid querying on vectors. Proceedings of the VLDB Endowment 19(2), 183–195 (2025) 36. Zuo, C., Qiao, M., Zhou, W., Li, F., Deng, D.: Serf: Segment graph for rangefiltering approximate nearest neighbor search. Proceedings of the ACM on Management of Data 2(1), 1–26 (2024)