CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search
Authors: Ming Yang
Yuzheng Cai
Weiguo Zheng
Venue: NeurIPS 2024 poster (2024)
Keywords: similarity search
approximate nearest neighbor search
high-dimensional space
graph index
Primary area: other
TL;DR: A graph-based schema for ANNS

Abstract: The state-of-the-art approximate nearest neighbor search (ANNS) algorithm builds a large proximity graph on the dataset and performs a greedy beam search, which may bring many unnecessary explorations. We develop a novel framework, namely *corssing sparse proximity graph (CSPG)*, based on random partitioning of the dataset. It produces a smaller sparse proximity graph for each partition and routing vectors that bind all the partitions. An efficient two-staged approach is designed for exploring *CSPG*, with fast approaching and cross-partition expansion. We theoretically prove that *CSPG* can accelerate the existing graph-based ANNS algorithms by reducing unnecessary explorations. In addition, we conduct extensive experiments on benchmark datasets. The experimental results confirm that the existing graph-based methods can be significantly outperformed by incorporating *CSPG*, achieving 1.5x to 2x speedups of *QPS* in almost all recalls.

CSPG: Crossing Sparse Proximity Graphs for A Approximate Nearest Neighbor Search
Ming Yang, Yuzheng Cai, Weiguo Zheng
School of Data Science, Fudan University, China
yangm24, yuzhengcai21 em.fudan.edu.cm zhengweiguo@ fudan.edu.co
Abstract
The state-of-the-art approximate nearest neighbor search (ANNS) algorithm builds a large proximity graph on the dataset and performs greedy beam search, which may bring many unnecessary explorations. We develop a novel framework, namely corssing sparse proximity graph (CSPG), based on random partitioning of the dataset. produces a smaller sparse proximity graph for each partition and routing vectors that bind all the partitions. An efficient two-staged approach is designed for exploring CSPG, with fast approaching and cross- cross-partiiee partition expansion. We theoretically prove that CSPG can accelerate the existing graph-based ANNS algorithmss by reducing unnecessary explorations. In addition, we conduct extensive experiments benchmark datasets. The experimental results confirm that the existing graph-hased methods can be significantly outperformed by incorporating CSPG, achieving 1.5x 2x speedups of QPS in almost all recalls.
1 Introduction
Nearest Neighbor Search (NNS) aims to find some vectors a set of high- high-dimensional vectors with the smallest distance to query vector. It is becoming increasingly popular in various application domains [17],, such as information retrieval S (9] pattern recognition (TO. 11, recommendation
systems 12 133 and retrieval augmented generation (RAG) [1 15). However, it is costly to find the
exact nearest neighbors in practice, thus recent studies have focused on Approximate Nearest Neighbor
Search (ANNS), which targets efficiency while mildly relaxing accuracy constraints [16] 17
Existing ANNS algorithms can divided into four categories [6], including tree-based approaches 21 hashing-based approaches 22 quantization-based approaches (28-31), and graph- based approaches 66 35). Among these approaches, graph-based ANNS algorithms stand out with the high answer quality and low latency [16], by constructing Proximity Graph (shorted as PG) on the given vector dataset. As shown in Figure T each vector is represented by a node in the graph, and each node is connected to its nearby neighbors.
For the greedy beam search over the proximity graph, is observed that the distance computation dominates the overall time cost 33 37 Since at each step, all neighbors of the current node are pushed into the candidate set according to the computed distance. The number of distance computations can be calculated as multiplied by the number of explored nodes (6), where is the average degree of the graph. Intuitively, searching within a smaller graph requires less exploration and thus reduces the overall cost, which has been proved for particular type of proximity graph, i.e., Monotonic Search Network (MSNET) 6 38) However, for most proximity graphs, it is very likely to degrade the answer quality when the graph is smaller.
In this paper, we present a novel and effective framework, namely Crossing Sparse Proximity Graph (CSPG), enabling efficient search while not sacrificing answer quality. The basic idea is to reduce the number of explored vectors by searching in the much smaller graphs. Specifically, we randomly divide the whole dataset into several partitions, and for each partition, construct proximity graph that is smaller than the proximity graph built on the whole dataset. These partitions share set of routing
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Example Dataset
Query Nearby
Query Nearby
Search Path
Pi
12
U1
UO
(a) An example dataset of vectors
(h) Relative Neighhorhood Graph (RNG)
Figure 1: An example dataset of vectors and its proximity graph.
vectors (Section 3.1) that allow the greedy search to travel across different partitions dynamically. The query process involves two stages, i.e., fast approaching and eross cross-partiiee partition expansion. The first stage conducts the greedy search within one partition, using small candidate set to quickly approach the nearby regions of the query vector. Then, the second stage continues the greedy search with larger candidate set, allowing it to travel across different partitions for more precise results.
We theoretically prove that the expected number of explored vectors when searching across these small graphs is the same as searching on the small proximity graph for one of the partitions. Hence, by random partitioning with randomly sampled routing vectors, we can reduce the number of explored vectors compared with the traditional proximity graph built on the whole dataset, thus reducing the number of distance computations. By integrating CSPG with various graph- based ANNS algorithms, extensive experiments show that it significantly speeds up the query performance on benchmark datasets, and the detailed empirical results also align with our theoretical analysis.
Contributions. In summary, we make the following contributions in this paper.
To improve the query performance by reducing the number of explored vectors, we propose a general framework, namely Crossing Sparse Proximity Graph (CSPG), through random partitioning and random routing vectors. This framework can integrate with and enhance the existing graph- based ANNS indexes.
We develop an efficient two-staged search paradigm over the CSPG, including fast approaching and cross-partition expansion.
We theoretically prove that CSPG can benefit the existing graph-based ANNS algorithms by introducing Approximate Monotonic Search Network (AMSNET) that considers the distance backtracking in the search path.
Extensive experiments confirm that by integrating the CSPG, the existing graph-based based algorithms can be speeded up significantly under the same answer quality.
2 Background
2.1 Problem definition
Let D {11, U2, )n denote the dataset of n vectors, where represents vector in the d- dimensional Euclidean space Rd,, The L2 distance between any two vectors p E H and E Id is denoted as 5(p. q). The task of k-nearest neighbor search (k-NNS) can be defined follows.
Definition (k-Nearest Neighbor Search, shorted as k-NNS). Given dataset D and query vector q. k-NNS returns a subset of vectors, denoted by T C D, such that for any E T and \T,, we have ō(v, q) 8(t,g).
Definition 2 (l-Approximate Nearest Neighbor Search, shorted as k-ANNS ). Given a dataset 'D and a query vector q, k-ANNS returns subset vectors, denoted by S C D, such that [S n T) is as large as possible, where T. is the answer set to k-NNS w.r.t. the query For simplicity, is omitted when k 1.
In other words, the task of k-ANNS returns & approximate closest vectors of the query vector, not guaranteeing all the exact top-k nearest vectors, to improve query efficiency.
2.2 Graph-based ANNS algorithms
As discussed above, graph-based ANNS algorithms conduct a best-first greedy beam search on the proximity graphs to approach the closest nodes for query vector. Their built proximity graphs can be classified into four categories [16 40) as follows. Please refer to Appendix Aoror more details.

---

Delaunay Graph (DG) 42). It ensures that for any edge, no other vectors will be situated within the hypersphere defined by an edge connecting two vectors, where the hypersphere is centered the midpoint of the edge and the length of the edge is the diameter.
Relative Neighborhood Graph (RNG) [39] It guarantees that for any edge between and g, no other vectors will reside within the lune(p, q) = {u E IR ( p) I 6(p. q) 8(u, q) S 9)).
RNG imposes stricter restrictions on its edges, thus decreasing the average degree [43]
K-Nearest Neighbor Graph (KNNG) 44 In KNNG, neighbors of each vector v E 'D are its top-k
nearest neighbors in D. NN-Descent 44 proposes method for constructing KNNG.
The MST utilizes distances between vectors as edge weights. Then, it performs hierarchical clustering on the dataset multiple times randomly, adding some edges to the edge set. MST can establish global connectivity with minimal number of edges.
Minimum Spanning Tree (MST) Graph 45
2.3 Monotonic Search Network
Monotonic Search Network provides theoretical results to understand the costs of greedy search.
Definition 3 (Monotonic Path, shorted MP (8). Given a proximity graph built on dataset D, for two nodes p and u in the graph, a path from to u is denoted as p ~- u = {U1, 02: ..., ve). where p U1 and Ut. It is a monotonic path iff it satisfies that 6(01, u) >> 8(V2, u) ... 6(U,-1, u).
Definition& 4 (Monotonic Search Network, shorted as MSNET (8).. Given a dataset D consisting o vectors in the space Rd, a proximity graph built on D is called a monotonic search network iff there exists at least one monotonic path from p to u. for any two nodes p and u in D.
When running greedy beam search in an MSNET, since the distance strictly decreases at each step, i.e., distance backtracking can be avoided [38]. Let C' denote the smallest convex hull that can cover a set of n d-dimensional vectors D, and let R represent the maximum distance between two vectors in DD Denote the volume of C as Ve and let V, R) represent the volume of a sphere with radius R. For an MSNET built on D, when there exists a constant x s.t. KVc 2 VB(,, Rt), which implies that the distribution of vectors should be relatively uniform (never in some extremely special shape), the search length expectation of an
will continuously approach the query vector
MSNET (denoted EM) is O (nd log n /Ar) as proved in (6). where
DE Ar min {18 (v1, v2) - 8 (vi, eg)l, 1ó (vi, U2) - (v2, wa)l, 18 (vi, v3) 5 (v2, va)l}
In other words, Ar the minimum distance difference for any non-isosceles triangle on D. As increases, Ar decreases and approaches constant value when n is large (6).
3 Crossing Sparse Proximity Graphs
3.1 CSPG: Crossing Sparse Proximity Graphs
An effecttvee approach to the k-ANNS problem is expected to identify more vectors that are closest to the query with a minimal cost. A straightforward approach is to relax edge selection by allowing vector to connect with both nearby and relatively distant neighbors. To guarantee efficiency, the node degree cannot be increased too much making it challenging to maintain both nearby and distant neighbors. To address the problem, we propose method to maximize the number of vectors searched near the query without increasing average node degrees. The basic idea is randomly partitioning the dataset D into multiple groups that share some common vectors, called routing vectors. Then a sparse proximity graph (shorted SPG) is built for each group of vectors. Since these SPGs are sparser than that built for the whole dataset D. allowing larger steps to approach the query quickly. Moreover, the routing vectors across multiple SPGs enable efficient fine-grained search. For ease of presentation, let PG(D) denote the proximity graph built on the dataset D.
Definition 5 (Random Partition). Given a vector dataset D. the group of subsets P1, P2.P2.... P Pr constitute a random partition of such that (1) (1))PUPS UP2U...UPP = DD 1PP....P..... = C. and (3) (P)C) n (P. (P, = 1 for i j. where PP; is randomly sampled from 'D and C is the common vectors shared by all the subsets (also called routing vectors).
Definition 6 (Crossing Sparse Proximity Graphs, shorted as CSPG). Given a vector dataset DD its CSPG(D) consists of multiple proximity graphs 91, 12.9..... 9m for D's random partition P2, , Pm. respectively, i.e., G. PG(P.).
Note that Pi is sparser than D as it is randomly sampled from D. Thus, the average edge length (i.c., the distance between two vectors) of the resultant proximity graph Gi is larger than that of the
3

---

Query Nearby
Query Nearby
First Stage
Second Stage
G2
Figure 2: An example of CSPG index, where the proximity graphs are built using relative neighbor- hood graph 91 and 92 (with very similar degree to Figure 16
proximity graph for D. Generally, any existing graph-based index can be used to build the proximity graphs in CSPG. Since the partitions share routing vectors, the corresponding proximity graphs are interrelated through these routing vectors. Hence, the routing vectors serve to navigate the greedy search across different proximity graphs. Let of denote that vector vj belongs to graph 9i-
Example 1. For the dataset 'D = {ri, v2...., vig Figure ! we build the CSPG Fig- ure 2 by randomly sampling 2 routing vectors C {va, 27). And there are two partitions Pi (1r, U3, 14. vs, 27, 09) and P2 = {12, U4, Ub 17, Ug). where routing vectors are highlighted in red, with the green graph representing 91 and the blue graph representing 92.
3.2 Novelty of CSPG
Comparison with Inverted File Index (IVF). Generally. IVF uses clustering algorithms (c.g.. k- means) to divide the dataset into buckets. During the search, it selects some buckets with the closest centroids w.r.t the query, after which vectors in such buckets will be scanned for final results. The buckets of IVF index disrupt the distribution of vectors in the original dataset. In contrast, CSPG preserves the original distribution by random partition, which diffuses all vectors, and the routing vectors are used for connecting all proximity graphs from different partitions.
Comparison with PG(D). The CSPG index is built based on random partitions, with the help of routing vectors for connectivity. When the number of partitions m 1, CSPG falls into the special case that builds a PG index over all vectors, which is consistent with most state-of saaee-of-theeaa art graph-based ANNS algorithms. Some existing PG index 46 47 also utilized similar ideas of using data partition and redundancy. Existing studies 446 47 uses k-means other methods to divide the dataset, and obtain some redundant vectors. Then, such algorithms also construct proximity graphs in each partition separately. which are eventually merged into large PG as the final proximity graph covering all vectors. Such existing techniques are developed to deal with a huge amount of vectors, making it feasible to handle large datasets. In contrast, the CSPG methods aim at building several proximity graphs to speed up query answering.
Comparison with HNSW. (1) From the perspective of redundancy, the lower level HNSW contains all vectors from the upper level. But in CSPG, there is common overlap between partitions, and the remaining points of different partitions are distinct. (2) From the perspective of structure, HNSW is a hierarchical structure. In contrast, CSPG serves framework rather than specific structure (hierarchical or flat), allowing to enhance query performance across a broad range of mainstream graph indices. HNSW transitions from top level to bottom level unidirectionally, while CSPG builds horizontally with smaller, sparser proximity graphs. (3) From the perspective of searching, HNSW only unidirectionally search each level from top to bottom, and the final results are obtained from the bottom-level graph. But CSPG can traverse back and forth between different sparse proximity graphs, collecting final results from various partitions. The performance of HNSW is closely tied to the quality of the bottom-level graph, while CSPG generates more diverse and robust answers by leveraging cross-partition traversal and result collection.
3.3 CSPG index construction and updates
Algorithm 2 presents the process for CSPG index construction. It first samples the routing vectors RV from dataset D, then the other vectors D) RV randomly assigned to partitions. Finally, for each partition P,, we construct the proximity graph by applying the graph-based based ANNS algorithm.
Since CSPG is framework based mainstream proximity graphs, current updating methods of the underlying graph index are applicable. Moreover, the random partitioning makes it highly flexible for vector insertion and deletion. Details are presented in Algorithms 3 and of Appendix

---

Algorithm Search on CSPG index
Require: CSPG index G = (G), G2, ..., ,m), query vector 4, parameters efi and e/2
Ensure: k nearest neighbors of 9
1: C tt= sclected entry vector p P1 visited t {p}
First stage starts
2: while [C do
(r, (r. <-
closest vector w.r.t. q in
4:
for all unvisited neighhor u of in G1 do
5:
C. c- CU {(u, 1)}, visited 4- visited U {u}
ir|c] > efi then remove the farthest vectors w.r.t to keep [C] ef2 7: p < the closest vector w.r.t in visited
6:
Second stage starts
8: C < {(p, wiisstee + (p)
while IC 0
10: (r,h) f- the closest vector w.r.t q in C
the
11:
for all unvisited neighbor u of in Gr do
12:
C <- L {(u,h) h)], visited <- visited U [u] if is routing vector then L L [(u, i (1, m) A h}
13:
14:
if [2]] > ef2 then remove the farthest vectors w.r.t. q to keep [ e/2
15:
return top-k closest vectors w.r.t. q in visited
Time and space complexity. For dataset DD with n vectors, the time and space cost of building index are (n)) and (S())), respectively, As each partition has s(1-AA] + An vectors, CSPG consumes O (m T (((1-)) Xn)) time and O m S [(1--)) + An) space, which is at the same order of magnitude comparing with the original costs for most graph-based ANNS algorithms.
Two-stage search on CSPG
The search process of CSPG is divided into two stages, i.e., fast approaching and precise search. Specifically, the first stage aims to quickly approach the query vector by using only one proximity graph, while the second stage will carefully search around by considering all partitions for the final closest vectors. Traditional beam search on single proximity graph maintains a fixed-size candidate set. In contrast, CSPG uses different sizes efi and e,f for the two stages respectively, where ef < ef2- Algorithm outlines the procedure of searching on the CSPG index.
4.1
The First Stage: exploring single partition for fast approaching
In the first stage, the algorithm quickly approaches the query nearby with a shorter search length and fewer neighbor expansions. As shown in Algorithm [ it conducts greedy beam search discussed in Section [ on the graph G1.
Example 2. Given dataset 'D and query vector & We build CSPG and conduct the first stage search (efi = 1) to approach the nearby region of the query within just I step (Figure[])
Fach proximity graph CSPG(D) smaller and sparser than the proximity graph for the whole dataset 'D (denoted as PG(D)). This sparsity allows the first stage search to use larger steps and fewer moves to approximate the query. On the other hand, CSPG uses a smaller candidate size efi, eliminating some expansions that do not contribute to the final results.
4.2
The Second Stage: cross-partition expansion for precise search
After the greedy search in the first stage, the candidate set contains the closest vector delivered the first stage from the first partition P1 w.r.t. the query vector. As shown in Algorithm [ after resetting the visited set, it continues the greedy beam search with a size ef2 for the candidate set L. In the second stage, the significant difference from the first stage lies in line 13] Specifically, if the expanded neighbor u is a routing vector, all its instances in all partitions will be pushed into L. This approach allows the search process to dynamically traverse different proximity graphs, maximizing the search space to include as many potential closest vectors as possible
Example This example continues the search from Example 2 For comparison, let us consider the traditional greedy beam search within PG(D). As shown in Figure [b] it takes 6 steps to approach the nearest neighbor vi (with fixed candidate set size ef = 3). For CSPG, it first conducts the first stage, then switches the candidate set size from efi to ef2 = 3 and enters the second stage for
5

---

more precise search in the query nearby as shown in Figure (the two stages have 4 steps in total). In the second stage, CSPG expands the neighbors of v/.. vector, both vî and v) are added to f. Next, the algorithm expands vig updating L to {ut, 1/. w/} as 07 is also a routing vector. Then, by expanding 17, we reach the closest node ng in 91.
{o1}. in G1. Since va is routing
Due to the sparsity of each proximity graph in CSPG, the search CSPG(D) approaches the query results faster than PG(D). Moreover, some expansions may be removed. For example, with a candidate size of ef2 2. the candidate set in Step 2 would be {ut, vř), removing fj due to the limited size, ignoring the unnecessary expansion to V/..
In PG(D), redundant vectors are mainly used to merge graphs. In contrast, CSPG leverages the distribution of routing vectors to ensure that the expansion of one graph aids in reducing expansions in other graphs. This means position reached by one graph can be accessed by other graphs without additional expansion. For example, moving from v to Ua in G2 allows continuing the search from ia to ug in G1. The search across multiple graphs in the second stage appears as though it is conducted within a single proximity graph. The total number of steps to traverse the query nearby is 3, fewer than the 4 steps in PG(D) while maintaining the same precision. In practice, with appropriate partitioning. CSPG outperforms traditional PG algorithms, as discussed in Section 6
5 Analysis of search efficiency
For most graph-based ANNS algorithms, calculating the distance between two vectors usually dominates the overall search time. In this section, we focus on the number of distance computations during query processing, denoted by C. We will show that the expected cost E[C'] for the proposed CSPG method is lower than the traditional PG under certain constraints.
5.1 The expected number of distance computations
Following the setting of previous work (6), assume that the start vector p and query vector g are randomly selected from the d-dimensional vector dataset. On the proximity graph G built on the dataset, the greedy search sequence is denoted by p ~ q = {VI, u2...., VzJ. where 01 = p, ir g. Denote Ip ~4 ql as its length. The search sequence length of an MSNET equals its search path length, as the search consistently approaches the query without backtracking. Recall that when exploring each node, all its unvisited neighbors are pushed into the candidate set, and their distance to q is computed. By assuming that the average degree of is a, the expected number of distance computation is [[[] = oR [[p ~ dl].
5.2 Expected search sequence length on Monotonic Search Network
As introduced in Section 2.3 for a Monotonic Search Network (MSNET), the expected length of the search sequence M Ip ull O ( n à log n // /Ar) (6). In CSPG schema, assume that there are m partitions (m < n), and the proximity graph G, on each partition P. is a MSNET. Since we randomly select routing vectors RV and then randomly divide the other vectors into m partitions, the distribution of vectors is the same in each partition. Then, we have the following theorem.
Theorem 1. Given a start vector s E RV and a query vector q E RV, by performing greedy beam each MSNET G; independently, we can obtain monotonic paths s' ~ q". where
search from
s¹.q¹ E G.. It holds that E ~+ q" = E - q' 1 S i. < m.
Proof. Since the distribution of vectors in each graph G; are the same, the assumptions for deriving the expected path length in 6 remain unchanged, thus they have the same expected path length. O
By starting the search on a random entry vector p in proximity graph G1. the routing vectors help us to travel across different partitions P; in the second stage. Thus, the search sequence of CSPG is composed several sub-sequences from different graphs 9, The following theorem reveals that the expected search sequence length of CSPG is the same as the case of searching on the PGG1).
Theorem 2. Denote ECSPG [|p ~ ql] as the expected length of search sequence in CSPG. Denote g0.1p ~* q/] as the expected sequence length when searching only on the graph Gy. It holds that ECSPG [|p qI] ES [pp 4
Please refer Appendix foor the detailed proofs. Based on Theorem in CSPG are MSNET, the expected search path length is
when the proximity graphs
CSPG [|p ~ g]] = 0 [p ~ 41] =
( (An
n21 2) m
3
log An+ n11 m1)-
2) 3 /Ar)
m7

---

5.3 Approximate Monotonic Search Network
Most proximity graphs in practice are the approximation of MSNET, where the search path may have detours due to the lack of some necessary monotonic paths, resulting in distance backtracking. Given a query vector 9. we say that vector u conquers q iff Ee E N (u), (u).8(v, q) < 8(u, q). denoted by u > (u * q). For a certain vector in the search path p ~ q. distance backtracking is avoided iff u > q. since when exploring u, we can visit v to strictly decrease the distance w.r.t. 4.
Intuitively, for the proximity graph 9, when the degree of every vector is large enough, likely to be met for any query vector q E G. which help to avoid distance backtracking. However, since the average degree is usually limited in practical proximity graphs, there is a probability that
is
vector u conquers a random query vector g E G, formally defined as p(u) Eveo ((w>g)) where I(u > q) = 1 iff > q. Next, introduce the Approximate Monotonic Search Network (AMSNET), which reduces distance backtracking by maximizing p(u) of each vector u.
Definition 7 (Approximate Monotonic Search Network, shorted AMSNET), Given a dataset D of n vectors, a proximity graph G built on D is called an approximate monotonic search network iff for every vector u E D, its neighbor set (u) satisfies that [W()) S a while maximizing p(u).
Theorem 3. For datasets with the same distribution, as the number of vectors n decreases, p(u) is monotonically non non-decreusing.
Please refer Appendix [ for detailed proofs. Since AMSNET allows distance backtracking,
there exists a detour factor w > 1 for the expected search sequence length. Specifically, when the underlying proximity graphs of CSPG are AMSNETs, the expected search sequence length
is BCSPG [Ip ~ 4]] = O w (Are =((-))))
log (An
-(1=2) m
/Ar Moreover, according to
Theorem for every vector u, dataset size decreases, p(u) is non-decreasing. In other words, the probability of distance backtracking at every vector is non-increasing as n decreases, thus w is non-increasing decreases. We confirm the monotonicity of w in Section
5.4 Speedup analysis for CSPG
For the dataset D of n vectors, we have the following assumptions as discussed above: (1) 3x, <VC 2 VB R). (2) > 1, À < I, and the vector distribution of cach partition P; is the same as D. (3) The proximity graphs built in PG and CSPG are AMSNETs with a degree upper bound of a.
When the proximity graph is AMSNET, the expected path length for PG method is EL =| =1=00l On à log n PG), where PG is the minimum distance difference for any non-isosceles triangle D. Similarly, CSSP is defined for each partition P. in CSPG. And the detour factor for PG and CSPG are denoted as w PG and CCPG respectively. Thus, considering the expected number of distance computations, the speedup ratio of CSPG over PG is
B 1p
all
PG
Ar CSPG
n log n
Speedup = RCSPO 9l
WCSPG
X ArPG
x
(An m(1-A)
log
An + m(1-))
Ar Since each proximity graph in CSPG are smaller than that in PG, and Section 5.3 shows that w is non-increasing
Define a up Pe
CSPO
decreases, PG 2 CSPG Also, since Ar decreases as n increases (6, we have CSPG 2 PG Thus, it holds that a 2 1. Next, we consider 3
lognd
In CSPG, each partition has less than r vectors when
(An+ n1 2)) log( (An+ a 2
m > 1 and A < 1, i.e., An + m(1-a) < and 8 > 1. Thus, Speedup = a. > 1, which ensures that CSPG always outperforms PG when using AMSNET. As the dataset size n increases, B is decreasing
and we have lim Speedup a 1)A+1 ==+30
Moreover, when - oo and d is increasing, is
also decreasing and lima-ro0 Speedup
6 Evaluation
6.1 Experimental setup
As summarized in Table four benchmark datasets are used in our experiments, which are the most commonly used public datasets come from Anr-benchmarks [48].
7

---

Table 1: Comparison for index construction cost, in which DS is the data size (MB), IS is the graph index size (MB), and IT is the index construction time (s)
SIFTIM
GISTIM
DEEPIM
SIFTIOM
index
DX
1S
DS
I8
IT
DS
1T
135
15
TINSW
253
33
254
237
251
28
2,596
416
Vamuna
97
120
388
1296
1,122
ICNNG
44
85
53
390
54
79
633
742
HNSW
488
389
50
3,662
380
382
587
48
1,221
3,894
627
CSPG
Vamana
195
145
186
608
192
136
1,938
1,627
HCNNG
77
131
81
465
86
119
934
1.128
HNSW
Mana
15PG-Vmmas
HCNNG
CSRG HCNNG
1w45
SIFTIM
1m3
GISTIM
165
DEEP1M
1
SIFTIOM
1.5
1.0
1.0
0.5
2.5
0.90
0.85
00
1.00
0.85
0.95
1.00
0.65
0.95
Rece
Recalig10
Recell@10
Recali@10
Figure 3: QPS v.s. recall curves for comparing query performance
Three well-known graph-based ANNS algorithms HNSW Vamana 46 and HCNNG 455 are
selected as baselines, which achieved competitive performance previous studies [16 49]. Also, we integrate each of them in the proposed CSPG method, resulting in three methods #SPG-HNSW VVPG-Vaman,,..m and CSPG-HCNNG. During the query phase, we set k- 10 and the quality of query results is evaluated by recal|@10. The detailed index construction and query processing parameters listed in Appendix D The efficiency of an algorithm is measured by Queries Per Second (QPS), which is defined as the number of queries processed per second. And the answer quality evaluated by recall@k |snz] which measures the overlap between the retrieved results S and the ground machine with Intel Xeon Gold 6136 CPU @ @3.00GHz and 128GB memory. We use 24 threads for both index construction and query processing. All our source codes are available at
truth T .llll experiments conducted
com/PUITAR/CSPG
6.2 Evaluating query performance
Figure presents the QPS-recall curve of the CSPG method built upon each graph-based ANNS algorithm, comparing it with the corresponding traditional PG implementation. For all these datasets and graph-based algorithms, CSPG method consistently improves the overall query performance. Specifically, CSPG helps the Vamana and HCNNG indices to achieve at least 1.5x speedup at fixed recall of 0.9 on all the datasets. Such acceleration is due to the significantly reduced number of distance computations, as illustrated by Figure TO The practical superior query performance of CSPG also aligns with the theoretical analysis in Section 5
6.3 Evaluating index construction
By default, we use sampling ratio of À 0.5 to divide the data into = 2 partitions. Thus, the total number of vectors in the two proximity graphs is (1 11--) A)m++ + Anm = 1.5n. As shown in Table I for each graph-based ANNS algorithm, the index construction time and index size of CSPG is roughly 1.5x of the traditional PG version. Though CSPG has a larger index size, it is still affordable since the memory consumption of the vector raw data is much larger than the indices.
6.4 Impact of factors and parameters
In this section, we investigate how potential factors and parameters affect the query performance.
Varying the dataset size. Take dataset SIFTIOM as an example, we randomly sample 0.1, 0.2, 0.5, 2, and million vectors and build the graph- based ANNS indices and the corresponding CSPG method, using the default parameter settings. As shown in Figure CSPG always achieves better performance compared with original algorithms over all the sampled datasets. For each graph-based ANNS algorithm, though CSPG always helps to improve the performance, such improvement becomes less obvious. It aligns with our theoretical results in Section 5.4. which shows that as n increases, the speedup ratio decreases but converges to value larger than 1.
8

---

HNSW
ESPG-HNSW
Vamana
CSPG-Vamana
HONNG
CSPG-HNUNG
le5
SIFTO.1M
2.55
SIFTO.2M
1e5
SIFTO.5M
1e5
1.55
SIFTSM
0.5
0.5
0.0
0.80
1.00
0.85
0.90
0.95
1.00
0.85
0.90
0.95
1.00
0.80
0.90
0.95
1.00
Recall@10
1ecalig
Recaligi0
Figure 4: Query performance when varying the dataset size 12
m-16
CSPG-HNSW
CSPG-Vamana
CSPG-HCNNG
1.5
2.5
QPS (917T3M)
2.0
2.0
0.5
0.5
0.50
0.25
0.85
0.90
0.95
1.00
0.85
0.95
1.00
Figure 5: Query performance when varying the number of partitions
A-0.1
A-02
A-0.3
A-0.4
A-0.5
3.65
CSPG-HNSW
165
CSPG-Vamana
1.5
CSPG-HCNING
3.5
1.00
QPS (SIFT1M)
2.0
2.0
0.75
0.5
0.5
0.59
0.25
0.90
0.95
0.80
0.90
0.95
0.50
0.85
0.90
0.95
1.00
Recal@10
Recalia00
10call8
Figure Query performance when varying the sampling ratio À
Varying the number of partitions. Since the number of partitions m affects the CSPG index quality, we conduct experiments for evaluating the query performance with m = 1, 2, 4, 8, 16 partitions, in which 1 indicates the original graph-based ANNS algorithm without partition. Note that the other parameters are the same as the default settings. Intuitively, larger m results in fewer vectors in each partition, and CSPG seems achieve better performance. However, large may decrease the similarity of vector distribution among different partitions, which contradicts the assumptions of the same vector distribution discussed in Section 5.. Therefore, for different datasets with various distributions, choosing an appropriate parameter m is crucial. As shown in Figure 5 for SIFTIM dataset, dividing all vectors into 2 or 4 partition results in better QPS-recall curves. Figure TT shows that the optimal value of m for the other datasets ranges from 2 to 8.
Varying the sampling ratio. When constructing the CSPG schema, the sampling ratio À is used to randomly sample An routing vectors before dataset partition. By using the default values of all the other parameters, Figure 6 reveals that for SIFT1M dataset, larger X tends to improve the query performance of CSPG. And also holds for other datasets, as shown in Figure [2] This is because more routing vectors help to navigate the search traveling across different partitions efficiently. Also, more routing vectors result in more shared vectors in each partition, increasing the similarity of vector distribution among different partitions, which is more aligned with the assumptions of the same vector distribution discussed in Section 5.4
Varying the candidate set sizes. CSPG has two parameters efi and efe for searching, limiting the size of the candidate set in the two stages, respectively. As shown in Figure| 7 and Figure [3] we try different ef 1, 2, 4, 8, 16 and obtain 5 QPS v.s. recall curves. The marks in each curve are obtained by varying the value of efz uniformly picked from [10, 300). In most cases, efi = 1 provides the best query performance, which aligns with our goal of the first stage fast approaching.
Statisties for detour factor. We randomly sample 0.1, 0.2, 0.5, 2, and 5 million vectors from SIFTIOM dataset. By using CSPG with the default parameter settings, at different Recall@k, we length of scarch sequence
obtain the empirical detour factor
length search sequence mumber distance backtracking averaged for all

---

elym1
mf
e6ym
efy166
1w5
CSPG-HNSW
165
CSPG-Vamana
165
CSPG-HCNNG
1.25
QPS (SITT.N)
1.00
0.25
0.80
0.85
0.30
0.95
1.00
0.80
0.55
0.30
0.95
1.00
9.90
0.55
0.90
0.95
1.00
Recaligr1
Recallg10
Recalig 10
Figure Query performance when varying the candidate set size e. the first stage
SIFTO.
SIFT0.2M
+ SIFTO. SM
SIFTZM
-
SIFTMM
CSPG-HNSW
CSPG-Vamena
1SPG-HCNNG
1.9
18
1.8
1.7
1.0
1.6
0.7
1.0
Recwiggto
Recalig10
Figure 8: Detour factor when varying the dataset size n
search paths. As shown in Figure 8 larger results in larger w at fixed Recallak, which aligns with our discussion Section 5.3 that non-increasing as n decreases.
6.5 Hyperparameter grid search and evaluation with ANN-Benchmarks
To show the Pareto frontiers with the optimal hyperparameters, conduct grid search experiment to identify the most effective hyperparameter combinations for each baseline on SIFTIM dataset. As presented in Appendix D we summarise the parameter selection sets for different indices in Table 4 and the results of the grid search experiment are illustrated in Figure 14
Next, we conduct a more comprehensive evaluation using the ANN-Benchmarte 48 which is widely used bench- marking environment. For each algo- rithm, we choose the optimal param- eters from the grid search experiment with the highest QPS when Recall 10 = 0.9 + 5e on SIFTIM dataset. As shown in Figure 9 enhanced with the proposed CSPG framework, representa- tive algorithms such as HCNNG, HNSW, Vamana and NSG achieve better per- formance on SIFTIM dataset.
HCNNG
CSPGHCNNN
0P5 (SFTIM)
Vimana
HNSW
CSPG-NSW
MSG
hifoef
falss hr
Rocall@10
Figure 9: QPS v.s. Recall @ 10 curve on SIFTIM with the optimal parameters in .NN-Bnnchssrks
7 Conclusion
We proposed novel graph-based indexing schema named CSPG for Approximate Nearest Neighbor Search (ANNS), which is compatible with the current leading graph-based approaches in high-recall scenarios. Furthermore, we propose a novel search algorithm for the CSPG schema, which uses two-stage strategy and cross pprstitttiiionn expansion to reduce meaningless expansion during the graph search and make the process more focused on the parts related the answer. Next, we analyze the expectation of CSPG's search amount, establish speedup model, and prove that CSPG can always have an advantage. Finally, we investigate the advantages of CSPG through experiments and earry out a more detailed evaluation of the key factors affecting the performance of CSPG.
10

---

Acknowledgments and Disclosure of Funding
This work was substantially supported Key Projects of the National Natural Science Foundation of China (Grant No. U23A20496) and Shanghai Science and Technology Innovation Action Plan (Grant No. 21511100401). Weiguo Zheng the corresponding author.
References
[1] Akhil Arora, Sakshi Sinha, Piyush Kumar, and Amab Bhattacharya. Hd-index: Pushing the callbility-acccuraae boundary for approximate knn search in high-dimensional spaces. arXiv preprint arXiv: 1804. 2018.
[2] Yu A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighhor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4))824-836, 2018.
[3] Kazuo Aoyama, Kazumi Saito, Hiroshi Sawada, and Naonori Ueda. Fast approximate similarity search based on degree-reduced neighborhood graphs In Proceedings of the 17th SIGKDD international conference on Knowledge discovery and data mining, pages 1055-1063, 2011.
[4] Minjia Zhang and Yuxiong He. Zoom: Ssd- based vector search for optimizing accuracy, latency 2018.
and memory. arXiv preprint
[5] Rentong Guo, Xiaofan Luan, Long Xiang, Xiao Yan, Xiaomeng Yi, Jigao Luo, Qianya Cheng, Weizhi Xu, Jiarui Luo, Frank Liu, al. Manu: a cloud native vector database management system. Proceedings of the VLDB Endowment, 15(12)33548 3561, 2022.
[6] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graph. arXiv preprint arXiv: DrXXiv/707.000 /ttp//0070044400 2017.
[7] Wenhui Zhou, Chunfeng Yuan, Rong Gu, and Yihua Huang. Large scale nearest neighbors search based neighborhood graph. In 2013 International Conference on Advanced Cloud and Big Data, pages 181-186. IEEE, 2013.
[8] Chun Jiang Zhu, Tan Zhu, Haining Li, Jinbo Bi, and Minghu Song. Accelerating large-scale molecular similarity search through exploiting high performance computing. In 2019 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 330-333. IEEE, 2019.
[9] Myron Flickner, Harpreet Sawhney, Wayne Niblack, Jonathan Ashley, Qian Huang, Byron Dom, Monika Gorkani, Jim Hafner, Denis Lee, Dragutin Petkovic, et al. Query by image and video content: The qbic system. computer, 28(9):23-322 1995.
[10] Atsutake Kosuge and Takashi Oshima. An object- pose estimation acceleration technique for picking robot applications by using graph-reusing k-nn search. In 2019 First International Conference on Graph Computing (GC), pages 68-74. IEEE, 2019.
[11] Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions on information theory, 13(1):21-27, 1967.
[12] Yitong Meng, Xinyan Dai, Xiao Yan, James Cheng, Weiwen Liu, Jun Guo, Benben Liao, and Guangyong Chen. Pmd: An optimal transportation-basee user distance for recommender systems. In Advances in Information Retrieval: 42nd European Conference on IR Research, ECIR 2020, Lisbon, Portugal, April 14-17, 2020, Proceedings, Part Il 42, pages 272-280. Springer, 2020.
[13] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. Item-based collaborative filtering recommendation algorithms. Proceedings of the 10th international conference on World Wide Web, pages 285-295, 2001.
[14] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:187771901,, 2020.
11

---

[15] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yi Dai, Jiawei Sun, and Haofen Wang. Retrieval -uggeented generation for large language models: A survey, arXiv preprini arXiv:2312. 10997, 2023.
[16] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2 12631, 2021.
[17] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. Approximate nearest neighbor search on high dimensional data eeaeeeexprmmetts. analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering, 32(8):1475-1488, 2019.
[18] Keinosuke Fukunaga and Patrenahalli M. Narendra. A branch and bound algorithm for comput- ing k-nearest neighbors. IEEE transactions on computers, 100(7):750-553, 1975.
[19] Norbert Beckmann, Hans-PPter Kriegel, Ralf Schneider, and Bernhard Seeger. The r-tree: An efficient and robust access method for points and rectangles. Proceedings of the 1990 ACM SIGMOD international conference Management of data, pages 322 331, 1990.
[20] Chanop Silpa-Anas Anan and Richard Hartley. Optimised kd-trees for fast image descriptor matching. In 2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1-8. IEEE, 2008.
[21] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Com- munications of the ACM, 18(9):509-511) -175009--77-11 1975.
[22] Hosagrahar V Jagadish, Beng Chin Ooi, Kian-Lee Tan, Cui Yu, and Rui Zhang. idistance: An adaptive b+-tree based indexing method for nearest neighbor search. ACM Transactions Database Systems (TODS), 30(2):364 (02):3344397,,0000
[23] Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. Query-aware locality- sensitive hashing for approximate nearest neighbor search. Proceedings of the VLDB Endow- ment, 1-1::1-12, 2015.
[24] Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. Similarity search in high dimensions via hashing. In Vldb, pages 518-529, 1999.
[25] Jinyang Gao, Hosagrahar Visvesvaraya Jagadish, Wei Lu, and Beng Chin Ooi. Dsh: data sensitive hashing for high-dimensional k-nnsearch. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 1127-1 138, 2014.
[26] Yingfan Liu, Jiangtao Cui, Zi Huang, Hui Li, and Heng Tao Shen. Sk-Ish: an efficient index structure for approximate nearest neighbor search. Proceedings of the VLDB Endowment, 7(9): 745-756, 2014.
[27] Yair Weiss, Antonio Torralba, and Rob Fergus. Spectral hashing, Advances in neural information processing systems, 21, 2008.
[28] Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. Cache locality is not enough:
nearest neighbor search with product quantization fast scan. In 42nd International Conference on Very Large Data Bases, page 12, 2016.
[29] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization for approxi- mate nearest neighbor search. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2946-2953, 2013.
[30] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEFE transactions on pattern analysis and machine intelligence, 33(1):117-128, 2010.
[31] Jianyang Gao and Cheng Long. Rabitq: Quantizing high-dimensional vectors with theoretical error bound for approximate nearest neighbor search. Proceedings of the ACM on Management of Data, 2(3):1-27, 2024.
12

---

[32] 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.
[33] Sunil Arya and David M Mount. Approximate nearest neighbor queries in fixed dimensions. In SODA, volume 93, pages 271-280. Citeseer, 1993.
[34] Yubao Wu, Ruoming Jin, and Xiang Zhang. Fast and unified local search for random walk based k-nearest-neighhor query in large graphs. In Proceedings of the 2014 ACM SIGMOD international conference on Management of Data, pages 1 1139-1150, 2014.
(35] Kiana Hajebi, Yasin Abbasi- Yadkori, Hossein Shahbazi, and Hong Zhang. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Twenty- Second International Joint Conference Artificial Intelligence, 2011.
[36] Zeyu Wang, Haoran Xiong, Zhenying He, Peng Wang, et al. Distance comparison opera- tors for approximate nearest neighbor search: Exploration and benchmark. arXiv preprint arXiv:2403.13491, 2024.
[37] Jianyang Gao and Cheng Long. High-dimensional approximate nearest neighbor search: with reliable and efficient distance comparison operations. Proceedings of the ACM on Management of Data, 1(2):1227, 2023.
[38] DW Dearholt, N Gonzales, and G Kurup. Monotonic search networks for computer vision databases. In Twenry- -econd Asilomar Conference on Signals, Systems and Computers, vol- ume 2, pages 548-553. IEEE, 1988.
[39] Godfried T Toussaint. The relative neighhourhood graph of a finite planar set. Pattern recogni- tion, (2(4):261-268 1980.
[40] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. Efficient approxi- mate nearest neighbor search in multi-dimensional databases. Proceedings of the ACM on Management of Data, 1(1):1-27, 2023.
[41] Franz Aurenhammer. Voronoi dlagrams-asunne of a fundamental geometric data structure. ACM Computing Surveys (CSUR), 23(3):345-403 1991.
[42] Ben Harwood and Tom Drummond. Fanng: Fast approximate nearest neighbour graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5713-5722 2016.
[43] Jerzy W Jaromezyk and Godfried T Toussaint. Relative neighborhood graphs and their relatives. Proceedings of the IEEE, 1009):1502-1517, 1992.
[44] Wei Dong, Charikar Moses, and Kai Li. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th international conference on World wide web, pages 577-586, 2011.
[45] Javier Vargas Munoz, Marcos A Gonçalves, Zanoni Dias, and Ricardo da S Torres. Hierar- chical clustering-basee based graphs for large scale approximate nearest neighbor search. Pattern Recognition, 96: 16:100 2019.
[46] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. Diskann: Fast accurate billion- nearest neighbor search on a single node. Advances in Neural Information Processing Systems, 32, 2019.
[47] Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu. Rui Gan, and Shipeng Li. Scalable k-nn graph construction for visual descriptors. 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 1 1106-1113. IEEF, 2012.
[48] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. ANN-Benchmarks: A bench- marking tool for approximate nearest neighbor algorithms. Information Systems, 87:101374, 2020.
[49] Magdalen Dobson, Zheqi Shen, Guy E Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. Scaling graph- anns algorithms to billion-size datasets: A comparative analysis. arXiv preprint arXiv:2305.04359 2023.
13

---

A Related graph-based ANNS algorithms
As discussed above, graph-based ANNS algorithms conduct a best-first greedy beam search on the proximity graphs to approach the closest nodes for a query vector. Their built proximity graphs can be classified into four categories
[6 40 as follows.
Delaunay Graph (DG) [41 42]. ensures that for any edge, no other vectors will be situated within vectors, where the hypersphere is centered the midpoint the edge and the length of the edge is the diameter. But when the dimension d is large, DG tends become complete graph [42]. rapidly increasing the costs of greedy search.
the hypersphere defined by edge connecting
Relative Neighborhood Graph (RNG) 339 guarantees that for any edge between p and q, no other vectors will reside within the lune q) = (u E IR ((u, I 8(p,9) q) A a,u, q) S 8(p, 4))- Compared to DG, RNG imposes stricter restrictions on its edges. thus decreasing the average degree Various works are based on RNG, including the Monotonic Relative Neighbor Graph (MRNG)
43
6 and FANNG 42].
K-Nearest Neighbor Graph (KNNG) 44 In KNNG, neighbors of each vector U E 'D are its top-k nearest neighbors in D, avoiding too many explored neighbors during searching. Since each node in KNNG has only k neighbors, it cannot achieve the same level of connectivity as DG. NN-Descent proposes a method for constructing KNNG. For constructing KNNG, NN-Descent proposed, which starts from a random graph and iteratively refines the graph towards the KNNG.
4
was
Minimum Spanning Tree (MST) Graph 45 The MST utilizes distances between vectors as edge weights. Then, it performs hierarchical clustering on the dataset multiple times randomly, each time adding some edges the edge set. MST can establish global connectivity with minimal number of edges but may result in detours during searching.
Most well-known graph-based ANNS algorithms, including HNSW (2). Vamana 46 HCNNG 45 and NSG [6], do not exactly fit into one of the four categories. Instead, they usually evolve from one more of these proximity graphs. For example, Vamana evolved from the combination of two prior algorithms. HNSW originated from both the DG and RNG algorithms, while NSG originated solely from the RNG algorithm.
B Algorithms and illustrations
Algorithm 2 CSPG index construction
Require: dataset D = {V1, 82, ... ) number of partitions m, and sampling ratio À E [0, 1]
Ensure: CSPG index G = (G1, 92, ..., Gm J. routing vectors IVV
I: Pi < 0 for 1 < Σ RV <- $
2: RV random [n A samples from D
for each vector in D> RV do
4: add to random sampled partition P.
+ construct a proximity graph G. for each partition P:
6: return G and RV
Algorithm 3 CSPG vector insertion
Require: CSPG index G = (G1, G2, ..., ...,Gm),, routing vectors RV, and vector x
I: assign a random i, insert x to G. with the insertion method of the underlying graph index
2: if x: is selected as route vector then
3: insert into RV
for each j {1, 2, ..., m * do
5: insert x to G, with the insertion method of the underlying graph index
Algorithm 4 CSPG vector deletion
Require: CSPG index G = {G1, G2, Gm routing vectors RV, and vector
I: for for each {1, 2, ..., m) s.t. E G. do
2: remove x from G. with the insertion method of the underlying graph index
3: if is route vector then remove x from RV
14

---

Table 2: Candidate Set for the search in the query nearby (dashed parallelogram).
Step
PG's Candidate Set
CSPG's Candidate Set
0
[va}
(vd)
{ua}
[vî, v
2
{us, es.)
(ot, uf. vi}
{17, va)
(o), u9, od}
4
(reg U8, 05)
C Proofs for Section 5
Theorem
all as the expected length of search sequence in CSPG. Denote EC: as the expected sequence length when searching only on the graph G;. It holds that
2 Denote |CSPG [
E ECSPG
[|p al]
1 ~ a]]-
Proof. For the greedy search CSPG starting from Gi, denote E RV as the first routing vector that the search sequence visits. Thus, Pr(0 not exists) + L.e sE RV Pr(0 s) 1, where & not exists indicates that the sequence never visits a routing vector before reaching the query vector q. Then, we have
(p q not exists
RCSG Ip ~ dl = Pr(0 not exists)
[p m q
Σ .ERV
Pr(U s)ECSP
0
Ip ollo not exists +
Pr(0 not exists)E
Σ Pr(D = 8) p Up al] + n. CSPG [[s al)
SERV
Note that the of ECSPG [|s ~+ ql] can be further expanded similarly. Since any search sequence bounded by length n, such expansion can be done iteratively a finite number. Consider the last expansion of
m CSPG [16' ~ al] = Pr(U not exists)RR [1' ~ of not exists +
Pr(O 5") (B [|s i s']] ECPG [|>"~" all
~
a VERV
The search path s" ~y q lies in one of the graphs. According Theorem 1, since the path s has the same expected length in any graph, it holds that ECSPG []s" ~m all gc. I|s" me q[]. Thus,
15 CSPG [|s' ~ al] = Pr(O not exists) [[o i oll0 not exists
Σ Pr(O = 6") (E [1s' mn s - B&: [|s" ~ 21l
"EERV
[I' allo not exists +
Pr(O not exists)
Σ Pr(U = =') [s ~ 0/00 5"
"EERY
=F [|s' al]
By recursively apply such induction, we can prove that E CCPG [p qll E [|p ~ g]].
Theorem For datasets with the same distribution, as the number of vectors n decreases, p(u) monotonically non-dccreasing.
15

---

Proof. Given an AMSNET g build dataset D with vectors, for each vector E G, p(u) is the probability that u conquers random vector G. Consider the case that we randomly remove vector of from D. For the AMSNET G' built on dataset D), {g") ). denote pf (u) as the probability that conquers random vector g'. Next, we show that p' p'(u) 2 p(u).
In AMSNET G, since q" is randomly sampled from D, the probability that u > q" is p(u). Consider the following two cases.
> q² holds G. EnEgi I(u > q) 2 Eneg ll(u > q) - 1. is because G does not have q", and for building the AMSNET g' we can adjust the neighbors of u and u may conquer more vectors in g
If q" does not hold in 9, Eyeg I(u + 9) = =Eyeg I(us > q), since we can use the same neighbors of u for both 9 and G".
Therefore, have
p((u) p(u)
Eveg I(u 9) + (1 -[(p))
Enegr I(u x 4)
11 -
p(u) Eyeg I(u ②)
(1 p(u)) EEge T(u T(u 9)
n
Σ Egeg I(u > 9) - p(u)
np(u (u) p(u) p(u).
11
n
D Experiments settings and results
The detailed index construction parameters are listed follows, which are from previous studies 49 and Amn-bnnchmarks [48].
HNSW. The degree upper bound M = 32, and the efConstruction = 128.
Vamana. The degree upper bound R 32, beam size L = 128, and pruning parameter 1.2.
HCNNG. The number of cluster trees T 10, the leaf size of MST Ls 1000, and the MST degree = 5.
CSPG. For fairness, for each graph-based algorithm used in CSPG, we slightly adjust its parameters ensure the average degree of the built graphs is the same as the original algorithm.
The parameters ef for each baseline algorithm and the ef for CSPG method are uniformly picked from [10, 300] to obtain QPS at different Recall. For CSPG method, set parameter efi = 1 and sampling ratio À = 0.5 by default, while their impacts on performance are discussed in Section 6.4
Table 3: Statistics of Datasets
Dataset
Dimension
Data type
Base
Query
I
128
float 1,000,000
10,000
GISTIM
float
1,000,000
1.000
DEEPIM
96
float 1,000,000
10,000
SIFTIOM
128
uint8
10,000,000
10,000
16

---

HNSW
CSPG-HNSW
Vomana
CSPC-Uamana
HONNN
ESPG-HCNNG
Distunce computation
SIFTIM
GISTIM
DEEPIM
SIFTIOM
2.5
0.80
0.85
0.30
0.95
1.00
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
0.90
0.85
0.90
0.95
1.00
Recallg:00
Recalig10
Recall@110
Reca 1g:20
Figure 10: Number of distance computation v.s. recall curves for comparing query performance
165
CSPG-HNSW
165
CSPG Vamana
165
CSPG-HCNNG
2.5
CPS (SIFTIN
1.00
2.0
1.0
0.5
0.25
0.80
0.85
0.90
0.95
1.00
0.80
0.55
0.90
0.95
1.00
0.50
0.85
0.90
0.95
1.00
163
CSPG-HNSW
1e3
CSPG-Vamana
1e3
CSPG-HCNNG
6
QPS (CISTIM)
2-
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
1.00
0.80
0.55
0.90
0.95
1.00
CSPG-HNSW
165
CSPG-Vamana
CSPG-HCNNG
1.5
1.5
QPS (DEEP1M) M1
2.0
0.5
0.5
0.80
0.85
0.90
0.95
1.00
0.80
0.85
0.90
0.95
2.00
0.80
0.85
0.90
0.95
3.00
Recalig10
Recall@10
Recali@:10
Figure 11: Query performance when varying the number of partitions m
m6m1
#2
efym6
ef ml
e6-26
CSPW
165
CSPG-Varana
105
CSPG-HCNNG
1.25
2.5
GPS 15171300
2.0
2.0
0.75
0.5
0.5
0.50
0.25
0.80
1.00
0.95
1.00
1,63
CSPG-HNSW
1+3
CSPG-Vamana
1s3
CSPG-HCNNG
6-
0.80
0.85
0.90
0.95
1.00
0.60
0.25
0.90
0.95
1.00
0.50
0.85
0.90
0.95
1.00
1.65
CSPW
165
CSPG-Vamana
165
CCPGG
(PS
1.5
3.0
2.0
0.5
0.80
0.85
0.90
0.95
1.00
0.90
0.85
0.90
0.95
1.00
0.80
0.85
0.30
0.95
1.00
Recalig10
Recalig10
Recalig11
Figure 13: Query performance when varying the candidate set size e/i in the first stage
17

---

1=0.1
A=02
A-0.3
2-0.4
2-0.5
CSPG-NNSW
165
CSPG-Vamana
CSPG-HCNIG
DPS (SFFTM)
2.0
1.5
2.00
1.0
0.75
0.5
0.5
0.25
0.90
0.90
0.90
CSPG+HNSW
163
CSPG-Vamana
1:3
CSPG-HCNNG
9/5 (GISTMM)
4-
3-
24
0,90
0.95
1.00
0.80
2.00
0.90
0.95
1,00
C5PG-HN5W
165
CSPG-Vamana
1e5
CSPG-HCNNG
OPS 1PEEPPM
1.5
2.0
1.0
0.5
0.5
0.5
0,80
0.95
1.00
0.80
0.85
0.90
1.00
0.80
0,90
0.95
1.00
Recallig0
Recal@g10
Recalli10
Figure 12: Query performance when varying the sampling ratio X
Table 4: Hyperparameters selection sets
Baseline
Parameters Selection Sets
Vamana
RE [16, 32, 64), [L.0, 1.2, 144,, efCosstruction E (64, 128, 256
HNSW
M [16, 32, efConstructioon E [64, 128, 256}
NSG
RE [16, 32, 64), e/Construction E [64, 128, 256
HCNNG
8 (3, 5, 7), T
(5, 10, 15), Ls (750, 1000, 1250}
0.75
0.5
3.50
0.59
3.00
0.35
1.00
0.00
0.85
0.50
0.35
3,20
0.90
0.55
3.50
5.75
3.50
680
5.95
1.97
655
3.00
QPS 5387334
0.00
0.85
0.7
3.55
1.00
0.40
1.55
3.50
0.55
1.57
0.50
5.06
0.50
0.55
3.50
0.86
0,5
0.50
0.5
3.00
Reca 1g30
1+4
1.00
7.5
0.25
2.5
0.97
0.55
0.52
0.5
1.00
3.50
0.85
350
3.56
3.00
580
0.55
6,30
555
3.50
0.58
585
3.50
6,95
1.09
HCNNG
1955
HS2
10%L
200
2918 21.
KD00uu 201
(XL141299
STALOT 4
Ane ai 2i (01)
101 291-0
ATILJT Runn1)
An4 oil (o1))a
T1E 11/42/330000
Figure 14: QPS v.s. Recall @ 10 over different parameters combiinttonoii
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: As claimed the abstract and introduction, this article does present graph index schema CSPG that can be utilized to speed up graph-based ANNS algorithms.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In our theoretical analysis (Section 5), we assume that the vector distribu- tion of each partition in CSPG remains consistent. However, practically CSPG can still improve query performance by random partitioning, which ensures the similarity of vector distributions.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All the assumptions of our theoretical analysis are presented in Section and we provide all the proofs in Appendix C
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Appendix provides all the parameters, environment settings, and the imple- mentation details.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
20

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Our datasets are all commonly used datasets in previous ANNS studies. And all our experimental codes are available with detailed guidelines for reproducing.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
public//giide//Ddeatbbbmsss www.ssabmiiiiiiooooooooooooo. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips /nipss.c/puut
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We provide all the details including hyperparameters Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Error bars are not commonly used in our research field, and ensure that all experimental results are measured with multiple times and we remove outliers.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
21

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: All our experimental environments and hardware-relater technical descriptions are detailed in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:://///eaappppcccccplttt/tta
Question:
Answer: [Yes]
Justification: We have read the relevant guidelines of NeurlPS Code of Ethics carefully and strictly follow them.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification: Our research on ANNS can significantly enhance the efficiency and scalability various real-world applications, leading to improved user experiences and advancements in technology.
22

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our research is not related to any unsafe datasets or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The license and terms of use explicitly mentioned and respected. Creators and original owners of all assets used in the paper are properly credited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
23

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Our research is not related to this issue.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our study for Approximate Nearest Neighbor Search and the datasets involved are not related this issue.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our research is not related to this issue.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
24

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "bZEVZkVlXL", "reviewer": "Reviewer_PE2C", "summary": "The manuscript proposes a novel schema called \"Crossing Sparse Proximity Graphs\" (CSPG) which defines an proximity graph (PG) for the graph-based approximate nearest neighbor search (ANNS) problem. Searching on top of the CSPG is provably faster than existing proximity graphs (which derived from other ANNS algorithms, such as the relative neighborhood graph or the MST graph). The authors supported their work by extensive experimental results.", "questions": "It would be nice if the authors can compare their method with other ANNS algorithms. Is their method memory efficient? Is it more suitable for high-dim or low-dim vectors? Is their method better when the vectors are clustered or uniform?", "limitations": "The authors may optionally consider a complete benchmark with ann-benchmarks.com or use https://github.com/erikbern/ann-benchmarks.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The experiments are convincing. And the idea of a two-stage search process to create the CSPG is novel and may open new doors for more innovations.  \n\nI liked that the authors say (see Line 149), \"When the number of partitions m = 1, CSPG falls into the special case that builds a PG index over all vectors, which is consistent with most state-of-the-art graph-based ANNS algorithms.\" This makes their proposal a generalized counterpart of existing works.", "weaknesses": "The theoretical analysis is daunting (see Section 5.4). It is not clear why CSPG is always faster.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for reading our work and providing helpful suggestions. We have provided a Rebuttal PDF in the global Rebuttal, which contains all additional experimental setup and results.\n\n## For Weakness: Additional Explanation for Section 5.4\n\nCSPG is a framework designed to accelerate ANNS graph-based approaches. We randomly partition the dataset into multiple groups, where **the data distribution within each groups is similar (and similar to the original dataset)**, we then construct sparse proximity graph indexes on different subsets. We design a crossing-group retrieval algorithm (Algorithm 1) for this framework. The algorithm initially searches within a specific sparse proximity graph (First Stage) to get sufficiently close to the query. In the second stage, the algorithm uses routing vectors (redundancy) as bridges to traverse between multiple sparse proximity graphs. This traversal allows the query results to be derived from multiple sparse proximity graphs rather than a single large graph, resulting in greater diversity and robustness. Intuitively, as each sparse proximity graph is sparser and smaller with a shorter expected search length, we can achieve higher accuracy with fewer distance computations.\n\nSection 5 provides the theoretical explanation and analysis by introducing a novel concept, AMSNET, a more practiced and robust theoretical graph model based on MSNET [1]. While MSNET requires the graph search process to continually approximate the query, AMSNET allows the search process to take detours, provided that these detours are as small as possible. Mainstream graph methods generally satisfy this model under suitable parameters, since a good graph model cannot afford to have too many meaningless detours in its search process. The expected search path of MSNET [1] is $\\mathcal{O}(n^{\\frac{1}{d}} \\log n^{\\frac{1}{d}} / \\Delta r)$, and based on this, we derive that AMSNET's expected search length is $\\mathcal{O} \\left( \\frac{w}{\\Delta r} \\left(\\lambda n + \\frac{n (1 - \\lambda)}{m} \\right)^{\\frac{1}{d}} \\log \\left(\\lambda n + \\frac{n(1- \\lambda)}{m}\\right)^{\\frac{1}{d}} \\right)$, where $\\lambda < 1$ is the sampling ratio of CSPG, $m$ is the number of partitions, and $w$ reflects the probability of detours occurring in the search process, increasing as detours happen. It is proven in Theorem 3 that  $w$ does not decrease as $n$ increases.  \n\n**The bottleneck of the ANNS problem lies in the distance comparisons**, which corresponds to the node expansions in graph search. The Speedup of a query can be expressed as \n$$\nSpeedup = \\frac{\\text{PG's comparison}}{ \\text{CSPG's comparison}} = \\frac{\\text{PG's search length} \\times \\text{PG's degree}}{ \\text{CSPG's search length} \\times \\text{CSPG's degree}} = \\frac{\\text{PG's search length}}{ \\text{CSPG's search length}}.\n$$\nSince we fix the degree of a node in both PG and CSPG to be no more than $\\sigma$ (In ANNS, the degree of each node in the graph tends to be around the maximum degree of the graph.), the speedup ratio is equal to the ratio of the expected search length between CSPG and PG. When $n$ varies, this ratio is no less than 1 (even $n \\rightarrow \\infty$), demonstrating that CSPG can always work. Figure 9 in the submitted paper also indicates that CSPG requires fewer comparisons to achieve the same accuracy.\n\n## For Questions: Comparison with other approaches\n\n**Memory efficiency.** According to [4], graph-based indices are indeed the best among various index types for query performance, yet the memory of a graph is correspondingly more expensive. Though CSPG has a larger index size, it is still affordable since the memory consumption of the vector data is much larger than the indices, which is also the reason why Vamana [3] put the index in memory. \n\n**Dimension.** Whether dealing with high-dimensional or low-dimensional vectors, graph algorithms generally provide better support compared to other methods (such as Quantization-based), as shown in the ANN-Benchmark [2]. This is precisely why graph-based approaches stand out among various ANNS methods. Since CSPG optimizes mainstream graph algorithms, it also performs well in both high-dimensional and low-dimensional scenarios. For example, as detailed in Section 6, our method supports datasets like SIFT1M with 128-dimension vectors and GIST1m with 960-dimension vectors effectively.\n\n**Clustered/Uniform dataset.** To analyze the performance of CSPG on clustered and uniform data, we conduct comparative experiments on SIFT1M, GIST1M, DEEP1M, Text2Image, and MSTuring, a generated clustered dataset (GCD) and a generated uniform dataset (GUD). The Hopkins statistic for these datasets is shown in Table 1, which tends toward 0 when the data is uniform and toward 1 when the data is clustered). The performance over different distributions is shown in Figure 3 (Rebuttal PDF), where CSPG performs well in optimizing both uniform and clustered data.\n\n## For Limitations: ANN-Benchmark\n\nWe are conducting experiments using ANN-Benchmark [2] to compare CSPG with other ANNS methods on various datasets. To ensure the fairness, we run all the programs on the same machine (please refer to Appendix D), but it requires a long time to finish all of them. We will include all the results after finishing these experiments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l5vF0G9UUj", "reviewer": "Reviewer_4Bip", "summary": "This paper studies the problem of approximate nearest neighbor search (ANNS), and proposes an optimized solution for existing proximity graph-based solution. The main idea of this solution is to decompose the original dataset into several partitions, build a proximity graph for each partition, and consider crossing proximity graphs during the searching procedure. Finally, experiments are conducted on three public datasets.", "questions": "Q1. The idea of random partitioning is quite simple, and the technical novelty is quite limited.\n\nQ2. Since the idea is simple, I wish the authors could consider more on practical issues, such as dynamic updates (eg insertions and deletions) that are widely considered in recent studies. However, they are ignored in the algorithm design. Moreover, due to the usage of random partitions, the proposed solution can be less flexible to handle dynamic updates. \n\nQ3. More recent solutions from the related studies in the references, which have been demonstrated to be more efficient than the chosen ones (eg the standard HNSW), should be compared.\n\nQ4. In the experimental setup, it is unclear whether the index and dataset are stored in main memory, SSD, or disk. By contrast, the selected baseline work (eg [45]) has considered more than one kind of data storage.\n\nQ5. In the experimental study, the impact of k should be also tested.\n\nQ6. Based on the results in Table 1, it seems that the proposed solutions trade construction time and index size of better query efficiency. However, the rationale of the trade-off is not well discussed.\n\nQ7. Since the experimental results have shown that the improvement is 1.5x to 2x, which is marginal, the theoretical result of speedup analysis is not meaningful enough.\n\nQ8. Since several efficient solutions to ANNS have been proposed in recent years, they should be more carefully discussed in terms of the pros and cons. Besides, the following studies are also related:   \n[1] RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. ACM SIGMOD 2024     \n[2] Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces. VLDB 2023", "limitations": "Please refer to the weaknesses and questions.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "S1. The paper studies an important problem.   \nS2. The proposed solution has theoretical analysis.   \nS3. Experiments are conducted on public datasets.", "weaknesses": "W1. The novelty is limited.   \nW2. The experimental evaluation is inadequate.   \nW3. Important issues are not well considered in the algorithm design.   \nW4. Recent studies are not carefully reviewed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reading our work and providing detailed suggestions. We have provided a Rebuttal PDF in the global Rebuttal, which contains all additional experimental setup and results.\n\n## For Q1 and W1: Novelty and Contributions\n\nMost existing methods that adopt the idea of partitioning data often employ the clustering-based partitioning (e.g. kmeans). For example, DiskANN and IVF-based approaches use kmeans, which disrupts the original distribution of the given dataset and puts similar vectors into the same buckets. In this paper, we propose a totally different paradigm, i.e., making all sparse proximity graph (SPG)'s distribution as similar as possible, which allows us to divide and conquer the entire dataset. It also ensures that the load is distributed across different groups. To achieve this, we employ simple and efficient random partitioning. This strategy is simple yet effective as proved through both theoretical and empirical analysis. We believe the technical novelty is sufficient, mainly lying in that:\n\n- We are the first to present a novel framework named CSPG, that utilizes random partitioning for ensuring a consistent distribution of graph indices, producing a smaller SPG for each partition. Moreover, this framework allows mainstream graph indices to be embedded within our framework.\n- We develop an efficient two-staged approach for exploring CSPG, with fast approaching and cross-partition expansion. The approach can reduce many unnecessary explorations.\n- We theoretically prove that with the consistent distribution produced by the random partitioning, CSPG can accelerate the existing graph-based ANNS algorithms by reducing unnecessary explorations.\n\n## For Q4: In-memory Evaluations\n\nWe appreciate you pointing out the differences between the two versions of DiskANN. Regarding this concern, we mentioned in Section 6.1 that all evaluations were conducted in memory. \n\n## For Q2 and W3: Dynamic Updates\n\nHanding updates (insert and delete) is an interesting topic. Our framework can be easily extended to deal with updates.\n\n- CSPG is a framework based on mainstream proximity graphs (PGs), and current updating methods of underlying graphs are applicable to our framework.\n- The random partitioning makes our framework highly flexible for updates. For instance, when inserting a vector, it is randomly assigned to a SPG $\\mathcal{G}_i$, while the first stage of Algorithm 1 is only conducted on another SPG $\\mathcal{G}_j$. By ensuring $i \\neq j$, our framework enables concurrent querying and updating.\n- Due to our use of random partitioning, CSPG ensures that each partition fairly shares the load of updates, which is a capability that other partitioning methods cannot achieve.\n\n## For Q8 and W4: Mentioned Recent Studies\n\nThanks for suggesting two recent works. Among them, RaBitQ [5] is a quantization method with a sharp theoretical error bound while providing good accuracy. LSH-APG [6] also utilizes quantization and designs an efficient graph index, achieving a well-balanced performance between construction and query efficiency. We will include a discussion of the two works in the revised paper. \n\n## For Q5, Q6 and W2: Additional Experiments\n\nBased on our experiments and those of LSH-APG, HNSW, NSG, HCNNG, and DiskANN stand out as the most representative graph indexing algorithms. CSPG outperforms these representative methods across all recall ranges.\n\n**For Q5.** According to the experimental setup of LSH-APG, we compare the average search time of LSH-APG, CSPG-HNSW, CSPG-NSG, CSPG-Vamana and CSPG-HCNNG on the Audio dataset used in LSH-APG. We fix the recall above 0.99 and vary the value of k which is shown in Figure 1 (Rebuttal PDF). Our framework's construction time ranges from 3.8 to 9.6 seconds, whereas LSH-APG requires about 1.6 seconds to build.\n\n**For Q6.** According to [2,4], graph-based indices are indeed the best among various indexes for querying, yet the construction cost of a graph is higher. LSH-APG and [6] do achieve a good balance between query and build. With the development of technologies (e.g., RAG), there are increasing demands for latency, and our framework specifically addresses these needs. Additionally, the time and space costs for construction with CSPG are controllable. By tuning the sampling ratio $\\lambda$ and the number of partitions $m$, we can effectively manage the trade-off between query performance and construction costs. \n\n**For W2.** We also add some harder datasets for evaluations such as Text2image, MSTuring and SIFT100M, which can be found in NeurIPS'21 [7]. The results are shown in Figure 2 (Rebuttal PDF) and Figure 6 (Rebuttal PDF).\n\n## For Q3: Representative Baselines\n\nWhile there are some approaches that outperform our baselines on certain dataset, their performance varies across different datasets. For example, NGT-panng performs better than Vamana on the MNIST-784, but worse than Vamana on the glove-100-angular. Since we propose a framework for mainstream PGs and aim for a more general comparison, we selected HNSW, NSG, Vamana and HCNNG as our baselines, all of which rank highly in ANN-Benchmark [2]. Previous studies [1,4,6] also chose these indices, further demonstrate that our baselines are among the most representative ones.\n\n## For Q7: Speedup Analysis\n\nOur method is not a specific index but a framework that is applicable and beneficial to mainstream PGs. The speedup analysis in Section 5 proves that our framework can consistently provide optimization, lending strong support to our approach. Since the experiments may be influenced by various factors like dataset, graph and parameters, such theoretical analysis is necessary and general enough to explain why CSPG requires less computation.\n\nOn the other hand, Subramanya et al. [3] demonstrate that Vamana slightly surpasses HNSW in terms of QPS. Our framework outperforms mainstream PGs by 1.5-2x, making our improvement significantly substantial(not marginal) in the field of ANNS.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mUQv8aj1N3", "reviewer": "Reviewer_niwV", "summary": "The article considers the task of graph-based approximate nearest neighbor (ANN) search. It provides a general method for building several sparse overlapping proximity graphs, and a method for searching them. The proposed algorithm can be used in combination with any kind of existing proximity graph. The experimental results demonstrate that the proposed method improves performance of the state-of-the-art graph methods (HNSW, HCNNG, Vamana).", "questions": "The improvement provided by your method is smallest for HNSW. Do you think that this is because also HNSW uses overlapping graphs with randomly selected overlap nodes (in HNSW the overlapping graphs are hierarchical and searched in a fixed order, whereas in your method flat, and searched in a different fashion), and thus there is more redundancy? It would be interesting to see an analysis of similarities and differences between your method and HNSW.", "limitations": "I see no inherent limitations, expect the issues with the empirical verification that I addressed above.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method is novel and the explanation why it work is intuitive. It is also widely applicable, since it can be used in combination with any kind of proximity graph. The ablation experiments are comprehensive.", "weaknesses": "The only issue I find is the experimental verification. While the methodology is otherwise sound, I would like to see a complete hyperparameter sweep for all the baselines, as in ANN-benchmarks project that is used to select the data sets. Since DiskANN and HNSW have hyperparameter grids in ANN-benchmarks, I see no excuse of not running the experiments using these grids (as the data sets used in the experiments are small benchmark data sets with sample sizes of 1M, this should be computationally feasible), and reporting the results with the optimal hyperparameters. This would (1) verify that the performance improvement holds at the optimal hyperparameters, i.e., that the proposed algorithm really improves state-of-the-art; (2) would rule out the possibility that the observed performance improvement of the proposed method over the baseline is due to the additional hyperparameter exploration enabled by its additional hyperparameters. Also the experimental code should be provided for reproducibility (at least I did not find the code or link to it anywhere?).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for carefully reviewing our work and for your insightful suggestions and interesting topics. We have provided a Rebuttal PDF in the global Rebuttal, which contains all additional experimental setup and results. Regarding of reproducibility, We have provided our source code for all experiments and algorithms to PC/AC/SAC.\n\n## For W1: Hyperparameters grid\n\nRegarding the hyperparameter sweep on baseline parameters that you mentioned, we searched for datasets like SIFT1M, GIST1M and DEEP1M, focusing on baselines such as Vamana, HNSW, NSG and HCNNG. The parameter selection sets for different indices are show in Table 2 (Rebuttal PDF). We obtained a parameters grid (combination) and evaluated the QPS-Recall@10 benchmark as shown in Figure 4 (Rebuttal PDF). Next, we choose the parameters with the highest QPS when the Recall@10 is equal to $0.9 \\pm 5e^{-3}$ as shown in the Table 3 (Rebuttal PDF). Finally, we run the comparison (QPS-Recall@10) between graph-based methods (baseline) and CSPG (our solution) with the optimal hyperparameters we just got. The results are shown in Figure 5 (Rebuttal PDF).\n\n## For Q1: The Relation between HNSW and CSPG\n\nOur framework shares similarities with HNSW in utilizing redundancy to connect different graphs. However, there are some differences.\n\n- **From the perspective of redundancy.** CSPG-HNSW does generate more redundancy. On the one hand, there are redundant vectors between different levels within each sparse proximity HNSW graph built on a partition. On the other hand, there are also redundant vectors between different sparse proximity HNSW graphs. However, the redundancy in HNSW is used to connect the smaller upper-level graphs with the larger lower-level graphs within a single partition, whereas the redundancy between sparse proximity HNSW graphs is used to connect two completely different HNSWs (one vertically, the other horizontally). The roles of these redundancies are not the same. Moreover, this cost is converted into further optimization of HNSW, with not only the hierarchical structure enhancing the searching of each HNSW, but also the faster and more precise searches brought about by traversing across sparser proximity graphs.\n- **From the perspective of structure.** While HNSW is a hierarchical graph indexing structure, CSPG serves as a graph framework rather than a specific index. CSPG is not confined to a particular structure (hierarchical or flat), allowing it to enhance query performance across a broad range of mainstream graph indices. HNSW constructs a structure that transitions from sparse to dense unidirectionally. In contrast, CSPG is a framework horizontally builds smaller, sparser proximity graphs. \n- **From the perspective of searching.** HNSW explores each level from top to bottom, and the final results are obtained from the lowest-level graph. CSPG, after approximating the query on one sparse proximity graph (First Stage), traverses back and forth between different sparse proximity graphs (Second Stage), which collects final results in each sparse proximity graph. We might traverse graph $\\mathcal{G}_1$ for a while, then *jump* to another graph $\\mathcal{G}_2$. After some time, we may return to  $\\mathcal{G}_1$ again. However, in HNSW, there is no *jump* from a lower level to an upper one, since the upper levels are merely subsets of the bottom level. This difference enhances CSPG's searching accuracy: since HNSW's candidate results only come from the large bottom-level graph, the accuracy of the results is closely tied to the quality of the bottom-level graph. CSPG, however, traverses between different sparse proximity graphs and collects candidates from them, making the answers more diverse and robust. Additionally, Algorithm 1 has been proven to have an expected search length that is equivalent to that of a single sparse proximity graph (Theorem 2), while the expected search length for smaller sparse proximity graphs (sub-datasets) is shorter than that of a complete large graph, which means that CSPG performs higher accuracy with fewer calculations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f7OgnOoG6V", "reviewer": "Reviewer_U15c", "summary": "This paper proposes CSPG as a novel graph index for vector similarity search. CSPG divides the dataset into sub-datasets with some common routing vectors. It builds a separate graph for each sub-dataset; during search, graph traversal is first conducted on one sub-dataset to quickly approach the neighborhood of the query and then switched to routing vectors for all sub-datasets to explore all vectors. Experiment shows that CSPG improves the QPS when achieving the same query recall for three existing graph indices.", "questions": "I will raise the overall rating if the relation between this work and the hierarchical graph of HNSW is clarified.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "S1: Vector similarity search is an important problem, and graph index provides STOA performance. Thus, improving graph index is hot topic.\n\nS2: Theorical analysis is conducted for CSPG.\n\nS3: The experiment results are promising, i.e., CSPG seems a general technique that can accelerate different graph indices.", "weaknesses": "W1: The relation to HNSW needs to be clarified. In particular, HNSW shares similar idea with CSPG, i.e., the upper-level graphs contain vectors sample from the dataset and used to quickly approach the neighborhood of the query; moreover, the upper-level graphs are searched with ef=1 while the bottom level graph is searched with much larger ef (corresponding to the two-stage search in the paper). In principle, HNSW can also change the graph index used for each layer once the vectors for each layer are determined. Thus, the question becomes the difference between a hierarchical graph (as in HNSW) and some parallel graphs with overlaps. Can HNSW match the performance of CSPG by tuning its parameters? \n\nW2: Experiment should be enhanced. (1) Larger datasets should be used. Even if billion-scale datasets do not fit in common machines, datasets with 100M scale should be used. (2) Include NSG, as it is also widely used and shown to achieve good performance of the experimented datasets. (3) Try harder datasets. It is reported that the SIFT and Deep datasets are relatively easy [16] while Text-to-Image and Turing ANNS are more difficult. These datasets can be found at the NeurIPS’21 vector search challenge. \n\nW3: Requiring a larger overlap (i.e., \\lamada=0.5) between the sub-datasets and can only use a small number of sub-datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank you for carefully reviewing our work and for providing such insightful suggestions. We have provided a Rebuttal PDF in the global Rebuttal, which contains all additional experimental setup and results.\n\n## For Q1: The Relation between HNSW and CSPG\n\nOur framework shares similarities with HNSW in utilizing redundancy to connect different graphs and similarities for varying candidate sizes (In HNSW, $ef_1$ is always set to 1, while in CSPG, $ef_1$ can be tuned to a value larger than 1). More importantly, they differ in the following three aspects:\n\n- **From the perspective of redundancy.** For the standard HNSW index, there are redundant vectors between different levels to connect the adjacent levels. But in CSPG framework, redundant vectors are shared by independent sparse proximity graphs built for different partitions. When using CSPG with underlying HNSW index, there are redundant vectors between different levels in an HNSW, as well as redundant vectors between different HNSWs. The redundancy in an HNSW is used to connect the smaller upper-level graphs with the larger lower-level graphs within the partition, whereas the redundancy between HNSWs is used to connect completely different HNSWs (one vertically, the other horizontally). The roles of these redundancies are not the same.\n\n- **From the perspective of structure.** While HNSW is a hierarchical graph structure, CSPG serves as a graph framework rather than a specific index structure. CSPG is not confined to a particular structure (hierarchical or flat), allowing it to enhance query performance across a broad range of mainstream graph indices. HNSW constructs a structure that transitions from sparse to dense unidirectionally. In contrast, CSPG builds a framework horizontally with smaller, sparser proximity graphs.\n- **From the perspective of searching.** HNSW searches each level from top to bottom, and the final results are obtained from the lowest-level graph. CSPG, after approximating the query on one sparse proximity graph (First Stage), traverses back and forth between different sparse proximity graphs (Second Stage), which collect final results in each sparse proximity graph. We might traverse graph $\\mathcal{G}_1$ for a while, then *jump* to another graph $\\mathcal{G}_2$. After some time, we may return to  $\\mathcal{G}_1$ again. However, in HNSW, there is no *jump* from a lower level to an upper one, since the upper levels are merely subsets of the bottom level. This difference enhances CSPG's searching accuracy: since HNSW's candidate results only come from the large bottom-level graph, the accuracy of the results is closely tied to the quality of the bottom-level graph. CSPG, however, traverses between different sparse proximity graphs and collects candidates from them, making the answers more diverse and robust. Additionally, Algorithm 1 has been proven to have an expected search length that is equivalent to that of a single sparse proximity graph (Theorem 2), while the expected search length for a smaller sparse proximity graph (sub-datasets) is shorter than that of a complete large graph, which means that CSPG performs higher accuracy with fewer calculations.\n\n## For W2: Additional Experiments\n\nFollowing your suggestions, we have added the experiments as shown in Figure 2 (Rebuttal PDF) and Figure 6 (Rebuttal PDF). \n\n**Larger dataset.** We compared the query performance (k=10) of HNSW and CSPG-HNSW on the SIFT100M dataset. We kept the hyperparameters consistent with those in Appendix D. The final results show that CSPG maintains its advantage even at the 100M scale.\n\n**Inclusion of NSG and harder dataset.** We included the NSG and added comparisons for the Text2image (1M base vectors, 200 dimensions) and MSTuring (1M base vectors, 100 dimensions). The parameter settings were kept consistent with those described in Appendix D. The comparison results demonstrate that we still maintain an advantage even in more complex datasets.\n\n## For W1: Can HNSW be better than CSPG by parameters-turning?\n\nIn principle, CSPG partitions the dataset to make each proximity graph sparser and smaller to traverse with shorter expected search length, which has been proven in Section 5. As a result, **CSPG-HNSW should always be better than HNSW**. To convince that, we conduct experiments on SIFT1M, GIST1M, and DEEP1M, focusing on baselines such as Vamana, HNSW, NSG, and HCNNG. The parameter selection sets for different indices as shown in Table 2 (Rebuttal PDF). We obtained the optimal parameters for HNSW from all combination as shown in Figure 4 (Rebuttal PDF). We then chose the parameters with the highest QPS when the Recall@10 equals $0.9 \\pm 5e^{-3}$ as shown in Table 3 (Rebuttal PDF), and ran the comparison (QPS-Recall@10) between graph-based methods (baseline) and CSPG (our solution) with the optimal parameters we got. The results are shown in the Figure 5 (Rebuttal PDF). CSPG-HNSW outperforms HNSW even with the best parameters of HNSW. \n\n## For W3: Partition number $m$\n\nWe require a similar distribution between different partitions, and we achieve this by vector redundancy. However, increasing the number of partitions does not necessarily lead to better query performance (please refer to Figure 5 in the submitted paper). The reason is that large $m$ may decrease the similarity of distribution among different partitions, which contradicts the assumptions discussed in Section 5.4.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely appreciate all four reviewers for their instructive suggestions on our submitted paper. Their suggestions have been immensely helpful in improving our work and enhancing our experiments. To response the relevant points of concern, we have conducted additional experiments and included the results in the Rebuttal PDF. We will carefully reflect on and correct the shortages of our methodology to enhance the readability and comprehensibility in the final version. Detailed responses to each reviewer's comments are provided below. Due to space constraints, we have list all references here.



## References

[1] Fu C, Xiang C, Wang C, et al. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph[J]. Proceedings of the VLDB Endowment, 12(5).

[2] Aumüller M, Bernhardsson E, Faithfull A. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms[J]. Information Systems, 2020, 87: 101374.

[3] Jayaram Subramanya S, Devvrit F, Simhadri H V, et al. Diskann: Fast accurate billion-point nearest neighbor search on a single node[J]. Advances in Neural Information Processing Systems, 2019, 32.

[4] Wang M, Xu X, Yue Q, et al. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search[J]. Proceedings of the VLDB Endowment, 2021, 14(11): 1964-1978.

[5] RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. ACM SIGMOD 2024

[6] Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces. VLDB 2023

[7] https://github.com/harsha-simhadri/big-ann-benchmarks

Meta-review: The reviewers remark that the problem studied is important [U15c, 4Bip], the experiments are convincing [PE2C], empirical results are promising [U15c] & accompanied by theoretical results [U15c], the contribution has novel ideas [PE2C, niwV] and explanations are intuitive [niwV], but the theoretical results could be easier to follow [PE2C], there could be more/broader comparisons with other Approximate Nearest Neighbour Search (ANNS) algorithms/indices such as Hierarchical Navigable Small World graphs (HNSW) [PE2C, 4Bip, U15c], a complete hyperparameter sweep/grid as in prior work [niwV] and more explicitly consider dynamic updates [4Bip].

In the rebuttal the authors provide source code for all experiments, argue that dynamic updates are orthogonal to the proposed framework [response to 4Bip] & will discuss it in more detail in the final version, clarify/amend hyperparameter grid & other additional experiments [response to U15c], further discuss the relationship to HNSW [responses to niwV, U15c] and provide details on the utilised number of partitions [response to U15c].

The overall recommendation is to accept this submission with the agreed upon changes during the discussion phase. The work studies a relevant problem [U15c, 4Bip], achieves empirical improvements [PE2C, U15c] that are confirmed theoretically [U15c] while providing a versatile framework and explaining ideas/results clearly.
Decision: Accept (poster)