An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint
Authors: Mengzhao Wang
Lingwei Lv
Xiaoliang Xu
Yuxiang Wang
Qiang Yue
Jiongkang Ni
Venue: NeurIPS 2023 poster (2023)
Keywords: approximate nearest neighbor search
attribute filtering
high-dimensional vector
proximity graph
TL;DR: An Efficient and Robust Framework for ANNS with Attribute Constraint

Abstract: This paper introduces an efficient and robust framework for hybrid query (HQ) processing, which combines approximate nearest neighbor search (ANNS) with attribute constraint. HQ aims to find objects that are similar to a feature vector and match some structured attributes. Existing methods handle ANNS and attribute filtering separately, leading to inefficiency and inaccuracy. Our framework, called native hybrid query (NHQ), builds a composite index based on proximity graph (PG) and applies joint pruning for HQ. We can easily adapt existing PGs to this framework for efficient HQ processing. We also propose two new navigable PGs (NPGs) with optimized edge selection and routing, which improve the overall ANNS performance. We implement five HQ methods based on the proposed NPGs and existing PGs in NHQ, and show that they outperform the state-of-the-art methods on 10 real-world datasets (up to 315$\times$ faster with the same accuracy).

An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint
Mengzhao Wang Hangzhou Dianzi University vmzssy@yeah. net
Lingwei Lv Hangzhou Dianzi University 1lwOhdu, edu. en
Xiaoliang Xu" Hangzhou Dianzi University xxl xx1dhdu.. edu. en
Yuxiang Wang Hangzhou Dianzi University 1sswyx@hdu. edu. cn
Qiang Yue
Jiongkang Ni
Hangzhou Dianzi University yqohdu. edu. cn
Hangzhou Dianzi University hananoyuuki @hdu. edu. cn
Abstract
This paper introduces an efficient and robust framework for hybrid query (HQ) processing, which combines approximate nearest neighbor search (ANNS) with attribute constraint. HQ aims to find objects that are similar to feature vector and match some structured attributes. Existing methods handle ANNS and attribute filtering separately, leading to inefficiency and inaccuracy. Our framework, called native hybrid query (NHQ), builds a composite index based on proximity graph (PG) and applies joint pruning for HQ. We can easily adapt existing PGs to this framework for efficient HQ processing. We also propose two new navigable PGs (NPGs) with optimized edge selection and routing, which improve the overall ANNS performance. We implement five HQ methods based on the proposed NPGs and existing PGs in NHQ, and show that they outperform the state-of-the-ard methods on real-world datasets (up to 315x faster with the same accuracy).
Introduction
Approximate nearest neighbor search (ANNS) a crucial problem in data science and AI applications [3 9 47. For example, in paper-retrieval system based on ANNS, user wants to find papers that are most similar to her query text. As Fig. I () shows, the system converts each paper's unstructured text and the query text into feature vectors in a high nigh-dimenssioal space. Then it uses a vector index to perform ANNS and obtain papers with similar content. Many effective ANNS
methods have been developed to balance query efficiency and accuracy [8 19
36
40
[T].
However, ANNS does not support many real-world scenarios where users want to find objects with similar feature vectors to the query object and meets the given attribute constraint (e.g.. topic. venue,
and publish__yee year of a paper) [51] 41. We call this a hybrid query (HQ) 55 60 32 50 42 For instance, in Fig. [bb. user wants to find some recent papers from top-tier conferences related to her research interest. She can form a HQ by providing a descriptive text her interest and two paper attributes (e.g., NeurIPS and 2022). However, the traditional ANNS shown in Fig. [T] only finds
papers with similar content, and cannot guarantee matching attribute constraint. Therefore, many have tried to add attribute filtering (AF) on top of ANNS answer a HQ [54] 61]
Vearch 29 uses ANNS to find candidates that match the feature vector, and then applies AF to This strategy can work with other ANNS libraries, such SPTAG (37].
get the final results 32
NGT [59], and Faiss 17
On the other hand, Alibaba AnalyticDB-V (ADBV) (4 employs product
"Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Stuctared atrib
Enterditg
Unitaattred Test
RisniS 202
Feoture vector
Fosturt vedear
Qaers voit
énteekiin
Featur vecttr
Infoor coniiatiie
Cietr
Untimatrred docs
processing
sage intend ponsliigg restritttt aurtiaiii Shock
Seardh
Query lest
faanirppeeennnngo.ooo enahe, ra, Siileght cunt-rg onple
Aet bute Constratets
Feotir
Coveposter
(3) ANNS
Query rput
Id1 Our HG processing
Figure I: An example of different paper-retrieval schemes, including (a) ANNS and (c-d) HQ. ANNS retrieves results with semantically similar content, but it does not check the attribute constraint. A HQ processing obtains results that match both the feature vector and attribute constraints.
quantization (PQ) 28 to create multiple query plans. One of them is to do AF first and then ANNS to return the final results. This method is scalable and suitable for most cases (5T]. Milvus B8 partitions the dataset into subsets based on common attributes. This way. it can quickly select the subsets that meet the query's 's attribute constraints, and only perform ANNS on them instead of the whole dataset. This improves the search efficiency [51].
These solutions have a common idea: they do AF and ANNS separately in different orders (see Appendix A for details). No matter what order they use, the whole query pipeline can be simplified as Fig. D e), where two subquery systems (for AF and ANNS) are built independently. They can answer a HQ, but they are not designed for it, which affects their efficiency and effectiveness.
1.1 Limitations of Existing Methods
Ll: Two indexes need to be kept at the same time. Fig. Ie) shows that existing methods need both the attribute index and vector index for two separate subquery systems. This takes more memory space and adds more logic (e-g., merging) to make sure two indexes are consistent and query results are correct (54). Updating different indexes at the same time is hard when the data changes often.
L2: Extra computational cost from two separate pruning strategies. For existing methods, pruning is done based on attribute index and vector index separately, which increases computational cost. For example, suppose that the vector index in Fig. [ a proximity graph (PG, we define in Def. 4 [52], where each vertex is an object's 's feature vector. Then, some vertices near the query object's s feature vector but not matching the attributes can make the search follow wrong paths and return wrong answers to a HQ. We prune these wrong answers in the attribute- filtering phase, but the computational cost for returning them in the ANNS phase is unnecessary and inefficient.
L3: Query results rely on the merging of the candidates from both subquery systems. As Fig. [c) shows, we need to merge the top-k candidates Cj and C2 from both subquery systems to get the final results A = C2 n C2. But usually we have [R] < k. This is because existing methods do ANNS and AF separately, so each system can only return candidates that meet one type of constraint. To make R bigger, we need to make C1 and C2 bigger, which makes both systems slower [60].
L4: Existing methods are not friendly for PGs. Recent methods, like ADBV [54] and Milvus [T], use a "first AF, then ANNS" strategy to answer a HQ; they only use PQ many studies have shown PG is 10x faster than PQ for ANNS 5 3K
28 for ANNS. But
so we need find way to use PG in HQ. A simple way is to replace PQ-based vector index with PG-based one, but it has some problems: (1) In the "first AF, then ANNS" strategy, we want find similar vectors from dynamic space of the vectors filtered by attributes. It is not efficient to build a vector index for these filtered vectors in runtime. (2) Even worse, if we list all possible combinations of attribute values and prebuild a vector index for each one offline (like (56)), it would take too much memory space, e.g., mn different indexes for n attributes where each attribute has m values.
To sum up. most of these limitations happen because existing methods answer HQ in a "decomposition- assembly" model, where HQ is split into two subqueries that process separately and then combine the results. This motivates us to present a new general framework for HQ that works well with existing PGs. It has the well-designed composite index and joint pruming modules to support ANNS with attribute constraint, instead of keeping two separate indexes and doing pruning separately.
1.2 Our Solution and Contributions
To the best of our knowledge, we are the first to present a Native Hybrid Query framework (NHQ) for ANNS with attribute constraint in fused way, not the "decompssiioo-assembbly model used by

---

existing methods. As Fig. dd shows, our framework first combines feature vectors and attributes in a well-designed composite index (for L1); then it prunes the search space on the composite index by considering both the feature vector and attribute constraints (for L,2); and finally, it gets the final top-k results directly without a merging operation (for L33). Our NHQ is general framework, where the composite index is based on PG, so existing PGs can easily work with NHQ (for L4) and it also supports custom-optimizz PGs. Our main contributions are:
We introduce NHQ, a general framework for ANNS with attribute constraint ($3) NHQ works well with existing PGs, and can make them handle HQ only by lightweight modification.
We design two navigable PGs (NPGs) with optimized edge selection and routing strategies which have better sfffciennc--s-acccueee
trade-off than basal PGs.
We use the proposed NPGs and existing PGs in our NHQ framework, and get several new HQ methods that beat the state-of-the- competitors on all datasets (up to 315x faster, $5.3)
We show our methods' better effectiveness, efficiency, and scalability 10 real-world datasets, compared with state-of-the-ar HQ frameworks and methods ($5).
2 Preliminaries
Definition Object Set. An object set is defined as a S (eo....,en-il of size n. For each object e E S, (1) its features are represented as high-dimensional vector, denoted by v(e), (2) has set of attributes denoted by ".a....,mmm111 and e.o; indicates the value of attribute og of Moreover, we define the feature vector set of all objects in S as X' {v(c)le E S}.
Example 1 An object set could refer to different rypes of data, e.g. images, papers. When we specify the implicit semantics behind the
each object text, which is usually represented as a feature vector v(e) by neural network, egg., BERT [13;; and another is the explicit attribules, e.g.. {venue, topic), such as e.venue "NeurlPS".
paper, it carries types of information:
Given object set S and user-input query object q, many approaches have been studied to retrieve the most similar objects to from S by considering feature vectors' distance alone [[5 36 [6]. In the following, we first introduce ANNS, then formally define the HQ that study.
For an object E S and its feature vector v(e) E X, we write v(e) [v(e)) v(e) ...., v(e)d=1) d-11j where v(e)' is the value of v(e) on the i-th dimension. We focus on the high-dimension case where is from hundreds to thousands. For any two objects e, o S with feature vectors v(e). v(o) X,
we can measure their similarity with different methods, such as Euclidean distance [I9 and Cosine similarity (36] Euclidean distance is the most popular method 33 which Eq.
8(v(e),((o))
-
Definition NNS J8 20, 45).
Given an object set S and a query object with the feature vector v(g), the NNS aims obtaining the top-k objects from S whose feature vectors closest v(g).
In Def. the exact top-k objects (denoted by T) hold that
arg
Σ 8(v(e), TCS,T =k RET
min
(2)
Exact NNS on large S is not feasible because takes too much computation [52 So, an ANNS is more realistic, as it balances accuracy and efficiency with a vector index [52]. Let I' be the exact top-k objects from Def. and R be the approximate top-k objects from an ANNS method. We can use recall rate Recall@k & to measure the search accuracy of the approximate method:
IRN T
Recall@k
(3)
k A bigger Recoll@k means more accurate results from ANNS.

---

Online: joint pruning the
feature vector v(p)
Fusion
[(g.u))
A query object
T(g.4)
Attribute constraints {(t)
T(g.u.)
1.3
Featuree vector space x' CSS)
[(g.u,)
0.8
T(g..))
An object set S
Milll ES! Attribute vector space
[(g.u;)
Offiine: building composite index
Figure 2: NHQ framework overview.
To return the query results fast, ANNS makes vector index based on the feature vector. We can
classify ANNS methods into four types by how they make the index: quantization [28 [2]]; tree
46 21; hashing [22 [24]: and proximity graph (P6) 19]. Many works [33 19 have shown that
the PG-based methods have better efficiency vs accuracy trade-off.
Definition 3 Hybrid Queries (HQ). Given an object set and a query object q with a feature vector v(q) and a set of attributes {do...., am-11 } of size m, the HQ returns the top-k objects from S, denoted by T. The objects in T satisfy two conditions: I attribute filtering (AF): they have the same attributes as q- thttt is, for any T, Vi = 0,1, feature vectors are the closest to v(q) among those that meet !
e.a. = 9.0g; and ② ANNS: their - -,0.00
It is also too slow to answer an exact HQ on large S. So, current research works on an approximate
HQ processing [51 54] and the query accuracy is measured by Eq. 3 for a returned A from the approximate method. HQ is an extended ANNS with attribute constraint [5]. But it is a challenging problem, because all existing methods have accuracy and efficiency issues (L1-L4 $1.I.
NHQ Framework
We begin by defining proximity graph (PG) and then introduce the NHQ framework based on PG.
Definition 4 PG. Given an object set S, we define the PG of S w.r.. an distance threshold B as graph G (V. E) with the vertex set V and edge set E. ! For each vertex u E V, it corresponds to an object S. 2 For any two vertices u, and u from V, if u,uy E E, we have 8(v(us),((,)) < B, where v(us) and v(u;) is the feature vectors of objects un and új, respectively.
Let ((u)) be the neighbor set of u, Our idea to build PG that uses both feature vectors and attributes as composite index. In the index, the neighbors of may have the same attributes as can use Eq. to measure the feature vector distance, but we need to quantify the attributes and define a distance metric function [55]. Then, we can fuse the feature vector distance and the attribute distance into a fusion distance to compare the objects. Therefore, we can directly prune the vertices that have either dissimilar feature vectors different attributes with the fusion distance.
Fusion distance. Given an object S with feature vectors X' (see Fig. 2 bottom left), we can use different encoding methods B
44 48 to encode the attributes of each object e E S. Ordinal encoding works well for structured attributes [53]. We use ordinal encoding é(.) to get an attribute vector f(e) = [é(e)) ... , ((e))=") 1 for each object e, where f(e)' is e.a,'s 's encoded value (e.g.. (NeurIPS, NLP) can be encoded as 3] by {()). Then, we get attribute vectors = {f(e)le S).
We can measure the distance between two feature vectors v(e:) and v(e,) in X' by using Eq. 1 We can measure the distance between two attribute vectors {(e,) and E(e,) in Y by using this formula:
m-1
((((e)))(ez))
Σ
(((e)))
where ((((ee)* )
((l(e)) ((e))) C flei) (e))==lle))* f(e,) Eles)* ((ee))
(5)
In Eq. 45 m is the number of dimensions in f(ex), and E(es) * is the value on the k-th dimension. The smaller this distance is, the more similar the attribute vectors arc.

---

We can fuse the feature vector distance ((v(es), v(e;)) and the attribute vector distance x ((e)))))(()))))))) into a single distance ['e ej) for objects e, and ej by using this formula:
ez) = wy ((v(es), + We ((((e:),((es))
(6)
where w, and wy are distance weights. The smaller this distance is, the more similar the objects are in both feature vectors and attributes. Eq. [ simple and practical way combine two different distances. It also makes it easy to build a composite index on top of existing PGs, because we just need change the distance measure from Eq. to Eq. - For example. if we set wy and we we get I'(,, Eg) = 8(v(e,) v(e))). which is the same as building PG based on feature vector. If we set Wy = 0 and wy = I, we get I'(e,, E3) = ((())), [(e,)), which a PG based on attribute. So, we can find the best balance between two distances by adjusting wy and we.
Weight configuration. We found that w, 1 and wy 5(((c,), v(ez))/m give the best query performance for most datasets and algorithms (see Appendix[U], These weights do not depend on the dataset, but only on the feature vector distance d(v(es), p(e,)) of two objects and the attribute vector dimension m. The idea is to fine-tune the feature vector distance with the attribute distance. For example, if e and ej have the same attributes, that is, x(f(ex), ((e;)) vector distance as it is (i.e., I(e,,e)) eÿ) = 5(v(es). ((e)))) If e and ej have completely different attributes, that is, x(((e.),((e)) = m, we double the feature vector distance get ee() 2. ((v(e,), p(e))). In general, we have 5(v(e,), ((e)) S l'ee,, E4) S 2 d(v(e)), p(eg))
O, we keep the feature
Composite index. We build composite index based on Algorithm[]] (see Fig. 2 bottom right). (see We start with V S. each object E S is vertex v E V in G, and E = 0. Then, we add an edge Ue E between two vertices ui uj V if [(u;, u,) < B', where B' is a fusion distance threshold. Note that our composite index does not incur extra space cost, as shown in Lemmal) !
Algorithm Building Composite Index (S)
Input: Object set S Output: Composite Index G = (V, F.)
V < forall ut E do
S, E < 0
forall uj V {u:} do
if Uss Uj) S B' then E = EE {uuu}}
Lemma The composite index and the ordinary PG have the same index size for an object set S.
return G (V.
Theorem Let Qmin and Dmaz be the minimum and maximum distances between feature vectors
S. Suppose we have at least [e)) objects with the same attributes as e for any object e E S. Then, ! for any vertex and its neighbor in the composite index, we have Umin T[u, 0) I &mmxi ②
for any vertex u and its neighbor o in the ordinary PG. we have Immin S ((u, S 2 Pmax.
Theorem shows that our composite index has smaller fusion distance bound.
Joint pruning. Given a query object q. we use a composite index G and seed set P (usually chosen randomly from V (52)) to find the approximate top-k objects based on Algorithm We follow these steps (see Fig. [ top right): I Initialization. We use a visited vertex set C to store the vertices for search expansion and result set R of size l to store the current query results. We set both sets to P at first. 2 Search expansion. We take out the vertex u; with the smallest [(g, u.) from C as the next visited vertex, and then add ((u)) to C. 3 Query results update. We update R with the better vertices in N (u.). For any vertex Uj E N (u,) and vertex ur E R that is the farthest from q, we replace u, with uj in R if I' (4), uz)) < l'(g, u,). This means uy is more similar to in both feature vectors and attributes than u, We repeat ② and 3 until R does not change, then return R as the approximate top-k objects.
Algorithm 2: Joint Pruming (G, q, P)
Input: Composite index G = (V, E), query object q, seed set P
2
Output: Result set πt
candidate set C < P: result set R while R is updated do
U4 + arg min I'(q, u:):
C' = C {ui}
N(u)) + the neighbors of u,i
C= C (u,)
forall uy E N(,.) do
Uy + arg max l(q, ur)
if r(g. uy) [[q. u,) then
R = R {
R RU {4g}
return R
Example 2 We show an example of joint pruming for finding the nearest object (i.e., top-1) to the query object q in Fig. 2 (top right). We start with random vertex as the seed, i.e., P {
5

---

P3
(M, Mar
F4
(a] Nalve edge selection
(b) RNG's edge selection
Our edge selection
Figure 3: Different edge selection strategies for uy (we assume u, has at most four neighbors).
and ser C' = } and R {uo}. Then, we expand the search space with un 's neighbors and get C= C=fu1, u2 u3, 3. We update R with un because [[q un) = 0.5 is smaller than [' un) = 1.0. We continue to expand the search space with un 's and Us 's neighbors and get R = {us}. Since no vertex Uj E (us) has a smaller distance than [' U5), we return Us as the approximate top-1 nearest object. We prune the vertices u1, U2, and us from the search space.
Theorem 2 Given query object q, the composite index guarantees least the same Recallak of HQ as the ordinary PG. (see Appendix H for the proof)
Theorem states that our composite index has higher equal Recall@k than the ordinary PG.
4 Navigable PG Algorithm
To form the composite index, we can deploy specific PG in NHQ and change its original distance measure to the fusion distance (Eq. 6). This gives the PG the ability to handle HQ effectively. However, current PGs have limitations that affect NHQ's performance with the PG-based composite index. Therefore, we present two new navigable PGs (NPGs) in this section. We optimize the edge selection and routing strategies for building and searching on PG, respectively.
4.1 Edge Selection
Edge selection is a crucial step for building a PG. It determines the neighbors of each object e in object set S. Different strategies build different structures for a PG, which affect its search performance 19). Existing PGs use two factors for edge selection: distance between two vertices (D1) and distribution of all vertices (D2) [52]. Early PGs like NSW (35 and KGraph [4] only use DI and connect each vertex with some of its nearest neighbors (Fig. Aa)). However, this can cause redundant computations and reduce search efficiency
34
Recent PGs also use D2 with RNG's edge
selection, which diversifies the neighbors' direction
33 However, RNG's edge selection still fails
to diversify the neighbors well (Fig. 3h)). Due the space limitation, explain this in Appendix
Our edge selection. We design new edge selection strategy that uses DI and D2. It connects u, with one nearest neighbor in each area of u; (P1-P4 in Fig. (()). We define the landing zone of u; and one of its neighbors Uy E Nuu)). which is the area where only the vertices in it can be added to N(u.). We then describe our edge selection strategy based the landing zone.
Definition Landing zone. The landing zone Lu,, uz) of vertex un and one of its neighbors u N (u.) is an area defined by H (u, u,) \ B(us, d(v(u,), v(,)))) Here, H H(u, uy) is the half space with un that is split by the perpendicular bisector U U(u, uz) of the line between un and uj. And Blu, 8(v(u,) v(u;)) ))) is the hypersphere centered at u, with radius d(v(u,, vv(u),,((u))).
Example As Fig. 3c shows, in a two dimensional space, U(i, un) is a perpendicular bisector of the line connecting Wh and un (i.e., the red line), (us, wo) is located on the upper side of U U(u; uo). and Bu,, ((v(u,), v v(uo)) is the area enclosed by the green circle. Therefore, the landing zone L(u,, uo) formed by u, and un is the green shaded region (i.e., H (uu, (o)),))) \ BBu,, 0(v(u,), v(uo))))
To find the areas without any neighbor of us we intersect the landing zones of all its existing neighbors (i.c.. (u.))( L(u,, 1z)). Then, we add the closest vertex (w.rt. u;) within this area into N (u,). making the neighbors more diverse. We get N (u,) for each vertex u, E V as follows (Algorithm 3
! Candidates acquisition. We obtain a set of candidate neighbors for u, from (V \ {w:)). }) denoted by C(uz). We can use random sampling or extra index to get ((u)) (c.g.. get C(u)) based

---

on NSW [3]] and KGraph 14 in 4.. We ensure that 1 R, where R is the maximum number Neighbors initialization. We sort the elements in C(u.) in ascending order of distance to us. We initialize (u,)) with u, ''s nearest candidate neighbor u, from C(us) and remove u, from C(u.). & Neighbors update. We select the nearest vertex up of uy from ((u)), and add it to (u,) if it is in the intersection area (i.e., (u.)) I(u,, Uz)) of the landing zones of u, and its existing neighbors. We repeat this process until C(u)) = 0 or (u() R.
neighbors for u, (i.e.. IN [N, S R).
Our strategy ensures that ut's 's neighbors are di- verse in terms of the areas where C(u)) is lo- cated. This is because we add up to (u,) from different area each time. We have the follow- ing theorem.
Algorithm 3: Edge Selection (uz, 1, R))
Input: Vertex uy constants | and R Output: Neighbor set N (u:) candidate set C(u,) < candidate neighbors
Ur < arg miD,,,C((.)) d(v(us), (ux))
((ua) + N(u,) U {ue):
Theorem The angle between any two neigh- bors is not less than n 11/3. (See Appendix foor the proof)
C(u)) t- C(u)) {ue)
while C(u,) & 0 or N(us)) < R do
Up t arg min,, 8(v(u)). v(p)))
C(u,) + C(u)) {up} if up E (a,ENN L(u,, u5) then N(u)) +- ((;)) U {up)
Example 4 In Fig.
3c), assuming (u4) {ug, U4."..,, Ug]. we
{ and C(us) include ug in N(ua) because it lies within L(u, un) (the green region). Next, we add us to ((aa) since it belongs to L(us, un) O L(u;, u3). We continue this process until each new area has one neighbor of us Consequently, in the search procedure, we can efficiently route to the query object q by utilizing the neighbors of un present in the same area as q.
return N(us)
Complexity. To obtain C(u,), the time complexity depends on the methods used, so we skip this term in our analysis. The time complexity of sorting C(u.) is O(l (og(). For each up E C(us), we check at most [N (u:)) times (IN (u.)) S It) to see if up is in L(,, u,) for each uj E N (u,). So, our edge selection gets the final (ua) with no more than L- R checks. Thus, the time complexity of our edge selection on the vertex set V is O(l (R + log(()) IVD).
4.2 Routing
Routing is a crucial process for searching on a PG. It determines a path from the start vertex to the result vertex that matches the query. The routing strategy affects both the efficiency and accuracy of the search (39]. A recent study (58) splits routing into two stages: the far stage (SI) and the close stage (S2), based on how far they are from the query object.
Our routing. Algorithm 4 iillustrates our random two-stage routing strategy. In S1, we randomly select [R/h] neighbors from (ua) (where 1 < h < R, and R is the maximum out-degrce), and calculate their distances to the query object q. This enables us to quickly approach the neighborhood of q. In S2, we evaluate the distances of all neighbors in Nu,,) to 9. following a similar approach to the greedy search [19]. The tran- sition from SI to S2 occurs when SI reaches local optimum, indicated by further up- dates to the result set R. In S2, we continue updating R by checking all neighbors of the visited vertex. The process terminates when R no longer receives any updates.
Algorithm 4: Routing (G, q. P)
Input: PG G (V, query object q, seed set Output: Result set R
candidate set C' <- P: result set R t P forall {S1, S2} do
while R is updated do
ug - arg mitlaee 5(v(4), vuu)));
C= C (u:)
S1: M < [R/h] random neighbors of ua
S2: M < all neighbors of u,
CCCUM
forall uy E (u,) do
U, f- arg maxu, u())))
if ((v()),((u,) < 6(v(g),((u,))
then
R R R
R= RU Ru
Theorem 4 In the worst case, our rout- ing has the same Recall@k as the current greedy search [19].
C t R
return R
7

---

According to Theorem 3 (See Appendix L for the proof), our random strategy in SI does not reduce the accuracy because most vertices do not require distance calculation from the query in S1 and we can recover a small number of possibly missed vertices in S2.
Complexity. Previous works 36
show that the time complexity of greedy search state-of-the-ant PG (e.g., HNSW [36], NSG [9] is ( where R < [V] is the maximum roughly the average routing path length. In our routing, we use 1 and l2 to denote the average routing path lengths in SI and S2, respectively; then we have 1 + 12 log((V).
19
58
number of neighbors per vertex and log(
V(). Thus, our routing's time complexity is [(([R/h]) 1 + R 12).
4.3 NPG with Our Edge Selection and Routing
We present two NPGs, PG and N PGkgrrph, that use our edge selection and routing strategies on two basal PGs: NSW 35 and KGraph [4]. See Appendix M for implementation details.
5 Experiments
5.1 Experimental Setting
Table 1: Statistics of real-world datasets.
Dataset
Dimension
Blase
#'ueery
LID
[3]
Type
TQ-V
1,000)(K))
7.2
Video Attribates
Mssong
430
992,272
200
9.5
Audio + Altribules
Audio
192
53,387
200
5.6
Audio + Altributes
SIFTIM
128
1,000,000
10,000
9.3
Image Attributes
GIST TM
900
1,000U0])
1,000
18.9
Image i Aunihuses
1,989995
Attributes
GlaVe
100
1,183,314
10.000
200
Text i Artributes
200
Attributes
Paper
200
2,029,997
10,000
Text + Attributes
BICANNIDOM
128
100,000,000
Image + Attributes
Datasets. We use ten real-world datasets, including newly released dataset called Paper. They span various modalities, such as video, image, audio, and text. We summarize their main character- istics in Tab. [ With the exception of the Paper dataset, the remaining datasets solely consist of high-dimensional feature vectors without any original attributes. Therefore, we generate attributes for each object in these datasets using the similar method described in [51] 56). For instance, in SIFTIM IM, we augment each image with attributes such as date, location, and size, thereby creating an object set that comprises both feature vectors and attributes.
Compared methods. We compare our HQ methods with seven existing ones that have been used in many high-tech companies. ADBV [54] is a cost-based HQ method proposed by Alibaba. It optimizes IVFPQ (28 for ANNS. Milvus 33 51 divides the object set through frequently used attributes, and deploys ADBV 5el on each subset. Vearch [29] 32) is developed by Jingdong, which implements the HQ working off Strategy B. NGT (59 is a ANNS library released by Yahoo Japan, which answers HQ to conduct attribute filtering atop the candidates recalled by NGT (Strategy B). Faiss [17] is a ANNS library developed by Facebook, which answers a HQ based on IVFPQ (28 and Strategy A. SPTAG 37 is PG-based ANNS library from Microsoft, which answers HQ Strategy B. Filtered-DiskANY
21 proposes two optimizations based on DiskANN: Filtered Vamana and Stitched FilmaaadVamanaa connects vertices with shared attributes. Stitched builds separate graph indexes for each filter and overlays them. NHQ-N PG and NHQ-N PHQ-NPG PGkgraph are our HQ methods based on NHQ framework integrating two NPGs.
Metrics. We measure the search efficiency by queries per second (QPS), which is the number of queries (#4) divided by the search time (t), i... #g/t. We use the Recall rate to evaluate the search accuracy, which defined by Eq. 3 Unlike ANNS, hybrid query also requires attribute constraints in Eq. i.e., the elements in R n must have the same attributes as the query object.
Implementation setup. All codes are written C++, and are compiled by g++ 6.5. All experiments are conducted on Linux server with an Intel(R) Xeon(R) Gold 6248R CPU at 3.00GHz, and a 755G memory. We use 64 threads to build all the indexes in parallel. We use single thread for search, We report the average results from three trials.
which is common setting in related work [19 18).
8

---

10
101
1004
MMQ Wilnow
10
AHC Duulrin
10te
10
-B
10t
Stectedaaraaa
1014
Alsored JARAIN
0.50
0.85
RecHi030
6.80
USS
1.00
0.80
0.10
Rocar6000
0:30
0.85
1.00
Rccal19100
1.0
Accovi30
(a) SIFTIM
(h) Audio
In-memory
(b) On-disk
Figure HQ performance.
Figure 5: Comparison with new baselines.
5.2
HQ Performance
Fig. 4 Ashows that our methods outperform existing methods in terms of QPS vs Recall trade-off on all datasets. For example, NHQ-N N
CERQ-NPPrgrreee Pgrrrpphh achieves two three orders of magnitude higher QPS than others when @ecall@ 10 > 0.99. To execute -ieereddDiskAN,, we only test singlc-attribute queries in Fig. [ To eliminate other factors, we implement NHQ on DiskANN (NHQ can be easily extended to the current graph index), named WHQ-DiskANN We keep the same parameters in DiskANN. From the results, NHQ-DiskANN outperforms Siitered-DiskANe
both memory and disk versions.
101
AMG lesaaw
3000
10
(lean NCw
gio²
107
2000
1003
10
10
+ waser//natepp in
1W7 anggy
Ang.eNGhIsttaae C
10a
-
ASs #1
NHC eiay
pargctedtgr A)
U. Recon810
Recatiz10
Aecal1910
Recansio
(a) BIGANN 100M
(b) BIGANN1OOM
HNSW (SIFTIM)
(h) NSG (SIFTIM)
Figure 6: HQ performance on larger dataset.
Figure 7: Comparison of different strategies.
5.3 Scalability on Larger Dataset
To test the scalability of NHQ, we implement HQ on the state-of-the-arr disk-resident PG, DiskANN [27]. using "first ANNS, then AF strategy AJ=-DisKANN) and our NHQ (NHQ-DiskANN), Both implementations have the same hyper-parameters for DiskANN. Fig. ((a) and (b) show the QPS and Mean 1/Os results for different Recall on BIGANNI0OM dataset. NHQ-DiskANN consistently beats AF-DiskANN by a large margin. For QPS, NHQ-DiskANN is 315x faster than AF-DiskANN when Recall @ 10=0.95, because NHQ-DiskANN reduces expensive random disk I/Os. For example, to get a recall of 0.95, AF-DiskANN needs 1,303 disk I/Os, while NHQ-DiskANN only needs 30 I/Os, saving about 97.7% of disk I/Os. This shows the scalability of NHQ to handle larger dataset.
5.4 Ablation Study
Validation of NHQ framework. We test the universality of our NHQ (Strategy C) by applying the
HQ model with "decomposition-ssemmbby to different PGs (including HNSW [36 and NSG (19) based on "first ANNS, then AF" (Strategy B in Appendix(A) (A). We also use IVFPQ (2 in "first AF,
then ANNS" (Strategy A in Appendix A) following state-of-the-art implementation 154 51 because Strategy does not support PG (L4 in LLII. We integrate HNSW and NSG into NHQ to form
NHQ-HNSW and NHQ-NSG, respectively. As Fig. shows, NHQ outperforms other strategies different PGs, and keeps stable QPS advantage on different datasets. Due to IVFPQ's s limitations, the HQ based on Strategy A have low accuracy, e.g., Recall@10 < 0.8 SIFTIM.
1010
El Plas
1074
Cart now
10
1044
1040
10G
A0C-4 AND WWSW
10a
0.50
0.25
SIFTIM
0300
1D
0355
1,00
0.50
0.50
GISTIM
0.30
4.55
100
Recally (a)
SIFTIM
0.5
0.85
(b) Glo
US0
Recallii
636
Figure 8: Effect of our edge selection strategy.
Figure 9: Effect of different PGs.
Effect of our edge selection strategy. We compare our edge selection strategy with four existing ones: NGT 59 HNSW 36), HCNNG (39. and NSG [19 on SIFTIM and GISTIM datasets using a recent evaluation framework [52]. All competitors use the same routing inference and distance function. We measure the Speedup Recall metric, where Speedup is relative to brute force. Fig.

---

shows that our strategy outperforms the others. For example, at Recall @ 10=0.9 on SIFTIM, our strategy achieves 1.1 x, 1.4x. and 2 speedup over HCNNG/NSG, HNSW, and NGT, respectively.
Table 2: Comparison of different routing strategies.
Speedup (vx. INNSW)
Index (MB)
Memory (MI)
HNSW
1.00
790
3,571
8073
3,884
T0GG
1.30
N07
3,88
FINGER
1.30
2,150
11,625
Ours
1.21
790
3,871
Effect of our routing strategy. We compare our routing strategy with three existing ones: TOGG 58 FINGER [8), and HCNNG [39] within the HNSW index framework with consistent parameters.
Tab. 2 shows the speedup of each optimized strategy over the original HNSW at Recall @ =0
on SIFTIM. All optimized strategies are faster than the original HNSW, indicating the benefit of optimizing the routing procedure. Our strategy has the lowest storage cost, does not require extra structures. Moreover, it delivers a significant improvement in search performance.
Effect of different PGs under NHQ. We compare the performance of three PGs on NHQ: HNSW 36), NSG [9) and our KgGkgraph- We call them NHQ-HNSW, NHQ-NSG, and NHQ- N PGkkrrpp respectively. Fig. 9 shows their results on SIFTIM and GloVe. NHQ-NPG outperforms the others, especially on the harder Vlo dataset.
6
Discussion
Memory overhead. NHQ has a higher memory cost than Faiss when considering their best trade-offs. This is common drawback of graph-based methods compared to PQ-based methods in the ANNS community. This is mainly because graph-based methods build an extra proximity graph index (stored an adjacency list) to speed up the online search process. While graph-based methods have a higher storage cost, they achieve a significantly better trade-off between accuracy and efficiency and have become the mainstream algorithms in vector databases (such Milvus (51). Our NHQ framework enhances the ability of current graph-based methods to handle ANNS + AF.
Warch
ADDV
Mivus
Faus
SPTAG
-07
10a
5 10a
10a
10'
102
0.75
0.80
0.66
0.80
0.30
1.00
0.89
0.85
0.50
0:95
1.00
0.4
0.5
0.6
0.7
G.5
0.5 1.0
Recall@:10
Recalig10
Recalige1
(a) 36
(b) 2
972
(c) = 26244
Figure 10: Hybrid query performance of different number of attribute combinations (2). Number of attribute combinations. We conduct QPS-Recall comparisons across different attribute dimensions (3. 6. 9} in Fig. 10 The corresponding number of attribute combinations (represented by 2) is (36, 972, 26244). We find that increasing z can pose challenges for both the NHQ and existing frameworks. However, NHQ demonstrates higher speedup over existing frameworks in scenarios with large= 2, indicating its potential advantage in handling diverse attribute sets efficiently.
7 Conclusion
In this paper, we address HQ, which is ANNS with attribute constraint. We present a NHQ framework that adapts most existing PGs (including disk-resident PGs, e.g., DiskANN (77) and optimizes them for HQ. We introduce two NPGs with enhanced edge selection and routing strategies that achieve better ANNS performance than original PGs. We integrate several PGs into NHQ to implement HQ methods that are up to 315x faster than the state-of-the-as alternatives. A possible future and ongoing work is to apply our framework to multimodal search to handle more complex query requirements.
Acknowledgments
This work was supported by the Primary R&D Plan of Zhejiang (2021 and 2023C03199 198) and the National NSF of China (62072149).
10

---

References
[1] A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search.
2021.
[2] Akhil Arora, Sakshi Sinha, Piyush Kumar, and Amab Bhattacharya. Hd-index: Pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. PVLDB, 1 11(8)99669199, 2018.
[3] Jianmin Bao, Dong Chen, Fang Wen, Houqiang Li, and Gang Hua. Towards open-set identity preserving face synthesis. In CVPR, pages 6713-6722, 2018.
[4] Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, and Artem Babenko. Learning to route similarity graphs. In ICML, volume 97, pages 475-484, 2019.
[5] Erik Bernhardsson, Martin Aumüller, and Alexander Faithfull. Benchmarking nearest neighbors. 2018.
[6] Prosenjit Bose, Vida Dujmović, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Vera Sacristán, Maria Saumell, and David R Wood. Proximity graphs: E, 6, 6, X and w. International Journal of Computational Geometry & Applications, 22(05):439-469, 2012.
[7] Antoine Boutet, Anne-Marie Kermarrec, Nupur Mittal, and François Taïani. Being prepared in a sparse world: The case of KNN graph construction. In ICDE, pages 241-252, 2016.
[8] Patrick Chen, Wei-Cheng Chang, Jyun- Yu Jiang, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. Finger: Fast inference for graph-based approximate nearest neighbor search. In WWW, pages
2023.
[9] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. SPANN: highly- billion-scale approximate nearest neighborhood search. In NeurlPS, pages
2021.
[10] Shivani Choudhary, Tarun Luthra, Ashima Mittal, and Rajat Singh. A survey of knowledge graph embedding and their applications. CoRR, abs/2107. 17.8422 2021.
[11] Benjamin Coleman, Santiago Segarra, Alexander J Smola, and Anshumali Shrivastava. Graph reordering for cache-efficient near neighbor search. In NeurlPS, pages
2022.
[12] John P. Collomosse, Tu Bui, and Hailin Jin. Livesketch: Query perturbations for guided sketch-based visual search. In CVPR, pages 2879-2887, 2019.
[13] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. CoRR, abs/1810.04805,, 2018.
Ming-Wei
[14] Wei Dong, Moses Charikar, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW, pages 577-586, 2011.
[15] Karima Echihabi. High-dimensional vector similarity search: From time series to deep network embeddings. In SIGMOD, pages 2829-2832, 2020.
[16) Karima Echihabi, Kostas Zoumpatianos, and Themis Palpanas. High-dimensional similarity search for scalable data science. In ICDE, pages 2369-2372, 2021.
[17] Facebook. A library for efficient similarity search and clustering of dense vectors. http:///stbbbooomcfccoocsssrarae
2018.
[18] Cong Fu, Changxu Wang, and Deng Cai. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility. TPAMI, 2021.
[19] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. PVLDB, 12(5):461 4744 2019.
[20] Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In VLDB, pages 518-529, 1999.

---

[21] Siddharth Gollapudi. Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy. Nikit Beg- wani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, et al. Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters. In WwW, pages 3406-3416, 2023.
[22] Long Gong, Huayi Wang, Mitsunori Ogihara, and Jun Xu. idec: Indexable distance estimating codes for approximate nearest neighbor search. PVLDB, 13(9):1483-144 2020.
[23] Ruiqi Guo, Philip Sun, Erik Lindgeen, Quan Geng, David Simcha, Felix Chem, and Sanjiy Kumar. Accelerating large-scale inference with anisotropic vector quantization. In ICML, pages 3887-3896, 2020.
[24] Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. Query-aware locality- sensitive hashing for approximate nearest neighbor search. PVLDB, 91): 2015.
[25] Qiujun Huang, Jingli Mao, and Yong Liu. An improved grid search algorithm of svr parameters optimization. In ICCT, pages 1022-1026, 2012.
[26] Xiao Huang, Jundong Li, and Xia Hu. Label informed attributed network embedding. In WSDM, pages 731-739, 2017.
[27] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion-point nearest neighbor search on single node. In NeurlPS, volume 32, 2019.
[28] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. TPAMI, 33(1):117-128, 2011.
[29] Jingdong. A distributed system for embedding- retrieval. https://gihub..om//earhhhh 2020.
[30] Amar Viswanathan Kannan, Dmitriy Fradkin, Ioannis Akrotirianakis, Tugba Kulahcioglu, Ar- quimedes Canedo, Aditi Roy, Shih-Yuaa Yu, Arnv V. Malawade, and Mohammad Abdullah Al Faruque. Multimodal knowledge graph for deep learning papers and code. In CIKM, pages 3417-3420, 2020.
[31] Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. Improving approximate nearest neighbor search through learned adaptive early termination. In SIGMOD, pages 2539- 2554, 2020.
[32] Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning Wang, and Yuan Chen. The design and implementation of real time visual search system on JD e-commerce platform. In Proceedings of the 19th International Middleware Conference, pages 9-16, 2018.
[33] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. Approximate nearest neighbor search on high dimensional data experiments, analyses, and improvement. TKDE, 32(8): 1475-1488, 2020.
[34] Peng Cheng Lin and Wan Lei Zhao. Graph based nearest neighbor search: Promises and failures. CoRR, abs/1904.02077, 2019.
[35] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45:61-68. 2014.
[36] Yury A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. TPAMI, 42(4))824-836, 2020.
[37] Mierosoft. Sptag: A library for fast approximate nearest neighbor search. http:///gihuu.ccommirrrooffffff
2020.
[38] Milvus. The world's most advanced open-source vector database. https///gitubh.commiivus io/milvus, 2019.
12

---

[39] Javier Alvaro Vargas Muñoz, Marcos André Gonçalves, Zanoni Dias, and Ricardo da Silva Tor- res, Hierarchical clustering- based graphs for large scale approximate nearest neighbor search. Puttern Recognition, 96: (66970, 2019.
[40]
Liudmila Prokhorenkova and Aleksandr Shekhovtsov. Graph-based nearest neighbor search: 2020.
From practice to theory. In ICML, pages
[41] Jianbin Qin, Wei Wang, Chuan Xiao, and Ying Zhang. Similarity query processing for high- dimensional data. PVLDB, 13(12)3447733400, 2020.
[42] Jianbin Qin, Wei Wang. Chuan Xiao, Ying Zhang, and Yaoshu Wang. High-dimensional similarity query processing for data science. In SIGKDD, pages 4062-4063, 2021.
[43] Jie Ren, Minjia Zhang, and Dong Li. HM-ANN: efficient billion-point nearest neighbor search on heterogeneous memory. NeurIPS, 2020.
[44] Eli Schwartz, Leonid Karlinsky, Joseph Shtok, Sivan Harary, Mattias Marder, Abhishek Kumar, Rogerio Feris, Raja Giryes, and Alex Bronstein. Delta-encodee effective sample synthesis method for few-shot object recognition. NeurIPS, 31, 2018.
[45] Larissa Capobianco Shimomura, Marcos R Vieira, and Daniel S Kaster. Performance analysis of graph-based methods for exact and approximate similarity search in metric spaces. In International Conference on Similarity Search and Applications, pages 18-32. 2018.
[46] Chanop Silpa-Anan and Richard I. Hartley, Optimised kd-trees for fast image descriptor matching. In CVPR, 2008
[47] Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, and Jingdong Wang. Results of the neurips' 21 challenge on billion-scale approximate nearest neighbor search. In NeurlPS, pages 177-189, 2021.
[48] Zhenan Sun and Tieniu Tan. Ordinal measures for iris recognition. TPAMI, (1(11)22211-222 2008.
[49] Godfried T Toussaint. The relative neighbourhood graph of a finite planar set. Pattern recogni- tion, 12(4):261-26)
1980.
[50] Nam Vo, Lu Jiang, Chen Sun, Kevin Murphy, Li-Jia Li, Li Fei-Fei, and James Hays. Composing text and image for image retrieval - an empirical odyssey. In CVPR, pages 1439-6448, 2019.
[51] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. Milvus: A purpose-built vector data management system. In SIGMOD, pages 2614-2627, 2021.
[52] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. PVLDB, 14(11):1964-199 1978, 2021.
[53] Zhenhua Wang, Bin Fan, Gang Wang, and Fuchao Wu. Exploring local and overall ordinal information for robust feature description. TPAMI, 38(11):2198-2211, 2015.
[54] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. Analyticdb-v: A hybrid analytical engine towards query fusion for structured and unstructured data. PVLDB, 13(12):31523316) 2020.
[55] Suping Xu, Lin Shang, and Furao Shen. Latent semanties encoding for label distribution learning. In IJCAI, pages 3982-3988, 2019.
[56] Xiaoliang Xu, Chang Li, Yuxiang Wang, and Yixing Xia. Multiattribute approximate nearest neighbor search based on navigable small world graph. Concurrency and Computation: Practice and Experience, 32(24), 2020.
13

---

[57] Xiaoliang Xu, Jun Liu, Yuxiang Wang, and Xiangyu Ke. Academic expert finding via (k, P)- core based embedding over heterogeneous graphs. ICDE, pages 338-351. 2022.
[58] Xiaoliang Xu, Mengzhao Wang, Yuxiang Wang, and Dingcheng Ma. Two-stage routing with optimized guided search and greedy algorithm on proximity graph. Ghowledge-Based Systems, page 107305, 2021.
[59] Yahoo. Nearest neighbor search with neighborhood graph and tree for high-dimensional data. 2016.
https///gttubb.oom/yyyoojjaaapap
[60] Wen Yang. Tao Li, Gai Fang, and Hong Wei. Pase: Postgresql ultra-high- approxi- mate nearest neighbor search extension. In SIGMOD, page 2241-2253, 2020.
[61] Zhao Zhang, Fuzhen Zhuang. Hengshu Zhu, Zhiping Shi, Hui Xiong, and Qing He. Relational graph neural network with hierarchical attention for knowledge graph completion. AAAI, pages 1612-9619, 2020.
[62] Wan-Lei Zhao, Hui Wang, and Chong-War Wah Ngo. Approximate k-nn graph construction: A generic online approach. IEEE Transactions on Multimedia, 2021.
[63] Weijie Zhao, Shulong Tan, and Ping Li. SONG: approximate nearest neighbor search on GPU.
In ICDE, pages 1033-1044, 2020.
[64] Yuke Zhu, Ce Zhang, Christopher Ré, and Li Fei-Fei. Building a large-scale multimodal knowledge base for visual question answering. CoRR, abs/1507.05670, 2015.
14


Reviews:
[{"review_id": "UffECHYMBK", "reviewer": "Reviewer_XZ58", "summary": "Attribute filtering (AF) is an important part of many scenarios using nearest neighbor search. Here, each data points has a feature vector in a geometric space and also a set of attributes (e.g., data, author) and queries must be matched to nearest vectors satisfying some attribute constraints.\n\nWhile many algorithms have been studied for the classic ANNS problem, ANNS + AF is hard and needs new algorithms. Recently, there has been a flurry of attempts at this. Some of the basic approaches include filtering results of classic ANNS (which tends be yield poor results) or building separate indices for each attribute (Which leads to duplication).\n\nThis paper proposed that a better way to address this might be to create a fusion distance that incorporates geometric distance between feature vectors and suitably normalized similary score between attribute vectors. They then argue that a proximity graph data structure can be built using this distance. And that this performs better than other baselines selected in the paper. ", "questions": "In preliminaries, can you clearly state the attribution filtering problem and the defintion of recall for attribute filtering problem? It is unclear how the attribute vectors or indexed data and queries are matched.\n\n\n Please describe the datasets clearly in the main section. Please describe the encoding l(.) function for your datasets.\n\nwhy are proximity graphs (PG) and not navigation graphs (e.g., NSG, HNSW) not the starting points for your construction. Proximity graphs tend to be disconnected even for non-AF use cases. Would like to see some analysis of connectivity of PG on AF-datasets.", "limitations": "-", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors identify and articulate an important problem.\nEmpirical comparisons are made with many baselines.", "weaknesses": "There is no description of the dataset design in the main section. In appendix O, the datasets are described as usual vector datasets with 3 attributes (e.g., date, location, size) It looks like each vector can only have one possible combination of the attributes. So one can model it is one attribute dimension (cross-product) In such a case, why it not be easier and faster to build separate indices for each possible choice of attributes? Isnt complex index design only needed when datasets have multiple labels with an attribute dimension? In any case, it is impossible to evaluate the algorithm without well motivated datasets.\n\nMissing baseline: filter-diskann [www'23], methods therein and equivalent code (in-memory and on-disk) are not compared. Instead weaker baselines are compared.\n\nThere is far too much greek notation. The notation can be greatly simplified for better readability. Simple pseudocode would also make for much better reading.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: Dataset Issue**\n\nWe appreciate your comments. Our datasets are diverse in size, # attributes, dimensions (feature and attribute vectors), and domains (image, video, etc.). Each vector has 3-9 attribute types with various values, common in real-world scenarios [1] [2].\n\nA data point with 3 attribute types (date, location, size) may have a value for each type. We agree that 3 values form one combination. But we consider not only the full combination of 3 values, but also partial combinations of 2 or 1 values. This leads to many combination cases (up to 26244 in our dataset). Some queries seek the nearest vectors that match partial attribute constraints (e.g., date regardless of location or size). Modeling the combination as a single attribute dimension is infeasible for such queries. Building separate indexes for each combination is also time-consuming [3] and impractical for queries with partial constraints. Hence, we designed a composite index that can handle diverse queries based on fused distances (it computes the preferred attribute dimensions while ignoring the unconstrained ones).\n\nWe’ll clarify the dataset design in the main text.\n\n**W2: Missing Baselines**\n\nThanks for your suggestions and sorry for the missing baselines. We noticed that Filtered-DiskANN [3] was released after our submission. Before that, we had considered all related work on hybrid queries and compared all SOTA methods.\n\nFiltered-DiskANN proposes two optimizations based on DiskANN: FilteredVamana and StitchedVamana. FilteredVamana connects vertices with shared attributes. StitchedVamana builds separate graph indexes for each filter and overlays them. These optimizations improve performance significantly. However, Filtered-DiskANN only supports single-attribute queries. This limits its applicability in scenarios requiring multiple attributes. For example, in product search, users may input a query image with color and size filters. Filtered-DiskANN cannot handle such cases. In contrast, NHQ supports any attribute combination in a query.\n\nWe now add a comparison between NHQ and Filtered-DiskANN on SIFT1M dataset. Each vector has 3 attribute types, with 6, 6, and 5 values respectively. To execute Filtered-DiskANN, we only test single-attribute queries for all competitors. To eliminate other factors, we implement NHQ on DiskANN (NHQ can be easily extended to the current graph index), named NHQ-DiskANN. We keep the same parameters in DiskANN. The results are in Fig. 1 of the attached PDF. NHQ-DiskANN outperforms Filtered-DiskANN, in both memory and disk versions. Upon analysis, we observe that SIFT1M has up to 180 attribute combinations, which may challenge Filtered-DiskANN in building a high-quality graph index. Additionally, when # attributes is large, StitchedVamana will build many graph indexes, increasing the indexing cost. Moreover, FilteredVamana only considers one matched attribute between a vertex and its neighbors, which also limits its application in complex attribute combinations.\n\n**W3: Presentation Issue**\n\nThank you for your suggestions to enhance readability. We'll use simpler symbols instead of Greek notation and add more pseudocodes. We'll also move the pseudocodes of the composite index and joint search from the appendix to the main text. Moreover, we'll provide the pseudocodes of our edge selection and routing.\n\n**Q1**\n\nThanks for raising this point. The AF problem involves an object set $C$ and a query object $q$ with attributes $a_1,\\cdots,a_m$ of size $m$. The goal is to find objects $G$ in $C$ that share the same attributes as $q$. For any $e\\in G$, it holds $\\forall i=1,2, \\cdots, m, e . a_{i}=q . a_{i}$, where $e . a_{i}$ is the value of attribute $a_i$ of $e$. Note that $q$ may have partial attribute combinations (see W1). In this case, $e$ can have any value for the unconstrained attribute types. For the ANNS+AF problem, we also require the feature vector of $e$ in $G$ to be closest to that of $q$, resulting in the ground-truth set $G^*$ of ANNS+AF. Hence, the recall for ANNS+AF is $\\frac{|R\\cap G^*|}{k}$, where $R$ is the result set from an ANNS+AF method, and $k$ is the result size. However, recall for AF alone is unnecessary, as AF requires all results to match $q$'s attribute constraint, leading to a recall of 1.\n\nTo illustrate attribute matching, consider an example with 2 attribute types: date and city. Suppose we have an object $e$ with $e.date=2023$ and $e.city=New\\ York$, encoded as an attribute vector [1,3]. When the attribute vector of a query $q$ is [1,3] or [1,null] (where 'null' means no constraint), the attribute distance between $e$ and $q$ is 0, indicating a perfect match. However, if $q$ is [2,1] or [null,1], the attribute distance is 2 since the attributes of $q$ and $e$ are mismatched.\n\nWe'll clarify AF in preliminaries.\n\n**Q2**\n\nThanks for your suggestions. We follow previous works [4] and use ordinal encoding (i.e., our l(.)) to obtain attribute vectors for all datasets. For example, “New York” is encoded as 1 and “Beijing” as 2. Note that l(.) can use other encoders such as one-hot encoding.\n\nWe'll clarify the datasets and l(.) in the main text.\n\n**Q3**\n\nMost navigation graphs diversify the neighbors on a base graph. For example, NSG and HNSW implement their edge selection based on KGraph and NSW, respectively, and achieve SOTA performance for ANNS [5]. Similarly, we build our navigation graph based on KGraph and NSW, using our edge selection. The results show that our strategy outperforms NSG and HNSW (see Fig. 2 of the PDF).\n\nWe evaluate the connectivity of PG on both AF-datasets and non-AF-datasets (see Tab. 1 in the PDF). The results show that PG has similar connectivity in both cases. We know that KNNG has poor connectivity due to the cluster characteristics of non-AF-datasets [5]. PG diversifies the neighbor distribution and connects clusters [6]. For AF-datasets, vectors in different clusters may have the same attributes, which helps connectivity in NHQ."}, {"review_id": "eIz2B54Xl5", "reviewer": "Reviewer_MN6o", "summary": "The paper discusses how hybrid query finds objects that are both similar to a feature vector and match some structured attributes. However, existing methods handle ANNS and attribute filtering separately, leading to inefficiency and inaccuracy. The paper proposes a new efficient and robust framework called native hybrid query (NHQ) and two new navigable PGs (NPGs) with optimized edge selection and routing, which improve the overall ANNS performance.", "questions": "1. Discuss the storage cost theoretically and experimentally of NHQ with PQ-based methods.\n\n2. Include results of NHQ without edge selection strategy. This comparison can help readers understand the strengths of the proposed edge selection strategy.\n\n3. Include more related works (HQ-based methods and edge selection strategies).", "limitations": "Please refer to Paper Weakness.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Optimized edge selection and routing are proposed which is efficient for ANNS problems.\n\n2. The authors perform a sufficient complexity analysis of the proposed method. This helps readers understand the superiority and limitations of the proposed method.\n\n3. Many experiments have been conducted. The authors have conducted experiments on multiple datasets to show their superiority in terms of accuracy, efficiency, and memory usage.", "weaknesses": "1. Compared to PQ-based methods, the PGs need more storage in runtime. Thus, a discussion on storage cost theoretically and experimentally of NHQ with PQ-based methods is necessary. There is still an improvement space on trade-off strategy on storage and efficiency.\n\n2. More related works (HQ-based methods and edge selection strategies) are needed.\n\n3. Lack of results of NHQ without edge selection strategy in ablution study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1, Q1: Storage Cost Analysis**\n\nWe appreciate your suggestions and agree that comparing the storage cost of NHQ and PQ-based methods is necessary.\n\n* Theoretically\n\nNHQ and PQ-based methods have the same attribute storage cost, so we only analyze their feature vector storage cost.\n\nPQ-based methods compress high-dimensional vectors into the Cartesian product of multiple sub-codebooks. Let a vector $x$ be split into $M$ sub-vectors $u_j$, $1\\leq j \\leq M$, of dimension $D^*=D/M$, where $D$ is a multiple of $M$. The sub-vectors are quantized separately using $M$ quantizers with $K$ centroids each. We need to store the $M \\times K$ centroids,  i.e., $KMD^* = KD$ floating-point values ($4KD$ bytes). Each vector is compressed as the code length $L=M\\log_2K$ ($L/8$ bytes). The storage cost of PQ on $N$ vectors is: $4KD + NL/8$ bytes.\n\nNHQ builds a graph index for $N$ vectors with at most $R$ neighbors each. We use the adjacency list (a vertex with $R$ neighbor ids) to store the index, costing $4R$ bytes. We also store each raw vector with $ZD$ bytes. The storage cost of NHQ on $N$ vectors is: $ZND + 4NR$ bytes.\n\nOn SIFT1M dataset, where $D=128$, $Z=4$, PQ sets $K=256$, $M=32$, costing 32131072 bytes (31MB). NHQ sets $R=20$, costing 592000000 bytes (565MB).\n\nNote that PQ is often combined with IVF, known as IVFPQ, which adds a coarse step to find probing centroids near the query. This increases the storage cost of PQ-based methods depending on specific optimizations.\n\n* Experimentally\n\nWe compare the storage cost of NHQ and PQ-based methods on eight datasets in Tab. 2 of the attached PDF.\n\nWe observe that: (1) NHQ costs more than PQ-based methods, consistent with our theory; (2) different PQ-based methods have different costs due to extra structures for optimization; (3) the same method has different costs on different datasets due to different optimal parameter configurations.\n\nNotably, PQ-based methods have low accuracy due to compression loss. As shown in [7] [8] and our experiments (Fig. 6 (a)-(c) of our paper), PQ-based techniques sacrifice accuracy (<0.8 on most datasets) for cost saving. In contrast, NHQ achieves close to 1 recall with high efficiency. Therefore, we believe that there is room for improvement in the trade-off between storage and search performance. We plan to explore this in our future work.\n\nWe'll add this analysis to our final version.\n\n**W2, W3, Q2, Q3: Missing Baselines/Ablations**\n\nWe appreciate your suggestions and have added more related works and evaluations on HQ-based methods and edge selection strategies.\n\n- HQ-based methods\n\nWe noticed that Filtered-DiskANN [3] was released after our submission. Before that, we had considered all related work on hybrid queries and compared all SOTA methods. Filtered-DiskANN proposes optimizations called FilteredVamana and StitchedVamana on DiskANN. FilteredVamana connects vertices with shared attributes. StitchedVamana builds separate graph indexes for each filter and overlays them. While these optimizations enhance performance, Filtered-DiskANN's limitation lies in its inability to handle queries with multiple attributes. In contrast, NHQ supports any attribute combination in a query.\n\nWe compare NHQ and Filtered-DiskANN on SIFT1M dataset, considering vectors with 3 attribute types. To execute Filtered-DiskANN, we only test single-attribute queries for all competitors. To eliminate other factors, we implement NHQ on DiskANN (NHQ can be easily extended to the current graph index), named NHQ-DiskANN. We keep the same parameters in DiskANN. The results are in Fig. 1 of the PDF. NHQ-DiskANN outperforms Filtered-DiskANN consistently, in both memory and disk versions. Upon analysis, we observe that SIFT1M has up to 180 attribute combinations, which may challenge Filtered-DiskANN in building a high-quality graph index. Additionally, when # attributes is large, StitchedVamana will build many graph indexes, increasing the indexing cost. Moreover, FilteredVamana only considers one matched attribute between a vertex and its neighbors, which also limits its application in complex attribute combinations.\n\n- Edge selection strategies\n\nWe add more related works on edge selection strategies, including NGT [9], HNSW [6], HCNNG [10], and NSG [11].\n\nNGT: It builds a KNNG by incrementally inserting vertices and obtaining their nearest neighbors through a greedy search. It then optimizes the distribution of neighbors for each vertex using an effective path adjustment strategy.\n\nHNSW: It generates a hierarchical graph, where the vertices on the upper-level graph are a subset of the lower-level graph. It not only selects the nearest neighbors for an inserted point but also considers the distribution of neighbors using a heuristic edge selection strategy.\n\nHCNNG: It divides the dataset into multiple hierarchical clusters, where all points in each cluster are connected through a minimum spanning tree.\n\nNSG: It deploys an edge selection strategy based on the monotonic relative neighborhood graph. It prunes edges by searching for candidate neighbors on a KGraph, which is a KNNG.\n\nWe compare our edge selection with the above four strategies on SIFT1M and GIST1M. To ensure a fair comparison, we implement our edge selection on a recent evaluation framework [5], which has deployed all above four strategies. Notably, all competitors use the same routing strategy and distance function. Fig. 2 (a) and (b) in the PDF show our strategy outperforms all other competitors for the Speedup-Recall trade-off. Our strategy also demonstrates more efficient index construction and smaller index size in Tab. 3 of the PDF.\n\nAdditionally, in Fig. 2 (c) and (d) of the PDF, we evaluate indexes with and without our edge selection strategy, keeping other design variables the same. The results show that our edge selection brings significant performance gains in both the context of HQ and ANNS.\n\nWe'll summarize the above analysis and include the main results in the revision."}, {"review_id": "cuEe9YCZ5f", "reviewer": "Reviewer_ffbB", "summary": "In this paper, authors tackle the problem of retrieving nearest neighbor items under constraints on attributes of the retrieved items. Each item is described by a feature vector and a set of discrete attributes. \n\nAuthors propose to use a distance function that uses weighted combination of feature vector based distance and discrete attribute based distance. \n\nTo support efficient retrieval for a given query and attribute constraints, authors use graph-based nearest neighbor search indices. The proposed hybrid distance function is used to build the graph in an offline step and to navigate the graph during test-time search.\n\nAuthors also propose two heuristics to improve graph construction and test-time graph navigation, and overall the proposed approach yields improvement over baselines.\n\nUpdate: I am leaning towards accepting the paper and have updated my rating from  `5: borderline accept` to `7: accept` after reading clarifications from the authors.", "questions": "- Performance for NPG_{kgraph} on SIFT1M dataset is reported in Fig 5c, 6c and 7a. But the three graph do not seem to match.\n- In Fig 5c), does NHQ-NPG_{kgraph} use proposed routing method and do other baselines (NHQ-HNSW and NHQ-NSG) use naive greedy search?\n- What hyper-parameters were tried for ANNS + AF filtering approach?\n- The proposed search strategy has two stages S1 and S2. How does transition from S1 to S2 happen?\n- Complexity in Sec 4.1 : If C(u_i) is selected through an additional index then it will not be a constant time operation. Also in the final results, is C(u_i) selected randomly or using some additional index (and what index)?\n- Some suggestion of writing and presentation\n    - Including gridlines in the plot can help reading the graph.", "limitations": "No discussion", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed idea of using a hybrid distance function (which combines feature vector and attribute based distances) provides significant improvement over two-stage inference pipelines that either retrieve based on feature vectors and then filter based on attributes or first filter based on attribute and then search over filtered items using feature vector.\n- The proposed approach outperforms popular baselines on a variety of datasets.", "weaknesses": "- Some missing baselines/ablations\n    - The three main contribution of the paper are\n        - a) New distance function for hybrid queries.\n        - b) New algorithm for constructing graph over items.\n        - b) New heuristic for efficiently navigating the graph at test-time.\n    - The experiments clearly show the advantage of using the hybrid distance function over two-stage search (which separately performs nearest neighbor retrieval based on feature vector and then filters based on attributes).\n    - But individual contribution of the proposed graph construction strategy and the proposed graph navigation strategy is not clear.\n    - The proposed graph construction algorithm should be compared with NGT, HNSW, Munoz et al. (2019) while keeping every other design variable the same i.e. with the same test-time inference as well as with the same distance function.\n    - Similarly, the proposed graph search method should be compared with existing methods for speeding up search such as TOGG (mentioned in the paper), Chen et al., (2023), Munoz et al., (2019).\n- The presentation of the paper can be further improved.\n    - Most algorithms are described in text but it would help to present them in Algorithm boxes.\n    - While it is okay to use appendix for extra results, theorem proofs etc, I think some important details such as experiment setup, datasets and baseline description has also been moved to appendix. Reading the paper involved too many jumps between the main paper and the appendix. Authors could make the hybrid distance section more concise to make some space or move some extra results to appendix while keeping only main results in the paper.\n    - Proof for theorem 4 is missing\n\n*Patrick Chen, Wei-Cheng Chang, Jyun-Yu Jiang, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh. 2023. FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search. In Proceedings of the ACM Web Conference 2023 (WWW '23)*\n\nMunoz, Javier Vargas, et al. \"Hierarchical clustering-based graphs for large scale approximate nearest neighbor search.\" *Pattern Recognition*\n 96 (2019): 106970.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: Missing Baselines/Ablations**\n\nWe appreciate your suggestions and include the missing ablations to validate our edge selection and routing strategies.\n\n* Graph construction strategy\n\nWe compare our edge selection strategy with four existing ones: NGT [9], HNSW [6], HCNNG [10], and NSG [11] on SIFT1M and GIST1M datasets using a recent evaluation framework [5]. All competitors use the same test-time inference setup and distance function. We measure the Speedup-Recall metric, where Speedup is relative to brute force. Fig. 2 (a) and (b) in the attached PDF show that our strategy outperforms the others. For example, at Recall@10=0.9 on SIFT1M, our strategy achieves 1.1x, 1.4x, and 25.9x speedup over HCNNG/NSG, HNSW, and NGT, respectively. We also compare the index construction time and size of our strategy with the others in Tab. 3 of the PDF. Our strategy is faster and smaller than the others, demonstrating its superior efficiency and cost.\n\n* Graph navigation strategy\n\nWe compare our graph navigation strategy with three existing ones: TOGG [12], FINGER [13], and HCNNG [10] within the HNSW index framework with consistent parameters. Tab. 4 in the PDF shows the speedup of each optimized strategy over the original HNSW at Recall@10 = 0.9 on SIFT1M. All optimized strategies are faster than the original HNSW, indicating the benefit of optimizing graph navigation. Our strategy has the lowest storage cost among the optimized strategies, as it does not require extra structures unlike the others. For instance, FINGER's storage cost is 3x higher than the original HNSW. This confirms the efficacy of our strategy, which improves search performance and minimizes storage requirements.\n\n**W2: Presentation Issue**\n\nThank you for your suggestions. We'll move the pseudocodes of the composite index and joint search from the appendix to the main text and reorganize Section 3 for better clarity. Additionally, we'll include the pseudocodes of our edge selection and routing in the final version.\n\nWe appreciate you pointing out the issue of poor readability due to important details being placed in the appendix. To address this, we'll move some crucial details (such as the experiment setup, datasets, and baseline description) into the main paper. Furthermore, we'll improve the hybrid distance section to make it more concise, allowing us to add these important details. Additionally, we'll transfer extra results from our experiments to the appendix, while retaining only the main results in the paper.\n\nWe have double checked our appendix, and the proof for theorem 4 can be found in Appendix L (bottom of page 18 in our appendix).\n\n**Q1**\n\nIn Fig. 5(c) and 6(c), we present the performance of the hybrid query (HQ) on the SIFT1M dataset. The difference in the scales of the axes makes the performance curves of NHQ-$NPG_{kgraph}$ appear mismatched, but they are actually identical in both figures. In Fig. 7(a), we report the performance of ANNS on SIFT1M. Therefore, it is natural that the QPS-Recall curve for $NPG_{kgraph}$ in Fig. 7(a) does not match the QPS-Recall curves for NHQ-$NPG_{kgraph}$ in Fig. 5(c) and 6(c).\n\n**Q2**\n\nYes, in Fig. 5(c), NHQ-$NPG_{kgraph}$ utilizes the proposed routing method, while the other baselines (NHQ-HNSW and NHQ-NSG) employ naive greedy search. We'll clarify this point in the revision.\n\n**Q3**\n\nIn the ANNS+AF filtering approaches, there are two types of hyperparameters involved.\n\nThe first type pertains to the parameters specific to the ANNS methods used. We determine the optimal parameter configuration for these methods by referring to their respective papers or repositories (if provided) or by performing a grid search (if not provided). For example, parameters such as the maximum number of neighbors ($M$) and the size of the candidate set when selecting neighbors ($ef_{construction}$) are considered for HNSW.\n\nThe second type of hyperparameter relates to the intermediate result size ($C$), where the intermediate results are obtained from the ANNS methods. We apply the AF on these intermediate results to produce the final hybrid query results. Thus, $C$ impacts both search efficiency and accuracy. Since the optimal $C$ value may vary depending on the dataset and queries, it's challenging to predict it in advance. Therefore, we conduct a grid search to determine the appropriate $C$ before conducting the query tests. It's important to note that we generate different QPS-Recall pairs by adjusting the search candidate size of the ANNS methods. For example, we modify the parameter $ef_{search}$ in HNSW to yield different QPS-Recall trade-offs.\n\nWe'll include the hyper-parameter discussion of all methods in our appendix.\n\n**Q4**\n\nThe transition from stage S1 to S2 in the proposed routing strategy occurs when stage S1 reaches a local optimum, indicated by the candidate set $R$ not being updated. In stage S2, we proceed to update the candidate set $R$ by checking all neighbors of the visited vertex. The search process terminates when the candidate set $R$ no longer receives any further updates.\n\nWe'll add a pseudocode of our routing strategy to clarify it in the revision.\n\n**Q5**\n\nIt's correct that if $C(u_i)$ is selected through an additional index, it will not be a constant time operation. We highlight that the complexity analysis in Section 4.1 of our paper is on the basis of a given $C(u_i)$. The total complexity analysis should consider the time complexity of obtaining $C(u_i)$. In the final version, we'll make sure to clarify this point.\n\nAs stated in Section 4.3 of our paper, our edge selection process relies on two basal proximity graphs: NSW and KGraph. We obtain $C(u_i)$ using these two graph indexes (please refer to Appendix M for more details). The time complexity of obtaining $C(u_i)$ is $O(|V| \\cdot \\log^2(|V|))$ and $O(|V|^{1.14})$ for NSW and KGraph [5], respectively.\n\n**Q6**\n\nThank you for the suggestion. We'll incorporate gridlines in all the plots to enhance readability."}, {"review_id": "rG3onedsuh", "reviewer": "Reviewer_7xuq", "summary": "The paper introduces a novel approximate nearest neighbor search framework which baked in attribute constraints via a single composite index compared to many existing two stage solutions. The framework is mainly relying on a newly proposed distance function that fuses both feature vector distances and attribute vector distances. Based on the new distance function, several proximity graph based ANNS methods have been developed. The paper presents an ablation study showing the merits of the methods. The experimental results shown on multiple popular landmark datasets outperform baseline methods.  \n", "questions": "There will be other challenges as the number of attributes increases. It may be worth discussing solutions if there are very high diversities of attributes among the data to be indexed. For example, different categories in product search may not share the same attributes (names). The total number of attributes could be considerably large, and it will also increase the attribute vector distance computation cost. The two stage approaches, e.g. AF + ANNS, are less likely to be constrained. ", "limitations": "No limitations of the work are discussed in the paper. \n\nPlease refer to my questions and comments in Weakness and Questions.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The proposed fusion distance is an excellent idea that enables the opportunities of the single composite index construction as well as the advantages over the legacy two-stage models. \n\nEach step of the method has been well-explained. In addition, most of the components have provided theoretical proof or support analysis.\n\nANN problems are often complicated in comparisons considering the nature of trade-offs among different factors including memory, accuracy, speed, etc. The paper has conducted sufficient experiments, ablation studies, and explanations of results. These strengthen the hypnosis and make the work overall to be solid. \n", "weaknesses": "Details about config or setups for some baselines are missing. For example, the parameters or usages of FAISS are not discussed. It makes it harder to understand why FAISS gets saturated at recall 80% as shown in Section 5.2. Is it possible that the number of probes in IVF has not increased sufficiently?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: Experimental Details and Faiss Recall Issues**\n\nThank you for your suggestions. Due to space limitations, we included the environment configuration and setups for the baselines in the appendix. We apologize for the omission of important details in the main paper. We'll improve the organization of the experiments section and include essential information such as experimental setup, datasets, and baseline descriptions in the main paper. Additionally, we'll also provide detailed elaborations in the appendix.\n\nIn FAISS, we utilize the popular IVFPQ algorithm. In the indexing phase, IVFPQ first divides the database vectors into coarse clusters using k-means and then applies product quantization (PQ) to compress the vectors into compact codes. PQ divides each vector into $M$ subvectors and assigns each subvector to one of $K$ centroids in a codebook. The codebook is learned by performing *k*-means on the subvectors. The PQ code of a vector is the concatenation of the cluster IDs of its subvectors. This representation allows each vector to occupy $M$ bytes, where $M$ is typically 8 or 16 or 32. In the searching phase, IVFPQ first identifies the nearest coarse clusters to the query vector. It then scans the inverted lists of these clusters to find the nearest PQ codes to the query vector using asymmetric distance computation (ADC). ADC calculates the distance between the query vector and a PQ code by summing up the distances between each subvector of the query and the corresponding centroid of the PQ code. This approach avoids the need to decompress the PQ codes and reduces the memory access cost.\n\nSome key parameters of IVFPQ include:\n\n- The number of coarse clusters, which determines the number of inverted lists created and the number of clusters searched in each query. A larger number of clusters results in finer-grained partitioning but also increases computation and memory overhead.\n- The number of subvectors $M$ and the number of centroids $K$ in PQ, which determine the level of compression achieved and the amount of quantization error introduced. A larger $M$ or $K$ leads to higher accuracy but also increases storage and computation costs.\n- The number of nearest clusters to search for each query, which determines the number of inverted lists scanned and the number of PQ codes compared. A larger number yields higher recall but also increases computation cost.\n\nWe determine the optimal parameters of IVFPQ for different datasets using the automatic parameter adjustment tool provided with FAISS. Due to compression errors, the recall rate of IVFPQ saturates at a certain value (e.g., ~80%), as widely observed in the literature [7] (refer to Fig. 2(a) of [7]), [8] (refer to Fig. 1 of [8]) and empirically verified in our experiments (Fig. 6(a)-(c) of the main paper). We would like to highlight that increasing the number of probes in IVF does not eliminate this limitation. Even when scanning all coarse clusters, the recall rate remains low. This limitation is a consequence of approximate distance computation.\n\nThank you again for bringing up these points, and I hope this explanation clarifies the behavior of FAISS and its limitations in achieving higher recall rates.\n\n**Q1: High Diversities of Attributes**\n\nThank you for your comments. It is indeed true that challenges arise as the number of attributes increases. To test the impact of varying diversities of attributes, we conduct QPS-Recall comparisons across different attribute dimensions {3, 6, 9}, as shown in Fig. 3 of the attached PDF file. Notably, the corresponding number of attribute combinations (represented by $z$) is {36, 972, 26244}. We find that increasing the number of attributes can pose challenges for both the NHQ and two-stage (e.g., ANNS+AF) frameworks. Here are some observations from our experiments:\n\n- Decreased QPS with increased number of attributes. The QPS decreases for all methods, including both NHQ and two-stage frameworks, as the number of attributes increases. For instance, when the number of attributes is 36, 972, and 26244, the QPS of the Vearch method is 1852, 725, and 106, respectively, for the same Recall@10 of 0.95. This decline in QPS highlights the fact that handling a larger number of attributes necessitates additional computational resources.\n- Higher speedup of NHQ over two-stage framework. NHQ demonstrates a higher speedup over the two-stage framework when dealing with a large number of attributes, despite the increased attribute vector distance computation cost in NHQ. For example, when the number of attributes is 36, 972, and 26244, with a Recall@10 of 0.95, NHQ achieves speedups of 9.0x, 17.2x, and 16.5x over Vearch, respectively. This indicates that NHQ is more efficient in scenarios with a large number of attributes compared to the two-stage framework. It's important to note that although NHQ may experience increased attribute vector distance computation costs, the two-stage framework is also affected by higher feature vector distance computation costs required to generate more intermediate results for attribute filtering. However, the feature vector distance computation cost is typically significantly higher than the attribute vector distance computation cost. As a result, the two-stage methods are more likely to be constrained by the number of attributes compared to NHQ.\n\nIn summary, increasing the number of attributes introduces challenges for both NHQ and two-stage frameworks, leading to decreased QPS. However, NHQ demonstrates higher speedup over two-stage framework in scenarios with a large number of attributes, indicating its potential advantage in handling diverse attribute sets efficiently."}]

Author rebuttal:
We would like to express our gratitude to all four referees for providing us with valuable suggestions regarding the presentation and experimental studies. These suggestions have been immensely helpful in enhancing the quality of our paper. In response to the major concerns raised, we have conducted additional key experiments and included the main results in the attached PDF file. Furthermore, we will carefully revise the methodology and experiment sections to enhance their readability in the final version. Please refer to the detailed responses provided below for each individual reviewer. Due to space limitations, we put all references in here.

**References**

[1] VLDB'20: Wei, et al. Analyticdb-v: A hybrid analytical engine towards query fusion for structured and unstructured data.

[2] SIGMOD'21: Wang, et al. Milvus: A purpose-built vector data management system.

[3] WWW'23: Gollapudi, et al. Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters.

[4] TPAMI'15: Wang, et al. Exploring local and overall ordinal information for robust feature description.

[5] VLDB'21: Wang, et al. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search.

[6] TPAMI'18: Malkov, et al. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs.

[7] NeurIPS'19: Jayaram Subramanya, et al. Diskann: Fast accurate billion-point nearest neighbor search on a single node.

[8] NeurIPS'20: Ren, et al. HM-ANN : Efficient billion-point nearest neighbor search on heterogeneous memory.

[9] SISAP'16: Iwasaki, et al. Pruned bi-directed k-nearest neighbor graph for proximity search.

[10] PR'19: Hierarchical clustering-based graphs for large scale approximate nearest neighbor search.

[11] VLDB'19: Fast approximate nearest neighbor search with the navigating spreading-out graph.

[12] KBS'21: Xu, et al. Two-stage routing with optimized guided search and greedy algorithm on proximity graph.

[13] WWW'23: Chen, et al.  FINGER: Fast inference for graph-based approximate nearest neighbor search.

Meta-review: The paper introduces a novel approximate nearest neighbor search framework which baked in attribute constraints via a single composite index compared to many existing two stage solutions. 

The reviewers are overall positive on the ideas and rebuttals. MN6o: satisfied with the experiments and sufficient complexity analysis. ffbB: After rebuttal, satisfied with the rebuttal on experiments and presentation, scored from 5 to 7. 7xuq: idea is excellent. 

After the rebuttal, Reviewer XZ58 still has concerns on the presentation, but "Overall, I don't disagree with the ideas". After read the comments and discussions of others as well as the paper, I feel that the concerns are resolvable in the final version, and encourage the authors to refine as promised in the rebuttal.

Based on the paper, reviews, rebuttals and discussions, I would like to recommend to accept as Poster.
Decision: Accept (poster)