Efficient High-Dimensional ANN Search
Uploaded by
zhn20050407Efficient High-Dimensional ANN Search
Uploaded by
zhn20050407Subspace Collision: An Efficient and Accurate Framework for
High-dimensional Approximate Nearest Neighbor Search
Jiuqi Wei Xiaodong Lee Zhenyu Liao
Institute of Computing Technology, Institute of Computing Technology, Huazhong University of Science and
Chinese Academy of Sciences Chinese Academy of Sciences Technology
University of Chinese Academy of Fuxi Institution China
Sciences China zhenyu_liao@[Link]
China xl@[Link]
weijiuqi19z@[Link]
arXiv:2411.14754v2 [[Link]] 13 Jan 2025
Themis Palpanas Botao Peng
LIPADE, Université Paris Cité Institute of Computing Technology,
France Chinese Academy of Sciences
themis@[Link] China
pengbotao@[Link]
ABSTRACT ACM Reference Format:
Approximate Nearest Neighbor (ANN) search in high-dimensional Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng.
2025. Subspace Collision: An Efficient and Accurate Framework for High-
Euclidean spaces is a fundamental problem with a wide range of
dimensional Approximate Nearest Neighbor Search. In Proceedings of ACM
applications. However, there is currently no ANN method that per- Conference on Management of Data (SIGMOD ’25). ACM, New York, NY,
forms well in both indexing and query answering performance, USA, 17 pages. [Link]
while providing rigorous theoretical guarantees for the quality of
the answers. In this paper, we first design SC-score, a metric that we
show follows the Pareto principle and can act as a proxy for the Eu-
clidean distance between data points. Inspired by this, we propose a
1 INTRODUCTION
novel ANN search framework called Subspace Collision (SC), which
can provide theoretical guarantees on the quality of its results. We Background and Problem. Nearest neighbor (NN) search in
further propose SuCo, which achieves efficient and accurate ANN high-dimensional Euclidean spaces is a fundamental problem with
search by designing a clustering-based lightweight index and query various applications [30, 72, 75, 76] ranging from information re-
strategies for our proposed subspace collision framework. Exten- trieval [49], data mining [88], to recommender system [85]. Given a
sive experiments on real-world datasets demonstrate that both the dataset D of 𝑛 data points in 𝑑-dimensional space, a query 𝑞 ∈ R𝑑 ,
indexing and query answering performance of SuCo outperform and 𝑘 ∈ N, NN search will return the 𝑘 nearest neighbors of 𝑞 from
state-of-the-art ANN methods that can provide theoretical guaran- D. However, NN search in high-dimensional datasets is challenging
tees, performing 1-2 orders of magnitude faster query answering due to the curse of dimensionality phenomenon [18, 25, 42, 56, 62,
with only up to one-tenth of the index memory footprint. Moreover, 101]. To achieve a better trade-off between query efficiency and
SuCo achieves top performance (best for hard datasets) even when accuracy, many researchers turn to Approximate Nearest Neighbor
compared to methods that do not provide theoretical guarantees. (ANN) search, sacrificing some query accuracy to achieve huge
gains in efficiency [54, 90, 97]. ANN search will retrieve a set C of
| |
CCS CONCEPTS 𝑘 high-quality candidates to maximize 𝑟𝑒𝑐𝑎𝑙𝑙 = C∩G 𝑘 , where G
• Information systems → Nearest-neighbor search; Query consists of the exact 𝑘 nearest neighbors of 𝑞 in D. Depending on
optimization. where the index and dataset are stored, we can divide ANN methods
into three categories: in-memory methods [14, 38, 67, 104], disk
KEYWORDS methods [53, 60], and memory-disk hybrid methods [24, 44]. In this
paper, we focus on in-memory methods due to their great success
Subspace collision, ANN search, High-Dimensional spaces for fast high-recall search.
Limitations and Motivation. Nowadays, new data is gener-
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed ated at an ever-increasing rate, and the size of datasets is also
for profit or commercial advantage and that copies bear this notice and the full citation growing [55, 75, 76, 103]. We need to manage large-scale data
on the first page. Copyrights for components of this work owned by others than the
author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
more efficiently to support further data analysis [31, 37, 97, 98].
republish, to post on servers or to redistribute to lists, requires prior specific permission Many ANN search methods have been proposed, such as Locality-
and/or a fee. Request permissions from permissions@[Link]. Sensitive Hashing (LSH)-based [4, 52, 91, 104, 111, 112], Vector
SIGMOD ’25, June 22–27, 2025, Berlin, Germany
Quantization (VQ)-based [9, 11, 38, 48, 74, 105], tree-based [14,
© 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ACM ISBN 978-1-4503-XXXX-X/18/06
[Link] ∗ Xiaodong Lee and Botao Peng are the corresponding authors.
SIGMOD ’25, June 22–27, 2025, Berlin, Germany Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng
22, 50, 57, 70, 79, 80, 83, 93, 94, 99, 100, 106, 107, 113], and graph- SuCo achieves top performance (best for hard datasets) even when
based [6, 33, 34, 67, 71, 110]. However, each method has its own compared to methods that do not provide theoretical guarantees.
advantages and disadvantages. LSH-based methods are well-known Our main contributions are summarized as follows.
for their robust theoretical guarantees on the quality of results, but
• We design SC-score, a metric that we show follows the Pareto
they have to pay a high cost in terms of query answering time and
principle on commonly used real-world datasets, demon-
have a large memory footprint [104]. VQ-based methods use the
strating that SC-score can act as a proxy for the Euclidean
clustering structure as the index, so the index memory footprint is
distance between data points.
small, but a lot of indexing time is required to compute fine-grained
• We present Subspace Collision (SC), a novel ANN search
clusters [9]. Tree-based methods can partition data points into dif-
framework based on SC-score. Our experiments show that
ferent regions by splitting nodes, but as the space dimensionality
the subspace collision framework can achieve high recall for
increases, the effectiveness of trees decreases [17, 101], and query
ANN search. We perform rigorous mathematical analysis
performance is thus limited. Graph-based methods typically have
showing that the subspace collision framework can provide
better query efficiency, but take considerably more time to construct
theoretical guarantees on the quality of its results.
indexes and require a larger memory footprint [31, 54]. The reason
• We propose SuCo (code available online [102]), which achieves
is that graph-based methods need to identify the near neighbors
efficient and accurate ANN search based on our subspace col-
for each data point in the dataset (and connect to them) during the
lision framework. We design a clustering-based lightweight
indexing phase, while in the query phase, they only need to search
index to ensure excellent indexing performance, and design
on a gradually converging path. Thus, no existing ANN method
query strategies to ensure excellent query performance.
performs well in both indexing and query answering performance,
• We conduct extensive experiments, demonstrating that both
while providing rigorous theoretical guarantees for the quality of
the indexing and query answering performance of SuCo out-
the answers.
performs state-of-the-art ANN methods that can provide
Our Method. In this paper, we propose a novel ANN search
theoretical guarantees, performing 1-2 orders of magnitude
framework called Subspace Collision (SC) and design an index struc-
faster query answering with only up to one-tenth of the
ture and query strategy for this framework, forming an efficient and
index memory footprint. Moreover, SuCo achieves top per-
accurate method named SuCo [102]. Compared to other ANN meth-
formance (best for hard datasets) even when compared to
ods, SuCo performs well in both indexing performance (in terms
methods that do not provide theoretical guarantees.
of time and memory footprint) and query performance and has
rigorous theoretical guarantees. Moreover, we first design SC-score,
a metric that we show follows the Pareto principle (also known 2 RELATED WORK
as the 80/20 rule) on many commonly used real-world datasets LSH-based methods. Locality-sensitive hashing (LSH)-based meth-
(Figure 2), demonstrating that data points closer to the query point ods are known for their theoretical guarantees on the quality of re-
tend to have larger SC-scores. As such, SC-score can act as a proxy turned query results [3, 4, 36, 43, 52, 59, 63, 65, 87, 91, 104, 111, 112].
for the Euclidean distance between data points. Second, inspired A family of LSH functions is used to map data points from the orig-
by SC-score, we present a novel ANN search framework called inal high-dimensional space to low-dimensional projected spaces.
“Subspace Collision (SC)” (cf. Section 3) that is different from the The properties of LSH can ensure that data points that are closer
existing LSH-based, VQ-based, tree-based, and graph-based frame- in the original space are also closer in the projected space [39].
works. We design a naive method (without index structure) called For this reason, all that is needed to obtain high-quality results
SC-Linear, which achieves extremely high recall (over 0.99) on real- is to examine the points around the query point in the projected
world datasets (cf. Table 2), illustrating the effectiveness of the spaces [27]. LSH-based methods improve query efficiency by de-
subspace collision framework for ANN search. Third, we propose signing the index structure and query strategy in the projected
SuCo (cf. Section 4), which achieves efficient and accurate ANN spaces. Based on the query strategy, there are three categories
search by designing an index structure and query strategies for the of LSH-based methods: boundary constraint [3, 61, 89, 91], colli-
subspace collision framework. SuCo constructs lightweight indexes sion counting [36, 43, 52, 63, 65], and distance metric [87, 111].
by clustering data points in each subspace and using the inverted DET-LSH [104] is the state-of-the-art LSH-based method, which
multi-index (IMI) to reduce the clustering complexity. We further combines the ideas of boundary constraint and distance metric.
design a new query algorithm for IMI, called Dynamic Activation VQ-based methods. Vector quantization is a lossy data com-
(cf. Algorithm 3), which improves the query efficiency by up to 40% pression technique that encodes vectors from a high-dimensional
over the original query algorithm. Fourth, we perform a rigorous space into a finite set of values from low-dimensional discrete sub-
mathematical analysis, showing that the proposed subspace colli- spaces [40, 41]. Vector Quantization (VQ)-based methods aim to
sion framework can provide theoretical guarantees on the quality minimize the quantization distortion, which is the sum difference be-
of its results (cf. Theorems 1 and 2). Fifth, we conduct extensive tween each data point and its approximation [54]. Based on the way
experiments on real-world datasets. Numerical results show that of combining quantizers among multiple subspaces, there are four
SuCo outperforms state-of-the-art ANN methods that can provide categories of VQ-based methods: product quantization (PQ) [45],
theoretical guarantees in indexing and query answering perfor- additive quantization (AQ) [8], composite quantization (CQ) [109],
mance, performing 1-2 orders of magnitude faster query answering and tree quantization (TQ) [10]. PQ is the most popular VQ-based
with only up to one-tenth of the index memory footprint. Moreover, methods, which divide the original high-dimensional space into a
Cartesian product of many low-dimensional subspaces and then
Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search SIGMOD ’25, June 22–27, 2025, Berlin, Germany
x-axis as subspace y-axis as subspace
Rank Point SC-score
��� �� �� Rank Point Dist Rank Point Dist
1 �� 2
�� 1 �� 0 1 �� 0
�� 2 �� 2
2 �� 1 2 �� 1
q ��
3 �� 3 �� 3 �� 2
�� 1 2
4 �� 2 4 �� 2 4 �� 1
�� �� �� 5 �� 1
5 �� 2 5 �� 3
...
...
...
...
...
...
...
...
...
(a) Data points distribution, where the (b) Nearest neighbors when choosing 𝑥 or 𝑦 dimension (c) Nearest neighbors when intro-
Euclidean distance from 𝑂 1 to 𝑂 10 to as the subspace for measuring similarity. ducing the idea of collision based on
the query point 𝑞 gradually increases. 𝑥 and 𝑦 subspaces, where the colli-
sion ratio 𝛼 = 0.5.
Figure 1: Illustration of finding nearest neighbors using the idea of subspace and collision.
quantizes subvectors in each subspace separately [68]. Many exten- is still one of the state-of-the-art graph-based method [92], which
sions have been proposed to improve the performance of PQ for in- has an industrial-grade library and is therefore widely used.
dex construction and query answering [9, 11, 38, 46, 48, 69, 74, 105].
Although both PQ and subspace collision framework divide the 3 SUBSPACE COLLISION FRAMEWORK
high-dimensional space into subspaces, their design concepts are
3.1 Framework Design
different. PQ sums the distances between quantized data points and
the query in all subspaces to judge similarity, while the subspace Intuitively, two data points that are close in the high-dimensional
collision framework counts the number of collisions between data original space are also more likely to be close in its random subspace.
points and the query in all subspaces to judge similarity. Optimized Given a dataset D of 𝑛 data points in 𝑑-dimensional space and a
Product Quantization (OPQ) [38] using the inverted multi-index [9] query 𝑞 ∈ R𝑑 , and 𝑜 1∗, . . . , 𝑜𝑘∗ are the 𝑘-NNs of 𝑞 in D. Suppose we
is the state-of-the-art VQ-based method [31, 68]. randomly select 𝑠 dimensions from all 𝑑 dimensions as a subspace
Tree-based methods. Tree-based methods hierarchically par- (𝑠 < 𝑑), and the points 𝑜 1∗, . . . , 𝑜𝑘∗ and 𝑞 in this subspace are denoted
tition the high-dimensional space and group similar data points as 𝑜 1∗′, . . . , 𝑜𝑘∗′ and 𝑞 ′ . Then, it is expected that statistically, the prox-
into the same partition as leaf nodes [97]. The partitioning process imity of 𝑜 1∗′, . . . , 𝑜𝑘∗′ and 𝑞 ′ is greater than other points in D. The
is usually recursive, so the root node of the tree covers the entire above intuition is based on the premise that the distances between
high-dimensional space, and its children nodes cover disjoint sub- data points are relatively evenly distributed in each dimension. If
spaces. Based on the way of partitioning, there are three categories the distance between two points is concentrated in some dimen-
of tree-based methods: pivoting [19, 21, 108], hyperplane [14, 20, 22, sions, the above intuition may not hold. As shown in Figure 1(a)
26, 29, 32, 51, 58, 70, 81–83, 86, 93, 95, 96, 99, 107, 114] and compact and Figure 1(b), if we choose the 𝑥 dimension as the subspace for
partitioning [15, 35, 73]. Hyperplane partitioning is the most popu- measuring distance, 𝑂 5 is the nearest neighbor because its distance
lar tree-based method, which recursively partitions the space by from the query point 𝑞 is only distributed in the 𝑦 dimension. Simi-
the hyperplane with random direction or axis-aligned separating larly, if we choose the 𝑦 dimension as the subspace for measuring
hyperplane. Annoy [14] is the state-of-the-art tree-based method distance, 𝑂 3 and 𝑂 6 are the nearest neighbors since their distances
with balanced indexing and query answering performance [54]. to 𝑞 are mostly distributed in the 𝑥 dimension. Points like 𝑂 1 and
Graph-based methods. Graph-based methods construct a prox- 𝑂 2 , which are close to 𝑞 but their distances evenly distributed in
imity graph where each node represents a data point, and edges both 𝑥 and 𝑦 dimensions, are easily missed.
represent the neighbor relationships between data points [7, 90, 92]. We need to design a framework to solve the above problems,
The main idea of graph-based methods is “a neighbor’s neighbor is which meets two requirements:
likely also to be a neighbor”. Compared with other types of meth- • Req1: combine multiple subspaces to alleviate significant
ods, graph-based methods typically have better query efficiency errors that a single subspace may cause;
but require considerably more time to construct indexes [31, 54]. • Req2: reduce the impact of distance ranking within a single
The reason is that graph-based methods need to identify the near subspace on the final result.
neighbors for each data point in the dataset (and connect to them)
To this end, we first define “collision” and “subspace collision”.
during the indexing phase, while in the query phase, they only need
to search on a gradually converging path. Based on the way of build- Definition 1 (Collision). Given a dataset D of 𝑛 data points in
ing the proximity graph, there are three categories of graph-based 𝑑-dimensional space, a query point 𝑞 ∈ R𝑑 , and a collision ratio
methods: cluster and merge [71], iterate from an initial graph [23, 𝛼 ∈ (0, 1), if a data point 𝑜 ∈ D satisfies: ∥𝑜, 𝑞∥ is one of the
28, 33, 34, 54, 84], consecutive insertion [6, 64, 66, 67, 110]. Although minimum 𝛼 · 𝑛 distances between all 𝑛 data points and 𝑞, i.e., 𝑜 is
there have been some innovative works subsequently, HNSW [67] one of the (𝛼 · 𝑛)-NNs of 𝑞 in D, we say that 𝑜 collides with 𝑞.
SIGMOD ’25, June 22–27, 2025, Berlin, Germany Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng
Table 1: Notations Algorithm 1: SC-Linear
Input: Dataset D, dataset size 𝑛, data dimensionality 𝑑,
Notation Description query point 𝑞, number of results 𝑘, subspace number
R𝑑 𝑑-dimensional Euclidean space 𝑁𝑠 , collision ratio 𝛼, re-rank ratio 𝛽
D Dataset of points in R𝑑 Output: 𝑘 nearest points to 𝑞 in D
1 Initialize an array 𝑆𝐶_𝑠𝑐𝑜𝑟𝑒𝑠 of length 𝑛 and set all elements
𝑛 Dataset cardinality |D|
to 0;
𝑜, 𝑞 A data point in D and a query point in R𝑑
2 Divide the 𝑑-dimensional space into 𝑁𝑠 subspaces:
𝑜𝑖∗ The 𝑖-th nearest data point to 𝑞 in D
𝑆 1 , 𝑆 2 , . . . , 𝑆 𝑁𝑠 ;
𝑜𝑖 The 𝑖-th data point in D
3 Divide all data points 𝑜 1 , . . . , 𝑜 𝑛 and 𝑞 into 𝑁𝑠 subspaces;
∥𝑜 1, 𝑜 2 ∥ The Euclidean distance between 𝑜 1 and 𝑜 2
4 for 𝑖 = 1 to 𝑁𝑠 do
𝑜 ′, 𝑞 ′ 𝑜 and 𝑞 in a subspace
𝑁𝑠 Number of subspaces 5 for 𝑗 = 1 to 𝑛 do
𝑠 Dimension of each subspace 6 Calculate the Euclidean distance between 𝑜 𝑖𝑗 and 𝑞𝑖 ;
𝑆𝑖 , D𝑖 The 𝑖-th subspace and all data points in 𝑆𝑖 7 Sort 𝑜 𝑖1, . . . , 𝑜𝑛𝑖 by their distances to 𝑞𝑖 in 𝑆𝑖 ;
𝑜 𝑖𝑗 , 𝑞𝑖 The 𝑗-th data point and 𝑞 in the 𝑖-th subspace 8 for 𝑧 = 1 to 𝛼 · 𝑛 do
𝛼 Collision ratio 9 Select the 𝑧-th-nearest point to 𝑞𝑖 whose id in D is 𝑡;
𝛽 Re-rank ratio 10 𝑆𝐶_𝑠𝑐𝑜𝑟𝑒𝑠 [𝑡]++;
𝐾, 𝑡 Number of K-means clusters and iterations
11 Sort 𝑆𝐶_𝑠𝑐𝑜𝑟𝑒𝑠 in descending order;
12 for 𝑧 = 1 to 𝛽 · 𝑛 do
Definition 2 (Subspace Collision). Given a dataset D of 𝑛 data 13 Select the point with the 𝑧-th-largest SC-score in
points in 𝑑-dimensional space, a query 𝑞 ∈ R𝑑 , and a collision ratio 𝑆𝐶_𝑠𝑐𝑜𝑟𝑒𝑠 whose id in D is 𝑡;
𝛼 ∈ (0, 1). We randomly select 𝑠 dimensions from all 𝑑 dimensions 14 Calculate the Euclidean distance between 𝑜𝑡 and 𝑞;
as a subspace R𝑠 (𝑠 < 𝑑). The dataset D, the data point 𝑜, and the 15 return the top-𝑘 points closest to 𝑞 in the 𝛽 · 𝑛 candidates;
query point 𝑞 in this subspace are denoted as D ′ , 𝑜 ′ , and 𝑞 ′ . If a
point 𝑜 ∈ D satisfies: 𝑜 ′ is one of the (𝛼 · 𝑛)-NNs of 𝑞 ′ in D ′ , we
say that 𝑜 collides with 𝑞 in the subspace R𝑠 .
Definition 4 (SC-score). Given a dataset D of 𝑛 data points in
The definition of subspace collision downplays the distance rank- 𝑑-dimensional space, a query 𝑞 ∈ R𝑑 , 𝑁𝑠 𝑠-dimensional subspaces,
ing between data points and 𝑞 in the subspace, allowing Req2 to a collision ratio 𝛼 ∈ (0, 1). Probe collisions of 𝑞 in 𝑁𝑠 subspaces
hold. As long as a data point is close enough to 𝑞 (in the (𝛼 ·𝑛)-NNs), with the collision ratio 𝛼. For a data point 𝑜 ∈ D, its SC-score is the
it can be considered as colliding with 𝑞 in the subspace. Subspace number of subspaces where it collides with 𝑞. Therefore, SC-score
collision can thus alleviate the problem that the distance between is an integer in [0, 𝑁𝑠 ].
𝑜 and 𝑞 is mainly distributed in specific dimensions.
SC-score combines the collision results of 𝑁𝑠 subspaces to judge
Since using only one subspace to measure the similarity between
the similarity between data points and query points, allowing Req1
data points and the query point may cause significant errors, we
to hold. As shown in Figure 1(c), data points that are closer to the
need to design a method to obtain multiple subspaces and a method
query point in the original space tend to have larger SC-scores
that combines the collision results of these subspaces to judge the
(𝛼 = 0.5), and the subspace collision framework can return high-
similarity. To make full use of the information in all 𝑑 dimensions
quality results even if the distances between data points and the
of the data points, we design a multi-round sampling strategy “Sub-
query point are unevenly distributed. For example, 𝑂 1 and 𝑂 2 are
space Sampling” for the 𝑑 dimensions.
not the closest points to 𝑞 in both 𝑥 and 𝑦 dimensions, but they
Definition 3 (Subspace Sampling). Given a dataset D of 𝑛 data have the highest SC-score and, thus, the highest similarity. SC-score
points in 𝑑-dimensional space, we adopt a multi-round sampling reduces the similarity measurement error caused by the unevenly
strategy to obtain 𝑁𝑠 subspaces. In round 𝑖, a number of 𝑠 = ⌊ 𝑁𝑑𝑠 ⌋ distributed distance between 𝑜 and 𝑞 in different dimensions. The
dimensions are uniformly sampled without replacement to form a experimental results in Section 3.3.1 (Figure 2) show that SC-score
subspace 𝑆𝑖 , 𝑖 = 1, 2, . . . , 𝑁𝑠 − 1. For the last subspace 𝑆 𝑁𝑠 , it simply is a good metric to measure the Euclidean distance between data
pick up all remaining dimensions. points and query point because “data points closer to query point
tend to have larger SC-scores.” Both Figure 1 and Figure 2 show that
Definition 3 makes full use of all dimensions of the data. Even if the proposed subspace collision framework appropriately addresses
𝑑 is not an integer, all remaining dimensions after 𝑁𝑠 − 1 rounds
𝑁𝑠 Req1 and Req2 simultaneously. Theorem 1 in Section 3.4 provides
of sampling will be picked up by the last subspace 𝑆 𝑁𝑠 . For ease of a theoretical guarantee on the effectiveness of SC-score.
reading and understanding, we assume that 𝑁𝑑𝑠 is an integer in the
following sections, i.e., all subspaces (𝑆 1, ..., 𝑆 𝑁𝑠 ) have 𝑠 = 𝑁𝑑𝑠 . 3.2 Naive method for ANN
Based on the obtained 𝑁𝑠 subspaces, we design a metric “Sub- Based on the subspace collision framework proposed in Section 3.1,
space Collision Score (SC-score)” to measure the similarity between we design a naive method (without index structure) called SC-Linear
a data point and the query point. to support ANN search, as shown in Algorithm 1. First, an array is
Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search SIGMOD ’25, June 22–27, 2025, Berlin, Germany
Table 2: Recall of SC-Linear when returning 50 NNs under
different datasets and parameters.
𝛼=0.05 𝛼=0.05 𝛼=0.05 𝛼=0.05
𝛽=0.001 𝛽=0.005 𝛽=0.01 𝛽=0.05
Sift10M 0.9536 0.9916 0.9968 1
Deep10M 0.9418 0.9848 0.9968 1
SPACEV10M 0.9742 0.994 0.9962 0.9992
Turing10M 0.9638 0.9876 0.9944 0.999
(a) Sift10M: 𝑑 =128, 𝑁𝑠 =8, 𝑠 =16, 𝛼 =0.1 (b) Yandex Deep10M: 𝑑 =96, 𝑁𝑠 =8, 𝑠 =12,
𝛼 =0.1
returned by Algorithm 1. However, SC-Linear has no index struc-
ture to achieve fast query answering. It relies on calculating the
Euclidean distance between all data points and the query point in all
subspaces, which has the same time complexity as linear scanning
in the original space (that is why we named Algorithm 1 SC-Linear).
Therefore, we need to further design an index structure and query
strategies for the subspace collision framework to improve query
efficiency, which will be introduced in Section 4.
(c) Microsoft SPACEV10M: 𝑑 =100, (d) Microsoft Turing-ANNS10M: 𝑑 =100, 3.3 Preliminary Experiments
𝑁𝑠 =10, 𝑠 =10, 𝛼 =0.1 𝑁𝑠 =10, 𝑠 =10, 𝛼 =0.1 In this section, we conduct preliminary experiments to determine
whether the subspace collision framework is effective. On the one
Figure 2: “Pareto principle” of SC-score on four datasets. hand, we explore whether SC-score is a good measure of the dis-
Each figure contains 𝑛 = 10M (107 ) scatter points, the scatter tance between all data points and the query point. On the other
(𝑖, 𝑗) represents the average SC-score of the 𝑖-th NN for 1000 hand, we measure the performance of the SC-Linear algorithm to
queries is 𝑗, where 𝑖 = 1, 2, . . . , 107 , and 𝑗 ∈ [0, 𝑁𝑠 ]. see whether it can return high-quality query results. More detailed
experiments and parameter learning will be given in Section 5.3.
3.3.1 Effectiveness of SC-score. We select 1000 queries and count
initialized to record the SC-score of each data point (line 1). Then, the SC-score of all data points in the dataset under each query. We
use Definition 3 to sample and obtain 𝑁𝑠 subspaces, and divide all perform this statistical analysis on multiple commonly used ANN
data points and the query point into these subspaces, where 𝑜 𝑖𝑗 and datasets. Due to space limitations, we only show the results on four
𝑞𝑖 represent the 𝑗-th data point and 𝑞 in the 𝑖-th subspace (lines datasets in Figure 2 (other results are similar).
2-3). In practice, for convenience, we can divide the 𝑑-dimensional We can see from Figure 2 that SC-score follows the “Pareto
principle” and is insensitive to the data distribution. Data points
space into 𝑁𝑠 subspaces of the same length 𝑠 = 𝑁𝑑𝑠 , where the 𝑖-th
that are close to the query point have a high SC-score. Then, as the
subspace is allocated from the (𝑠 · (𝑖 −1) +1)-th to (𝑠 ·𝑖)-th dimensions
distance increases, the SC-score decreases rapidly until a “turning
in the original space, 𝑖 = 1, . . . , 𝑁𝑠 . This division method can be
point” is reached. After the “turning point”, the SC-score decreases
regarded as a special case of Definition 3. In order to count the SC-
slowly with the distance. The sharp change in trend makes each
score of each data point, it is necessary to calculate the Euclidean
figure look like an “L” shape.
distance between each data point and 𝑞 in each subspace (lines
The “Pareto principle” of SC-score makes it very suitable for
4-6). For each subspace 𝑆𝑖 , sort the distances and select 𝛼 · 𝑛 points
ANN search. In all four datasets, the x-axis of the “turning point”
closest to 𝑞𝑖 as collisions, and increase the SC-score of these points
is about 0.2𝑛, which means that the 20% of data points closest to
by one, where 𝛼 is the collision ratio (lines 7-10). To further improve
the query have a large and distinguishable SC-score, while the
query accuracy, we design a re-ranking mechanism (lines 11-15).
remaining 80% of the data points have a small and indistinguishable
Specifically, sort the SC-scores of all points and select 𝛽 · 𝑛 points
SC-score. Therefore, we only need to select data points with a
with the largest SC-scores as candidates, where 𝛽 is the re-rank
large enough SC-score before the “turning point” to obtain high-
ratio (lines 11-13). Calculate the Euclidean distance between all
quality ANN search results. SC-Linear is designed based on this idea.
candidates and 𝑞 in the original space, and return the top-𝑘 points
Specifically, the re-ranking mechanism (lines 11-15 in Algorithm 1)
closest to 𝑞 (lines 14-15). To facilitate understanding of SC-Linear,
selects 𝛽 · 𝑛 data points with the largest SC-scores as candidates
readers can refer to Figure 3 (the workflow of SuCo method). The
and then returns the top-𝑘 data points closest to the query among
difference between SC-Linear and SuCo is that SC-Linear does not
these candidates. Experimental results in Section 3.3.2 demonstrate
construct the inverted multi-indexes to speed up query answering.
that SC-Linear can return high-quality ANN results.
The experimental results in Section 3.3.2 show that SC-Linear has
high query accuracy, which demonstrates the effectiveness of our 3.3.2 Performance of SC-Linear. To measure whether SC-Linear
designed subspace collision framework. Theorem 2 in Section 3.4 can return high-quality results, we perform ANN search when 𝑘=50
provides a theoretical guarantee on the quality guarantee of results on four datasets (𝑁𝑠 and 𝑠 set for each dataset are the same as that
SIGMOD ’25, June 22–27, 2025, Berlin, Germany Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng
𝑗 𝑗
in Figure 2). Table 2 shows the average recall of 100 queries. We can random variable 𝑍 1 − 𝑍 2 is of zero mean and variance 2𝜎 2 , it then
see that SC-Linear can support accurate ANN search with extremely follows from Chebyshev’s inequality that, for any 𝑡 > 0,
high recall, demonstrating that the subspace collision framework 𝑗 𝑗
Pr (|𝑍 1 − 𝑍 2 | ≥ 𝑡) ≤ 2𝜎 2 /𝑡 2, (4)
we designed is very suitable for ANN search. Furthermore, when
the parameters 𝑁𝑠 and 𝛼 are set reasonably, SC-Linear can still have and thus
a high recall even if a very small re-rank ratio 𝛽 is used. This also
|𝑍 1 − 𝑍 2 | ≤ (𝑁𝑠 − 𝐶 − Δ)𝑡 .
Í 𝑗 𝑗
0≤ 𝑗 ∈ S¬𝐶 (5)
confirms the rule that “data points closer to query point tend to have
larger SC-scores”. More detailed parameter learning on 𝛼, 𝛽, and 𝑁𝑠 ′
For scenario (ii), we have, for some 𝑡 > 0 and a given 𝑗,
will be given in Section 5.3. √︁
0 ≤ 𝑍 1 ≤ (1 − 𝛼)(𝜎 2 + 𝑚 2 ), Pr (|𝑍 2 − 𝑚| ≥ 𝑡 ′ ) ≤ (𝜎/𝑡 ′ ) 2 .
𝑗 𝑗
3.4 Theoretical Guarantee Finally, adding things up leads to
√︁
𝑗 ∈ S𝐶 ∪S¬𝐶 |𝑍 2 − 𝑍 1 | ≤ 𝐶 (1 − 𝛼)(𝜎 + 𝑚 ) + (𝑁𝑠 −𝐶 − Δ)𝑡, (6)
In this section, through rigorous mathematical analysis, we provide Í 𝑗 𝑗 2 2
theoretical guarantees on the effectiveness of SC-score and the
quality guarantee of our proposed subspace collision framework holds with probability at least 1 − 2(𝑁𝑠 −𝐶 − Δ)𝜎 2 /𝑡 2 , for any 𝑡 > 0.
for ANN search. √︁ that the worst case is the case of Δ = 1, taking
Note √︁ then 𝑡 = 𝑐 1 (𝑚 −
(1 − 𝛼)(𝜎 2 + 𝑚 2 )) and 𝑡 ′ = 𝑐 2𝑚 + (1 − 𝑐 2 ) (1 − 𝛼) (𝜎 2 + 𝑚 2 ))
Theorem 1 (Effectiveness of SC-score). Given a query point 𝑞 ∈ R𝑑 ,
with some 𝑐 1, 𝑐 2 > 0 such that
two independent random data points 𝑜 1, 𝑜 2 ∈ dataset D, and the SC-
score of 𝑜 1 is greater than that of 𝑜 2 , then ∥𝑜 1, 𝑞∥ < ∥𝑜 2, 𝑞∥ holds with (𝑐 2 − 𝑐 1 (𝑁𝑠 − 𝐶 − 1))𝑚 >
probability at least 1/2 − 1/𝑒 2 for appropriate choices of the number
√︁ (7)
(𝐶 + 𝑐 2 − 𝑐 1 (𝑁𝑠 − 𝐶 − 1)) (1 − 𝛼)(𝜎 2 + 𝑚 2 ),
of subspaces 𝑁𝑠 and collision ratio 𝛼 ∈ (0, 1) that depend on the data
statistics and the dimension 𝑑. then we have ∥𝑜 1, 𝑞∥ < ∥𝑜 2, 𝑞∥. It can be checked that this happens
−2
2(𝑁 −1)
√︁
with probability at least 1− 𝑐𝑠2 𝑚/𝜎 − (1 − 𝛼)(1 + 𝑚 2 /𝜎 2 ) −
Proof of Theorem 1. In the following, we provide a proof of 1
√︁ −2
Theorem 1 by making explicit the impact of the number of subspaces 𝑐 2 · 𝑚/𝜎 + (1 − 𝛼)(1 + 𝑚 2 /𝜎 2 )(1 − 𝑐 2 ) . For given 𝑚, 𝜎 2 , we
𝑁𝑠 and the collision ratio 𝛼 ∈ (0, 1) as a function of the data· √︁ √︁
statistics. Assume without loss of generality that 𝑁𝑑𝑠 is an integer. take 𝑐 1 = 8(𝑁𝑠 − 1)/(𝑚/𝜎 − (1 − 𝛼)(1 + 𝑚 2 /𝜎 2 )), 𝑐 2 = (𝑒 −
√︁ √︁
𝑗 𝑑 (1 − 𝛼)(1 + 𝑚 2 /𝜎 2 ))/(𝑚/𝜎 − (1 − 𝛼)(1 + 𝑚 2 /𝜎 2 )) and any 𝛼 >
Let 𝑜𝑖 ∈ R 𝑁𝑠 and 𝑞 𝑗 denote the subvector of 𝑜𝑖 and 𝑞 in the 𝑗-th
max(1/(1 + 𝑚 2 /𝜎 2 ), 1 − 𝑒 2 /(1 + 𝑚 2 /𝜎 2 )), we have 𝑐 1, 𝑐 2 > 0 so that
subspace, with 𝑖 ∈ {1, 2}, 𝑗 ∈ {1, . . . , 𝑁𝑠 }, and 𝑁𝑠 is the number
the success probability is at least 1/2 − 1/𝑒 2 . This concludes the
of subspaces. Let 𝑧𝑖 = |𝑜𝑖 − 𝑞| ∈ R𝑑 denote the vector of absolute proof of Theorem 1. □
𝑗 𝑑
difference between 𝑜𝑖 and 𝑞, and 𝑧𝑖 ∈ R 𝑁𝑠 its subvectors. Assume
𝑗 𝑗 2 Theorem 2 (Quality Guarantee of ANN Search). Given a query
that the squared Euclidean norms of subvector 𝑍𝑖 ≡ 𝑧𝑖 are point 𝑞 ∈ R𝑑 and a dataset D consist of 𝑛 independent random vectors,
independent random variables with mean 𝑚 > 0 and variance 𝜎 2 , then, Algorithm 1 can answer a 𝑘-ANN query for 𝑞 with probability
we compare the following differences at least 1/2, with appropriate choices of the number of subspaces 𝑁𝑠 ,
Í 𝑠 𝑗 Í 𝑠 𝑗 the collision ratio 𝛼 ∈ (0, 1), and the re-rank ratio 𝛽 ∈ (0, 1), as a
∥𝑧 1 ∥ 2 = 𝑁
𝑗=1 𝑍 1 , ∥𝑧 2 ∥ 2 = 𝑁
𝑗=1 𝑍 2 , (1)
function of the data statistics, the dataset size 𝑛, and the dimension 𝑑.
by evaluating the number of subspace collisions (i.e., SC-score).
𝑗 𝑗
Note that the subvectors 𝑜 1 versus 𝑜 2 with same index 𝑗 must Proof of Theorem 2. Without loss of generality, we assume
belong to one the following three scenarios: 𝑑/𝑁𝑠 is an integer. Following the notations in the proof of Theo-
𝑗 𝑑
(i) “subspace collision” happens for both subvectors, this hap- rem 1, we denote 𝑜𝑖 ∈ R 𝑁𝑠 and 𝑞 𝑗 the subvector of 𝑜𝑖 and 𝑞 in the
pens 𝐶 ∈ {0, . . . , 𝑁𝑠 − 1} times; or 𝑗-th subspace, respectively, with 𝑖 ∈ {1, . . . , 𝑛} and 𝑗 ∈ {1, . . . , 𝑁𝑠 }.
𝑗 𝑗
(ii) “subspace collision” happens for 𝑜 1 but not 𝑜 2 , this happens Let 𝑧𝑖 = |𝑜𝑖 − 𝑞| ∈ R𝑑 denote the vector of absolute difference
𝑑
Δ ∈ {1, . . . , 𝑁𝑠 − 𝐶} times; or
𝑗
between 𝑜𝑖 and 𝑞, and 𝑧𝑖 ∈ R 𝑁𝑠 its subvectors. Assume that
(iii) “subspace collision” happens for neither subvector, this hap- 𝑗 𝑗 2
𝑍𝑖 ≡ 𝑧𝑖 are independent random variables across index 𝑖 and 𝑗,
pens 𝑁𝑠 − 𝐶 − Δ times.
with mean 𝑚 > 0 and variance 𝜎 2 , we obtain by independence that
For scenario (i), it follows from the Paley–Zygmund anti-concentration
inequality that, E[∥𝑧𝑖 ∥ 2 ] = 𝑁𝑠 𝑚, Var[∥𝑧𝑖 ∥ 2 ] = 𝑁𝑠 𝜎 2, (8)
√︁
𝑗
Pr 𝑍𝑖 ≤ (1 − 𝛼)(𝜎 2 + 𝑚 2 ) ≤ 𝛼, (2) for which each index 𝑗 must belong to one the following two cases:
𝑗
(i) “subspace collision” happens for subspace 𝑜𝑖 , this happens
with a collision ratio 𝛼 ∈ (0, 1). We thus have, on the index set S𝐶
for 𝐶 ∈ {0, . . . , 𝑁𝑠 } times for the data vector 𝑜𝑖 ; or
(of cardinality 𝐶) on which collision occurs, that 𝑗
√︁ (ii) “subspace collision” does not happen for 𝑜𝑖 , this happens for
Í 𝑗
0 ≤ 𝑗 ∈ S𝐶 𝑍𝑖 ≤ 𝐶 (1 − 𝛼)(𝜎 2 + 𝑚 2 ). (3) 𝑁𝑠 − 𝐶 times for the data vector 𝑜𝑖 .
For scenario (iii), on non-collision subspaces (that corresponds to Similar to the proof of Theorem 1, in each case, we can bound the
the index set S¬𝐶 having cardinality 𝑁𝑠 − 𝐶 − Δ), note that the
𝑗
value of 𝑍𝑖 as follows.
Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search SIGMOD ’25, June 22–27, 2025, Berlin, Germany
(i) By Paley–Zygmund inequality that �
-dimensional
2
𝑗 √︁
...
Pr 𝑍𝑖 ≤ (1 − 𝛼)(𝜎 2 + 𝑚 2 ) ≤ 𝛼, (9) � 1 K-Means K ce
ntro
of
...
�-dimensional Clustering id
alf
... s Inverted Multi-Index
with a collision ratio 𝛼 ∈ (0, 1). rs th with �2 cells for �1
... Fi ... ids
�-dimensional t ro
(ii) By Chebyshev’s inequality that, for any 𝑡 > 0, �1 K-Means cen
...
Clustering K
...
... Second half ...
... of �1
𝑗 2 2
Pr (|𝑍𝑖 − 𝑚| ≥ 𝑡) ≤ 𝜎 /𝑡 . (10)
...
...
...
...
... First half
... ...
of ��� K-Means K ce
We thus have that Raw Dataset �� � ntro
...
...
Clustering id
... ... s
√︁ Se Inverted Multi-Index
2
(𝑁𝑠 − 𝐶) (𝑚 − 𝑡) ≤ ∥𝑧𝑖 ∥ ≤ 𝐶 (1 − 𝛼)(𝜎 2 + 𝑚 2 ) + (𝑁 − 𝐶)(𝑚 + 𝑡), co with �2 cells for ���
𝑠 of nd ... ids
�� hal K-Means t ro
f cen
...
Clustering K
holds with probability at least 1 − (𝑁𝑠 − 𝐶)𝜎 2 /𝑡 2 . In the following, �
...
without loss of generality, we only discuss here the case where the
= 𝑁𝑠 , for which we should have 𝑘
re-rank ratio 𝛽 is chosen so that 𝐶 √︁ Divide �� subspaces Generate Inverted Multi-Index for each subspace
and 𝛽 both small, and ∥𝑧𝑖 ∥ 2 ≤ 𝑁𝑠 (1 − 𝛼)(𝜎 2 + 𝑚 2 ). Other scenar- (a) Index construction.
ios with 𝐶 < 𝑁𝑠 can be similarly studied by increasing 𝛽 accordingly.
In this setting, we show in the following, that the �-dimensional
√︁ obtained range of ... Inverted Multi-Index
Result
1st
the squared Euclidean distance ∥𝑧𝑖 ∥ 2 ∈ (0, 𝑁𝑠 (1 − 𝛼)(𝜎 2 + 𝑚 2 )] �-dimensional �1 with �2 cells for �1 Collisions in �1
Candidates 2nd
is indeed among the top-𝑘 smallest in a set of 𝑛 samples, with a ... Collision Rerank
Counting
...
...
3rd
Query
���
...
controlled probability. The moments and joint distribution of the ... Inverted Multi-Index Collisions in ���
with �2 cells for ��� k-th
top-𝑘 ordered (e.g., smallest) values in a set of 𝑛 i.i.d. samples has
been extensively studied in the literature of order statistics [1, 2].
Divide query Count collisions Re-rank and return top-k
For the simplicity of exposition, we discuss here the case where into subspaces in all subspaces candidates as the result
the squared distances are normally distributed ∥𝑧𝑖 ∥ 2 ∼ N (𝑁𝑠 𝑚, 𝑁𝑠 𝜎 2 )
(which, as we shall see below, admits closed-form approximation for (b) Query answering.
moments and leads to an explicit control of the success probability
as a function of all tuning parameters). To treat general (e.g., non- Figure 3: Overview of the SuCo workflow.
Gaussian) distributions, it suffices to replace the (approximations
of) first and second moments in (11) and (12) using PDF and CDF
of the specific distribution. In the normal case, the expectation of be chosen (within a range) to achieve an optimal “computation-
the 𝑘-th order statistic (i.e., the expected value of the 𝑘 smallest accuracy trade-off.” This is consistent with the choice of 𝛼, 𝛽 in
value) in a set of 𝑛 sample with 𝑛 large is approximately given by the proofs of Theorems 1 and 2 above, and with our experimental
√︁ 𝑘 −𝛾 conclusions in Section 5.3.3.
𝐸𝑘,𝑛 = 𝑁𝑠 𝑚 + 𝑁𝑠 𝜎 2 · Φ −1 , 𝛾 = 0.375, (11)
𝑛 − 2𝛾 + 1
and variance approximately given by 4 THE SUCO METHOD
−2 As analyzed in Section 3.2 and Section 3.3, SC-Linear’s query effi-
𝑘 (𝑛 − 𝑘 + 1) −1 𝑘
𝑉𝑘,𝑛 = 𝑁𝑠 𝜎 2 · 𝜙 Φ , (12) ciency is limited because when counting collisions in each subspace,
(𝑛 + 1) 2 (𝑛 + 2) 𝑛+1 it is necessary to calculate the Euclidean distance between the query
with 𝜙 (·) and Φ(·) the PDF and CDF of standard Gaussian distri- and all data points (lines 4-10 in Algorithm 1). Therefore, the prob-
bution. These approximations are known to be rather accurate as lem that needs to be solved is transformed into “how to find the
long as 𝑛 ≥ 9, see [13, 16]. Thus, it follows again from Cheby- 𝛼 · 𝑛 data points closest to the query in each subspace as quickly and
shev’s inequality that the probability
√︁ of correct answering is at least accurately as possible.”
1−𝑉𝑘,𝑛 /𝑡 2 for 𝑡 such that 𝑡 > 𝑁𝑠 𝑚 (1 − 𝛼)(1 + 𝜎 2 /𝑚 2 ) −𝐸𝑘,𝑛 . Tak- In this section, we propose SuCo to accelerate collision counting
√ 𝑘 (𝑛−𝑘+1)
−1 in each subspace by building lightweight indexes and designing
ing 𝑁𝑠 and 𝛼 ∈ (0, 1) and 𝑡 = 2𝑁𝑠 𝜎𝑛 𝑛 𝜙 Φ −1 𝑛+1 𝑘 ,
query strategies. Figure 3 provides a high-level overview of the
we conclude that the probability of correct answering is at least SuCo workflow, including index construction and query answering.
1/2. This concludes the proof of Theorem 2. □
The proof of Theorem 1 relies on the idea that in cases where 4.1 Index Construction
“subspace collision” happens for both or neither of the two subvec- To count collisions as quickly and accurately as possible, i.e., find
tors, their Euclidean distance should be approximately the same; the 𝛼 · 𝑛 data points closest to the query in each subspace, we need
while in cases where “subspace collision” happens for one but not to construct an index in each subspace, which should be able to
the other, their distance should differ by a significant amount, mak- quickly locate data points around the query.
ing the overall distance different. A similar argument holds for a There are two requirements for the index structure: (1) The
single data in the proof of Theorem 2. Intuitively, larger values of index structure should be lightweight enough. The index needs
collision ratio 𝛼 and re-rank ratio 𝛽 lead to higher computational to be constructed independently in all 𝑁𝑠 subspaces, and 𝑁𝑠 is 6-
complexity, while too small 𝛼 and 𝛽 reduce the accuracy of the pro- 12 in practice. If the index structure is complex, it requires a long
posed approach. As a consequence, the parameters 𝛼 and 𝛽 should indexing time and a large memory footprint to construct 𝑁𝑠 indexes.
SIGMOD ’25, June 22–27, 2025, Berlin, Germany Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng
1000
500
500
1000
1000 500 0 500 1000
(a) K-means clustering with inverted index. K-means clustering is (b) K-means clustering with inverted multi-index. K-means clustering
√
performed in the 2D space. The inverted index holds 𝐾 2D centroids is performed in each dimension. The inverted multi-index holds 𝐾
(red stars in the figure). 1D centroids for each dimension. 𝐾 2D clusters are obtained through
Cartesian product of 1D clusters.
Figure 4: Illustration of K-means clustering (𝐾=16) in 2D space using inverted index or inverted multi-index.
Therefore, the graph-based and tree-based indexes that are currently Algorithm 2: Create Index
popular in ANN search are no longer applicable. (2) The query Input: A dataset D, dataset size 𝑛, dimensionality of data
method for collision counting needs to be simple and fast enough. points 𝑑, subspace number 𝑁𝑠 , number of K-means
Collision counting needs to be performed in all 𝑁𝑠 subspaces, so the clusters 𝐾, number of K-means iterations 𝑡
query speed of the index for each subspace needs to be fast enough. Output: Centroid list 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠 and inverted multi-index
Fortunately, we don’t need to obtain few (usually 𝑘 ∈ [1, 100]) list 𝐼𝑀𝐼𝑠
but accurate query results like graph-based and tree-based indexes. 1 Initialize a list 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠 of length 2𝑁𝑠 and a list 𝐼𝑀𝐼𝑠 of
We only need to find many (𝛼 · 𝑛, usually 𝛼 ∈ [0.01, 0.1]) but not length 𝑁𝑠 ;
necessarily accurate data points as collisions. 2 Divide the 𝑑-dimensional space into 𝑁𝑠 subspaces:
Clustering-based indexes can meet the above two requirements. 𝑆 1 , 𝑆 2 , . . . , 𝑆 𝑁𝑠 ;
The index structure is lightweight enough because only the cluster 3 Divide all data points into 𝑁𝑠 subspaces: D1 , . . . , D𝑁𝑠 ;
centroids and data point assignments for each cluster need to be
4 for 𝑖 = 1 to 𝑁𝑠 do
recorded. The query method for collision counting is simple and
5 Initialize a map 𝐼𝑀𝐼𝑖 as the inverted multi-index;
fast enough because only the distance between the query and each
6 Further divide 𝑆𝑖 into two subspaces 𝑆𝑖1 and 𝑆𝑖2 ;
centroid needs to be calculated. Each centroid can represent all data
7 Divide D𝑖 into two subspaces: D𝑖1 and D𝑖2 ;
points in its cluster, and if the centroid is close enough to the query, √
all data points within the cluster can be considered to collide with 8 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠𝑖1, 𝑎𝑠𝑠𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠𝑖1 ← call Kmeans(D𝑖1, 𝐾, 𝑡);
√
the query. Ordinary K-means clustering uses an inverted index to 9 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠𝑖2, 𝑎𝑠𝑠𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠𝑖2 ← call Kmeans(D𝑖2, 𝐾, 𝑡);
store which data points are in each cluster. However, to achieve 10 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠.𝑎𝑝𝑝𝑒𝑛𝑑 (𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠𝑖1, 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠𝑖2 );
fine-grained indexing, many clusters need to be constructed (𝐾 is 11 for 𝑗 = 0 to 𝑛 − 1 do
large), which will restrict indexing and query answering efficiency. 12 𝐼𝑀𝐼𝑖 [𝑎𝑠𝑠𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠𝑖1 [ 𝑗], 𝑎𝑠𝑠𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠𝑖2 [ 𝑗]].𝑎𝑝𝑝𝑒𝑛𝑑 ( 𝑗);
The inverted multi-index (IMI) [9] replaces the vector quantization
13 𝐼𝑀𝐼𝑠.𝑎𝑝𝑝𝑒𝑛𝑑 (𝐼𝑀𝐼𝑖 );
inside the inverted index of K-means with the product quantiza-
tion [45]. Figure 4 shows the difference between K-means clustering 14 return 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠 and 𝐼𝑀𝐼𝑠;
using the inverted index and the inverted multi-index. In Figure 4(a),
K-means clustering is performed in the 2D space, and the inverted
index holds 𝐾=16 2D centroids and the IDs of all data points belong- Figure 3(a) shows the workflow of SuCo to construct the index,
ing to each cluster. In Figure 4(b), K-means clustering is√performed and Algorithm 2 gives the pseudocode. First, we need to initialize
in each dimension, and the inverted multi-index holds 𝐾 = 4 1D two lists, one to store the centroids obtained by clustering in each
centroids for each dimension and the IDs of all data points belong- subspace (the first part of our index) and the other to store the in-
ing to the cluster. Then, 𝐾=16 2D clusters can be obtained through verted multi-indexes constructed in each subspace (the second part
the Cartesian product of 1D clusters. Therefore, given the number of our index) (line 1). Then, we divide the 𝑑-dimensional original
of clusters 𝐾, K-means clustering using the inverted multi-index
√ space into 𝑁𝑠 subspaces (𝑆 1, 𝑆 2, . . . , 𝑆 𝑁𝑠 ) with 𝑠 = 𝑁𝑑𝑠 dimensions,
can reduce the time complexity from O (𝐾 ·𝑛 ·𝑑 ·𝑡) to O ( 𝐾 ·𝑛 ·𝑑 ·𝑡) and divide all data points into each subspace (lines 2-3). Assume
compared to using the inverted index, 𝑡 is the number of iterations. without loss of generality that 𝑠2 is an integer. For each subspace,
based on the product quantization concept of IMI, we further divide
Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search SIGMOD ’25, June 22–27, 2025, Berlin, Germany
each 𝑠-dimensional subspace into two 𝑠2 -dimensional subspaces �����1 0.4 0.6 1.0 1.5 1.8 �����2 0.3 0.6 1.1 1.3 1.6
(lines 4-7). Although each subspace can be divided into more than
���1 0 1 2 3 4 ���2 0 1 2 3 4
two parts, both the IMI paper [9] and our experiments show that
retrieved
dividing each space into two parts achieves the best performance.
Then, for 𝑆𝑖 , we perform K-means clustering on all data points in round cluster active_idx active_dists
two 𝑠2 -dimensional subspaces (𝑆𝑖1 and 𝑆𝑖2 ) to obtain the centroids 0 none 0 0.7
of clusters 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠𝑖1, 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠𝑖2 and the data point assignments
(belongs to which cluster) 𝑎𝑠𝑠𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠𝑖1, 𝑎𝑠𝑠𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠𝑖2 (lines 8-9). 1 (0,0) 1 0 1.0 0.9
We put all the obtained centroids into a list as the first part of our 2 (1,0) 1 1 0 1.0 1.2 1.3
index (line 10). To improve query efficiency, in each subspace 𝑆𝑖 ,
we use the obtained 𝑎𝑠𝑠𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠𝑖1, 𝑎𝑠𝑠𝑖𝑔𝑛𝑚𝑒𝑛𝑡𝑠𝑖2 to construct a map 3 (0,1) 2 1 0 1.5 1.2 1.3
𝐼𝑀𝐼𝑖 as the inverted multi-index, and we put all the obtained IMIs 4 (1,1) 2 2 0 1.5 1.7 1.3
into a list as the second part of our index (lines 11-13). Finally, the
centroids and IMI lists are returned as the SuCo indexes. 5 (2,0) 2 2 1 0 1.5 1.7 1.6 1.8
The original intention of IMI is to achieve as fine-grained data
points division as possible, so 𝐾 is very large (𝐾 = 228 is used in Figure 5: An illustration of the Dynamic Activation algorithm
its paper [9]). In contrast, in the subspace collision framework, we
only need to find a large number of data points (3%-5%) in the IMI of Algorithm 3: Dynamic Activation
each
10 subspace in a coarse-grained way, so 𝐾 is much smaller (𝐾 ∈
Input: Collision ratio 𝛼, dataset size 𝑛, number of K-means
2 , 212 ). That is why SuCo’s indexing performance outperforms
clusters 𝐾, distances and indices of the first and
all competitors (shortest time and least memory footprint); the
second subspace 𝑑𝑖𝑠𝑡𝑠 1, 𝑖𝑑𝑥 1, 𝑑𝑖𝑠𝑡𝑠 2, 𝑖𝑑𝑥 2 , the
experimental results are shown in Section 5.5.
inverted multi-index 𝐼𝑀𝐼
Output: Clusters containing data points that collide with 𝑞
4.2 Query Answering 1 Initialize a list 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑_𝑐𝑙𝑢𝑠𝑡𝑒𝑟𝑠, two arrays 𝑎𝑐𝑡𝑖𝑣𝑒_𝑖𝑑𝑥
√
To support ANN search based on the subspace collision framework, and 𝑎𝑐𝑡𝑖𝑣𝑒_𝑑𝑖𝑠𝑡𝑠 of length 𝐾;
two query strategies need to design: (1) how to count collisions for 2 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑_𝑛𝑢𝑚 ← 0;
the IMI of each subspace; (2) how to combine the collisions of IMIs 3 𝑎𝑐𝑡𝑖𝑣𝑒_𝑖𝑑𝑥 [0] ← 0;
in all subspaces to obtain the final ANN result. 4 𝑎𝑐𝑡𝑖𝑣𝑒_𝑑𝑖𝑠𝑡𝑠 [0] ← 𝑑𝑖𝑠𝑡𝑠 1 [𝑖𝑑𝑥 1 [0]] + 𝑑𝑖𝑠𝑡𝑠 2 [𝑖𝑑𝑥 2 [0]];
The Multi-sequence algorithm was proposed with IMI to query 5 while TRUE do
IMI and obtain data points that are close to the query [9]. How- 6 𝑝𝑜𝑠 ← index of the minimum element in 𝑎𝑐𝑡𝑖𝑣𝑒_𝑑𝑖𝑠𝑡𝑠;
ever, the Multi-sequence algorithm uses a priority queue to hold 7 𝑐𝑙𝑢𝑠𝑡𝑒𝑟 ← 𝐼𝑀𝐼 [𝑖𝑑𝑥 1 [𝑝𝑜𝑠], 𝑖𝑑𝑥 2 [𝑎𝑐𝑡𝑖𝑣𝑒_𝑖𝑑𝑥 [𝑝𝑜𝑠]]];
the candidate clusters, For the priority queue, both insertion and 8 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑_𝑐𝑙𝑢𝑠𝑡𝑒𝑟𝑠.𝑎𝑝𝑝𝑒𝑛𝑑 (𝑐𝑙𝑢𝑠𝑡𝑒𝑟 );
popping operations require logarithmic time complexity, which 9 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑_𝑛𝑢𝑚 += 𝑠𝑖𝑧𝑒𝑜 𝑓 (𝑐𝑙𝑢𝑠𝑡𝑒𝑟 );
is time-consuming. Therefore, we design a new algorithm called
10 if 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑_𝑛𝑢𝑚 ≥ 𝛼 · 𝑛 then
Dynamic Activation to support query IMI without a priority queue.
11 break;
Dynamic Activation algorithm returns the same query results as √
Multi-sequence algorithm. The experimental results in Section 5.2 12 if 𝑎𝑐𝑡𝑖𝑣𝑒_𝑖𝑑𝑥 [𝑝𝑜𝑠] == 0 and 𝑝𝑜𝑠 < 𝐾 − 1 then
show that the efficiency of Dynamic Activation algorithm is up to 13 𝑎𝑐𝑡𝑖𝑣𝑒_𝑖𝑑𝑥 [𝑝𝑜𝑠 + 1] ← 0;
40% higher than that of the Multi-sequence algorithm. 14 𝑎𝑐𝑡𝑖𝑣𝑒_𝑑𝑖𝑠𝑡𝑠 [𝑝𝑜𝑠 + 1] ←
Algorithm 3 gives the pseudocode of the Dynamic Activation 𝑑𝑖𝑠𝑡𝑠 1 [𝑖𝑑𝑥 1 [𝑝𝑜𝑠 + 1]] + 𝑑𝑖𝑠𝑡𝑠 2 [𝑖𝑑𝑥 2 [0]];
√
algorithm. Given the distances between a query and all centroids in 15 if 𝑎𝑐𝑡𝑖𝑣𝑒_𝑖𝑑𝑥 [𝑝𝑜𝑠] < 𝐾 − 1 then
two subspaces 𝑑𝑖𝑠𝑡𝑠 1, 𝑑𝑖𝑠𝑡𝑠 2 and the indices of sorted distances in 16 𝑎𝑐𝑡𝑖𝑣𝑒_𝑖𝑑𝑥 [𝑝𝑜𝑠]++;
ascending order 𝑖𝑑𝑥 1𝑖 , 𝑖𝑑𝑥 2𝑖 , we need to select one cluster from each 17 𝑎𝑐𝑡𝑖𝑣𝑒_𝑑𝑖𝑠𝑡𝑠 [𝑝𝑜𝑠] ←
subspace to form a cluster in 𝐼𝑀𝐼 . The sum of their distances (one 𝑑𝑖𝑠𝑡𝑠 1 [𝑖𝑑𝑥 1 [𝑝𝑜𝑠]] + 𝑑𝑖𝑠𝑡𝑠 2 [𝑖𝑑𝑥 2 [𝑎𝑐𝑡𝑖𝑣𝑒_𝑖𝑑𝑥 [𝑝𝑜𝑠]]];
from 𝑑𝑖𝑠𝑡𝑠 1 , the other from 𝑑𝑖𝑠𝑡𝑠 2 ) is used as the selection criterion.
The smaller the distance sum of clusters in 𝐼𝑀𝐼 , the earlier they 18 return 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑_𝑐𝑙𝑢𝑠𝑡𝑒𝑟𝑠;
are retrieved. We first activate a cluster in the first subspace, which
has the minimum distance in 𝑑𝑖𝑠𝑡𝑠 1 (lines 3-4). Activated clusters
can be combined with clusters from the second subspace, and the Figure 5 gives a running example of Algorithm 3. Algorithm 3
two clusters with the minimum sum of distances will be combined runs in a multi-round way, and in each round, it retrieves a cluster
as a retrieved cluster in 𝐼𝑀𝐼 (lines 6-9). When the number of data whose sum of 𝑑𝑖𝑠𝑡𝑠 1 (among the activated indices) and 𝑑𝑖𝑠𝑡𝑠 2 is
points in all retrieved clusters reaches the collision requirement minimal. In the initialization round (round 0), the index 0 of 𝑑𝑖𝑠𝑡𝑠 1
(lines 10-11), the algorithm stops and returns the retrieved clusters is activated (with initial value 0). In round 1, since only index 0
(line 18). Otherwise, we dynamically activate the clusters in the of 𝑑𝑖𝑠𝑡𝑠 1 is activated, the cluster with the joint index of 𝑑𝑖𝑠𝑡𝑠 1 and
first subspace in ascending order of 𝑑𝑖𝑠𝑡𝑠 1 (lines 12-14) and update 𝑑𝑖𝑠𝑡𝑠 2 (0, 0) is retrieved, and its distance to the query is 0.7. Then,
the combination information of the activated clusters (lines 15-17). we activate index 1 of 𝑑𝑖𝑠𝑡𝑠 1 (with initial value 0) and increase the
SIGMOD ’25, June 22–27, 2025, Berlin, Germany Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng
Algorithm 4: 𝑘-ANN Query Table 3: Summary of datasets
Input: A dataset D, dataset size 𝑛, dimensionality of data
points 𝑑, a query point 𝑞, number of results 𝑘, Dataset Cardinality Dimensions LID
subspace number 𝑁𝑠 , collision ratio 𝛼, re-rank ratio Deep1M 1,000,000 256 37.26
𝛽, number of K-means clusters 𝐾, the centroid list Gist1M 1,000,000 960 70.15
𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠, the IMI list 𝐼𝑀𝐼𝑠 Sift10M 10,000,000 128 22.05
Output: 𝑘 nearest points to 𝑞 in D Microsoft SPACEV10M 10,000,000 100 41.72
1 Initialize an array 𝑆𝐶_𝑠𝑐𝑜𝑟𝑒𝑠 of length 𝑛 and set to 0;
Yandex Deep10M 10,000,000 96 29.10
1
2 Divide 𝑞 into 𝑁𝑠 subspaces: 𝑞 , . . . , 𝑞 𝑠 ;
𝑁
TinyImages80M 79.302,017 384 61.75
3 for 𝑖 = 1 to 𝑁𝑠 do Sift100M 100,000,000 128 23.79
4 Divide 𝑞𝑖 into two subspaces 𝑞𝑖1 and 𝑞𝑖2 ; Yandex Deep100M 100,000,000 96 29.61
5 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠 1 ← 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠 [2(𝑖 − 1)];
6 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠 2 ← 𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠 [2(𝑖 − 1) + 1];
7 Calculate the distance between each centroid in
𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠 1 (𝑐𝑒𝑛𝑡𝑟𝑜𝑖𝑑𝑠 2 ) and 𝑞𝑖1 (𝑞𝑖2 ), obtain 𝑑𝑖𝑠𝑡𝑠 1𝑖 (𝑑𝑖𝑠𝑡𝑠 2𝑖 );
8 Obtain the indices of sorted 𝑑𝑖𝑠𝑡𝑠 1𝑖 (𝑑𝑖𝑠𝑡𝑠 2𝑖 ) in ascending
order: 𝑖𝑑𝑥 1𝑖 (𝑖𝑑𝑥 2𝑖 );
9 𝑐𝑙𝑢𝑠𝑡𝑒𝑟𝑠 ← call DynamicActivation
4.3 Complexity Analysis
(𝛼, 𝑛, 𝐾, 𝑑𝑖𝑠𝑡𝑠 1𝑖 , 𝑖𝑑𝑥 1𝑖 , 𝑑𝑖𝑠𝑡𝑠 2𝑖 , 𝑖𝑑𝑥 2𝑖 , 𝐼𝑀𝐼𝑠 [𝑖 − 1]); √
10 for each 𝑐𝑙𝑢𝑠𝑡𝑒𝑟 ∈ 𝑐𝑙𝑢𝑠𝑡𝑒𝑟𝑠 do For index construction,
√ SuCo has time cost O (𝑛( 𝐾𝑑𝑡 + 𝑁𝑠 )) and
11 for each 𝑝𝑜𝑖𝑛𝑡_𝑖𝑑 ∈ 𝑐𝑙𝑢𝑠𝑡𝑒𝑟 do space cost O ( 𝐾𝑑 + 𝑛𝑁𝑠 ). The time cost comes from three parts:
12 𝑆𝐶_𝑠𝑐𝑜𝑟𝑒𝑠 [𝑝𝑜𝑖𝑛𝑡_𝑖𝑑]++; (1) divide all data points into 𝑁𝑠 subspaces, O (𝑛𝑑); (2) use the
K-means algorithm√to cluster all data points within two parts of
13 Sort 𝑆𝐶_𝑠𝑐𝑜𝑟𝑒𝑠 in descending order; each subspace, O ( 𝐾𝑛𝑑𝑡); (3) build a map as the inverted multi-
14 for 𝑧 = 1 to 𝛽 · 𝑛 do index in√each subspace, O (𝑛𝑁𝑠 ). Therefore, the total time cost
15 Select the point with the 𝑧-th-largest SC-score in is O (𝑛( 𝐾𝑑𝑡 + 𝑁𝑠 )). The space cost comes from two √ parts: (1)
𝑆𝐶_𝑠𝑐𝑜𝑟𝑒𝑠 whose index in D is 𝑡; centroids obtained by clustering in each subspace, O ( 𝐾𝑑); (2)
16 Calculate the Euclidean distance between 𝑜𝑡 and 𝑞; the inverted multi-indexes constructed √ in each subspace, O (𝑛𝑁𝑠 ).
Therefore, the total space cost is O ( 𝐾𝑑 + 𝑛𝑁𝑠 ).
17 return the top-𝑘 points closest to 𝑞 in the 𝛽 · 𝑛 candidates;
√ For query√ answering,
√ SuCo has time cost O (𝑛(𝛼𝑁𝑠 +𝛽𝑑+log(𝛽𝑛))+
𝐾 (𝑑 + 𝛼 𝐾 log 𝐾)). The time cost comes from seven parts: (1)
calculate the distance
√ between all centroids and the query point in
value of index 0 to 1. In round 2, two indices of 𝑑𝑖𝑠𝑡𝑠 1 have been each subspace, O ( 𝐾𝑑); (2) obtain the indices of sorted distances
activated (0 and 1), and we retrieve the cluster with the joint index √ √
in ascending order in each subspace, O ( 𝐾 log 𝐾); (3) invoke the
(1, 0) because it has a smaller distance (0.9) than the cluster with the Dynamic Activation algorithm to obtain clusters containing √ data
joint index (0, 1). Then, we activate index 2 of 𝑑𝑖𝑠𝑡𝑠 1 (with initial
points that collide with the query in each subspace, O (𝛼𝐾 log 𝐾);
value 0) and increase the value of index 1 to 1. In round 3, three
(4) count collisions for all data points in each subspace, O (𝛼𝑛𝑁𝑠 ); (5)
indices of 𝑑𝑖𝑠𝑡𝑠 1 have been activated (0, 1, and 2), and we retrieve
partial sort and select candidates with large SC-score, O (𝑛 log(𝛽𝑛));
the cluster with the joint index (0, 1) because it has a minimum
(6) calculate the distance between all candidates and the query,
distance of 1.0. It should be noted that no new index of 𝑑𝑖𝑠𝑡𝑠 1 is
O (𝛽𝑛𝑑); (7) partial sort and return the top-𝑘 points closest to the
activated in this round, because for the retrieved cluster, the value
query among candidates, O (𝛽𝑛√log 𝑘). Therefore,
√ √the total time cost
of the activated index is not 0 but 1. The operations for subsequent
is O (𝑛(𝛼𝑁𝑠 + 𝛽𝑑 + log(𝛽𝑛)) + 𝐾 (𝑑 + 𝛼 𝐾 log 𝐾)).
rounds are the same as the previous rounds.
Algorithm 3 supports collision counting for the IMI of each
subspace. We further design Algorithm 4 to combine the collisions
of IMIs in all subspaces and support 𝑘-ANN queries, and Figure 3(b) 5 EXPERIMENTAL EVALUATION
shows the workflow of SuCo to answer 𝑘-ANN queries. First, we In this section, we first compare the performance of the Dynamic
initialize an array to record the SC-score of all data points and Activation algorithm we designed for IMI with the original Multi-
divide the query 𝑞 into 𝑁𝑠 subspaces (lines 1-2). For each subspace, sequence algorithm. Then, we study the performance of SuCo by
we calculate the distance between the query and all centroids in the self-evaluating and conducting comparative experiments with state-
two divided parts and then obtain the indices of sorted distances of-the-art ANN methods (with and without theoretical guarantees).
in ascending order (lines 3-8). Then, we call Algorithm 3 to obtain All methods are implemented in C/C++. SuCo is implemented in
clusters containing data points that collide with 𝑞 in each subspace C++ and compiled using -O3 optimization, useing OpenMP for
and count collisions for all data points (lines 9-12). Finally, we re- parallelization and SIMD for accelerating calculations [102]. All
rank the 𝛽 · 𝑛 data points with the largest SC-scores and return the experiments are conducted on a machine with 2 AMD EPYC 9554
top-𝑘 points closest to 𝑞 among them (lines 13-17). CPUs @ 3.10GHz and 756 GB RAM, running on Ubuntu 22.04.
Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search SIGMOD ’25, June 22–27, 2025, Berlin, Germany
' \ Q D P L F $ F W L Y D W L R Q $ O J R U L W K P 0 X O W L V H T X H Q F H $ O J R U L W K P Table 4: Comparison on SuCo and SC-Linear
4 X H U \ W L P H P V
4 X H U \ W L P H P V
Method Dataset Query Time (ms) Speedup Recall
Sift10M 3104.42 \ 0.968
SC-Linear
Sift100M 71644.5 \ 0.9942
Sift10M 5.139 604.1 0.9346
SuCo
162 242 322 482 642 Sift100M 68.835 1040.8 0.9822
K
D G L I I H U H Q W K E G L I I H U H Q W
Figure 6: Comparison of query efficiency between Dynamic For SuCo, 𝐾 = 502 , 𝑁𝑠 = 8. For query parameters, we dynamically
Activation and Multi-sequence algorithm on Sift10M. adjust their settings to observe the trade-off between query effi-
ciency and accuracy (as shown in Figure 11 and Figure 12). For
DET-LSH, DB-LSH, and PM-LSH, 𝛽 ∈ [0.005, 0.2],
𝑐 = 1.5.
For
LCCS-LSH, 𝑐ℎ𝑒𝑐𝑘_𝑘 ∈ 28, 218 . For OPQ, 𝛽 ∈ 10 −4, 10 −1 . For
5.1 Experimental Setup
Datasets and Queries. We use eight real-world datasets for ANN Annoy, 𝑠𝑒𝑎𝑟𝑐ℎ_𝑘 ∈ 103, 105 . For HNSW, 𝑒 𝑓 𝑆𝑒𝑎𝑟𝑐ℎ ∈ [300, 3000].
search, whose key statistics are shown in Table 3. LID1 is the local in- For SPTAG, we use the balanced K-means tree (BKT). For SuCo,
trinsic dimensionality and a larger LID implies harder dataset. Note 𝛼 ∈ [0.01, 0.1], 𝛽 ∈ [0.001, 0.05]. 𝑘 in 𝑘-ANN is set to 50.
that the points in Sift10M and Sift100M are randomly chosen from
the Sift1B dataset2 . Similarly, the points in Microsoft SPACEV10M, 5.2 Dynamic Activation vs. Multi-sequence
Yandex Deep10M, and Yandex Deep100M are also randomly chosen As introduced in Section 4.2, we design a new query strategy (Al-
from their 1B-scale datasets3 . We randomly select 100 data points gorithm 3) to support efficient querying of IMI. Figure 6 compares
as queries and remove them from the original datasets. the query efficiency between Dynamic Activation algorithm (we
Evaluation Measures. We adopt six measures to evaluate the designed) and Multi-sequence algorithm (proposed with IMI [9]).
performance of all methods: indexing time, index memory footprint, While achieving the same query accuracy (they return the same
query time, query per second (QPS), recall, and mean relative error query results), the efficiency of Dynamic Activation algorithm is
(MRE) [5, 77, 78], where the indexing time, query time, and QPS up to 40% higher than that of the Multi-sequence algorithm. The
evaluate the efficiency of methods, the index memory footprint advantage of Dynamic Activation algorithm increases as the query
evaluates the storage resource consumption of methods, and the workload increases (larger 𝐾 and 𝛼). The reason is that the Multi-
recall and MRE evaluate the quality of returned results. For a query sequence algorithm relies on a priority queue to hold the candidate
𝑞, if the returned result set is 𝑅 = {𝑜 1, . . . , 𝑜𝑘 } and the exact 𝑘- clusters, and frequent insertion and popping operations are time-
|𝑅∩𝑅 ∗ |
NN set is 𝑅 ∗ = {𝑜 1∗, . . . , 𝑜𝑘∗ }, recall is defined as 𝑘 , and mean consuming. Dynamic Activation algorithm updates and maintains
∥𝑞,𝑜𝑖 ∥ − ∥𝑞,𝑜𝑖∗ ∥ the activation list through activation strategies, eliminating the
relative error (MRE) is defined as 𝑘1 𝑘𝑖=1
Í
.
∥𝑞,𝑜𝑖∗ ∥ reliance on the priority queue and improving query efficiency.
Benchmark Methods. We compare SuCo with seven state-of-
the-art in-memory ANN methods. DET-LSH [104], DB-LSH [91], 5.3 Self-evaluation of SuCo
PM-LSH [111], and LCCS-LSH [52] are the state-of-the-art LSH- 5.3.1 SuCo vs. SC-Linear. Preliminary experiments in Section 3.3
based methods that provide theoretical guarantees. They are single- have demonstrated that the subspace collision framework is effec-
threaded because the authors did not design parallel methods. tive, and Table 2 shows that SC-Linear (has no index) can return
OPQ [38], Annoy [14], HNSW [67], and SPTAG [23] are the state-of- high-quality query results. In this section, we further compare the
the-art VQ-based, tree-based, graph-based, and tree-graph hybrid query performance between SuCo and SC-Linear under the same
methods, respectively, which do not provide theoretical guarantees. parameter settings: 𝛼 = 0.03, 𝛽 = 0.003. As shown in Table 4, com-
They use OpenMP and/or Pthreads for parallelization, and SIMD pared with SC-Linear, the query efficiency of SuCo is significantly
for accelerating calculations. improved (up to 1000 times), with an acceptable sacrifice of query
Parameter Settings. Both the indexing and query answering accuracy. The results demonstrate that the index structure and
phases of ANN methods require parameter settings. To select in- query strategy we designed for SuCo can be well applied to the
dexing parameters, we refer to the optimal parameters given in subspace collision framework for ANN search.
previous papers [31, 54, 104] and conduct our own experiments
to verify their rationality so that all methods can achieve the best 5.3.2 Parameter study on 𝐾 and 𝑁𝑠 . Parameters 𝐾 and 𝑁𝑠 deter-
indexing performance. For DET-LSH, 𝐿 = 4, 𝐾 = 16. For DB-LSH, mine the efficiency and space consumption of index construction
𝐿 = 5, 𝐾 = 12. For PM-LSH, 𝑠 = 5, 𝑚 = 15. For LCCS-LSH, 𝑚 = 64. and affect the efficiency and accuracy of queries. We evaluate the
For OPQ, 𝑀 = 2, 𝐾 = 220 (number of cells after Cartesian product). impactof 𝐾 and 𝑁𝑠 on the performance of SuCo by setting 𝐾 in the
For Annoy, 𝑓 = 30. For HNSW, 𝑒 𝑓 𝐶𝑜𝑛𝑠𝑡𝑟𝑢𝑐𝑡𝑖𝑜𝑛 = 200, 𝑀 = 25. range 28, 216 and 𝑁𝑠 in the range [6, 16]. As shown in Figure 7
(a) and (b), the indexing time and query time increase gradually
1 There is no unified method to estimate the LID, and we use an open-source toolkit [12]
with 𝐾 increasing from 28 to 212 but significantly with 𝐾 increasing
with theoretical basis [47] to calculate it for each dataset.
2 [Link] from 212 to 216 . In contrast, the recall increase significantly with
3 [Link] 𝐾 increasing from 28 to 212 but gradually with 𝐾 increasing from
SIGMOD ’25, June 22–27, 2025, Berlin, Germany Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng
4 X H U \ 7 L P H 5 H F D O O , Q G H [ L Q J W L P H 0 H P R U \ I R R W S U L Q W
0 H P I R R W S U L Q W * %
0 H P I R R W S U L Q W * %
, Q G H [ L Q J W L P H V
, Q G H [ L Q J W L P H V
4 X H U \ W L P H P V
4 X H U \ W L P H P V
5 H F D O O
5 H F D O O
28 210 212 214 216 28 210 212 214 216
K K Ns Ns
D 4 X H U \ S H U I R U P D Q F H E , Q G H [ L Q J S H U I R U P D Q F H F 4 X H U \ S H U I R U P D Q F H G , Q G H [ L Q J S H U I R U P D Q F H
R Q < D Q G H [ ' H H S 0 R Q < D Q G H [ ' H H S 0 R Q 6 L I W 0 R Q 6 L I W 0
Figure 7: Performance of SuCo when varying the number of K-means clusters 𝐾 and the number of subspaces 𝑁𝑠 .
4 X H U \ 7 L P H 5 H F D O O
4 X H U \ W L P H P V
4 X H U \ W L P H P V
4 X H U \ W L P H P V
4 X H U \ W L P H P V
5 H F D O O
5 H F D O O
5 H F D O O
5 H F D O O
H H
D < D Q G H [ ' H H S 0 E 6 L I W 0 F < D Q G H [ ' H H S 0 G 6 L I W 0
Figure 8: Query performance of SuCo when varying the collision ratio 𝛼 and the re-rank ratio 𝛽.
Table 5: SuCo under different distance measures 6 X & R ' ( 7 / 6 + 3 0 / 6 +
6 X & R 6 L Q J O H F R U H ' % / 6 + / & & 6 / 6 +
) R R W S U L Q W 0 %
7 L P H V
Gist Sift SPACEV Yandex Deep
1M 10M 10M 100M
Recall 0.9328 0.9868 0.966 0.9906
SuCo-L1
MRE 0.00099 0.00039 0.00103 0.0002 ' H H S 6 L I W 7 L Q \ 6 L I W ' H H S 6 L I W 7 L Q \ 6 L I W
0 0 0 0 0 0 0 0
SuCo-L2
Recall
MRE
0.9508
0.00068
0.9862
0.00042
0.9802
0.00035
0.9988
0.00002
D , Q G H [ L Q J W L P H E , Q G H [ P H P R U \ I R R W S U L Q W
Figure 9: Indexing performance comparison between SuCo
and competitors that provide theoretical guarantees.
212 to 216 . The index memory footprint remains rather stable in
the whole range. Therefore, we choose 𝐾 = 502 ∈ (210, 212 ) as the
default value. As shown in Figure 7 (c) and (d), the indexing time,
index memory footprint, and query time continue to increase as
𝑁𝑠 increases. The recall remains rather stable when 𝑁𝑠 is larger
𝛼 and 𝛽 on large-scale datasets. On the Sift100M dataset, the recall
than 8. Considering these two factors, we choose 𝑁𝑠 = 8 as the
of SuCo is 0.9822 when 𝛼 = 0.03, 𝛽 = 0.003. This demonstrates
default value. Based on our experiments with datasets of different
that SuCo has good scalability on large-scale datasets. Based on
dimensionality and size, we suggest choosing 𝑁𝑠 ∈ [6, 12] for new
our experiments with datasets of different dimensionality and size,
datasets, which is a good balance between indexing cost and query
we suggest choosing 𝛼 ∈ [0.03, 0.1] and 𝛽 ∈ [0.003, 0.005] for new
accuracy.
datasets, which is a good balance between query efficiency and
5.3.3 Parameter study on 𝛼 and 𝛽. Parameters 𝛼 and 𝛽 have a great accuracy. In addition, large-scale datasets tend to use smaller 𝛼 and
impact on query efficiency and accuracy. We evaluate the impact of 𝛽, and hard datasets tend to use larger 𝛽.
𝛼 and 𝛽 on the query performance of SuCo by setting 𝛼 in the range
[0.01, 0.2] and 𝛽 in the range [0.001, 0.009]. As shown in Figure 8 5.3.4 SuCo under different distance measures. In this paper, we
(a) and (b), the query time continues to increase as 𝛼 increases, but focus on the L2 distance (Euclidean distance), which is the most
the recall is rather stable when 𝛼 is larger than 0.05. As shown widely used distance measure. It is interesting to examine if SuCo
in Figure 8 (c) and (d), the query time continues to increase as 𝛽 can be used with other distance measures. Table 5 reports the
increases, but the recall increases slowly when 𝛽 is larger than performance of SuCo using the L1 (Manhattan distance) and L2
0.005. Therefore, 𝛼 = 0.05, 𝛽 = 0.005 is a good choice for SuCo. In distance measures on four datasets under the same setting. We
addition, we found that SuCo can achieve a high recall with smaller observe that SuCo achieves high query accuracy with L1, too.
Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search SIGMOD ’25, June 22–27, 2025, Berlin, Germany
Table 6: The time and space complexity of the state-of-the-art methods (for notation, see Section 5.7)
SuCo DET-LSH OPQ Annoy SPTAG HNSW
√ √
Indexing time O (𝑛( 𝐾𝑑𝑡 + 𝑁𝑠 )) O (𝐿𝐾𝑛(𝑑 + log 𝑁𝑟 )) O (𝑛( 𝐾 + 𝑘 ∗ )𝑑𝑡)√ O (𝐿𝑛𝑑 log 𝑛) O (𝑛𝑑 log 𝑛) O (𝑛𝑑 log 𝑛)
√ O (𝑛(𝑚 √log 𝑘 ∗ + log 𝐾)
Index space O ( 𝐾𝑑 + 𝑛𝑁𝑠 ) O (𝐿𝐾𝑛) O (𝐿𝑑𝑛) O (𝑛(𝑑 + 𝐸)) O (𝑛𝐸)
+( 𝐾 + 𝑘 ∗ )𝑑)
O (𝑛(𝛼𝑁
√ 𝑠 + 𝛽𝑑
√ + log(𝛽𝑛))
√ O (𝑛(𝛾𝑚
√ + 𝛽𝑑) O (𝐿𝑑 log 𝑛
Query time O (𝑛(𝛽𝑑 + 𝐿𝐾 log 𝑁𝑟 )) O (𝑑 log 𝑛) O (𝑑 log 𝑛)
+ 𝐾 (𝑑 + 𝛼 𝐾 log 𝐾)) +( 𝐾 + 𝑘 ∗ )𝑑) +𝛽𝑛𝑑)
6 X & R 2 3 4 $ Q Q R \ 6 3 7 $ * + 1 6 :
5.5 SuCo vs. Competitors without Guarantees
) R R W S U L Q W 0 %
5.5.1 Indexing performance. Figure 10 shows the indexing time
7 L P H V
and index memory footprint of SuCo and competitors that do not
provide theoretical guarantees. We found that SuCo has the best
indexing efficiency and the least index memory footprint. Since
' H H S 6 L I W 7 L Q \ 6 L I W ' H H S 6 L I W 7 L Q \ 6 L I W
SuCo only needs to find many (about 3%-5%) but not necessarily
0 0 0 0 0 0 0 0 accurate data points as collisions, the index structure does not need
D , Q G H [ L Q J W L P H E , Q G H [ P H P R U \ I R R W S U L Q W to divide the data points very finely. To construct the IMI√of each
subspace, we only need to perform K-means clustering of 𝐾 = 50
Figure 10: Indexing performance comparison between SuCo
twice, which makes SuCo highly efficient for indexing. However, the
and competitors that do not provide theoretical guarantees.
tree structure partitions data points in a fine-grained manner, while
the graph structure connects each data point to its sufficiently close
neighbor points, which makes the index heavyweight and requires
5.4 SuCo vs. Competitors with Guarantees longer indexing time and larger memory space (Annoy, SPTAG,
5.4.1 Indexing performance. Figure 9 shows the indexing time and and HNSW). Although OPQ also uses IMI as the index structure,
index memory footprint of all methods that provide theoretical its query strategy requires IMI to be able to divide data points very
guarantees. We found that SuCo and single-threaded SuCo have finely (different from our subspace collision framework),
√ so the
the least index memory footprint. Since SuCo’s clustering-based 𝐾 of K-means clustering needs to be very large ( 𝐾 = 210 − 214 ),
index structure is lightweight and only the cluster centroids and which seriously restricts the indexing efficiency of OPQ.
data point assignments need to be recorded, the required memory
space is small. In addition, SuCo has the best indexing efficiency,
while single-threaded SuCo is (naturally) slower, with the extra
cost coming from the (now serial) subspace clustering step. In prac-
tice, parallel indexing methods are used in the modern multi-core 5.5.2 Query performance. Figure 12 gives the recall-QPS curves of
systems to speed up index construction, so SuCo has an advantage SuCo and competitors that do not provide theoretical guarantees.
in indexing efficiency compared to other methods with theoretical We found that SuCo and HNSW outperform other methods, and
guarantees. LSH-based methods need to build one (PM-LSH) or on the hard datasets (Gist1M, SPACEV10M), SuCo performs better,
multiple (DET-LSH, DB-LSH) index trees or circular shift array while on the easy datasets (Deep1M, Sift10M), HNSW performs
(LCCS-LSH), which are heavy-weight index structures, requiring better. Graph-based methods (such as HNSW) sacrifice indexing
more time to construct the index, and occupying more memory. time and space consumption in exchange for higher query efficiency
because they need to identify the near neighbors for each data point
5.4.2 Query performance. For all methods, there is a trade-off be- in the dataset (and connect to them) during the indexing phase,
tween query efficiency and accuracy. Figure 11 gives the recall- while in the query phase, they only need to search on a gradually
QPS and MRE-QPS curves of all methods that have theoretical converging path. However, on the hard datasets, HNSW’s greedy
guarantees. We found that the query performance of SuCo and query strategy is prone to falling into local optimal subgraphs and
single-threaded SuCo is 1-2 orders of magnitude better than that is difficult to escape. In addition, HNSW requires few and accurate
of LSH-based methods. Benefiting from the design of the subspace query results directly from the index, so its query strategy has
collision framework, index structure, and query strategy, SuCo low fault tolerance. On the contrary, SuCo only needs to find many
can efficiently count collisions to obtain candidate points and then (about 3%-5%) but not necessarily accurate data points from its index
ensure the high quality of query results through a re-ranking mech- as collisions, so its query strategy is highly fault-tolerant and more
anism. SuCo only needs to retrieve 0.3%-0.5% of candidate points to suitable for hard datasets. It is important to emphasize that SuCo
achieve a high recall, indicating that the obtained candidate points has to pay the cost of providing guarantees for its answers; other
are of high quality. However, DET-LSH, DB-LSH, and PM-LSH need competitors, that do not provide any guarantees, do not pay this
to obtain more candidate points (up to 10%) and spend more time cost. Even with this cost, SuCo achieves top performance (best for
to achieve the same recall because the LSH projection loses the hard datasets) when compared to competitors that do not provide
distance information between data points. theoretical guarantees.
SIGMOD ’25, June 22–27, 2025, Berlin, Germany Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng
6 X & R 6 X & R 6 L Q J O H F R U H ' ( 7 / 6 + ' % / 6 + 3 0 / 6 + / & & 6 / 6 +
4 X H U L H V S H U V H F R Q G
4 X H U L H V S H U V H F R Q G
4 X H U L H V S H U V H F R Q G
4 X H U L H V S H U V H F R Q G
5 H F D O O 0 H D Q U H O D W L Y H H U U R U 5 H F D O O 0 H D Q U H O D W L Y H H U U R U
D 5 H F D O O 4 3 6 R Q ' H H S 0 E 0 5 ( 4 3 6 R Q ' H H S 0 F 5 H F D O O 4 3 6 R Q 6 L I W 0 G 0 5 ( 4 3 6 R Q 6 L I W 0
Figure 11: Query performance comparison between SuCo and competitors that provide theoretical guarantees.
6 X & R 2 3 4 $ Q Q R \ 6 3 7 $ * + 1 6 :
4 X H U L H V S H U V H F R Q G
4 X H U L H V S H U V H F R Q G
4 X H U L H V S H U V H F R Q G
4 X H U L H V S H U V H F R Q G
5 H F D O O 5 H F D O O 5 H F D O O 5 H F D O O
D * L V W 0 K D U G G D W D V H W E ' H H S 0 H D V \ G D W D V H W F 6 3 $ & ( 9 0 K D U G G D W D V H W G 6 L I W 0 H D V \ G D W D V H W
Figure 12: Query performance comparison between SuCo and competitors that do not provide theoretical guarantees.
6 X & R ' ( 7 / 6 + 2 3 4 $ Q Q R \ 6 3 7 $ * + 1 6 :
& X P X O D W L Y H F R V W V
& X P X O D W L Y H F R V W V
& X P X O D W L Y H F R V W V
& X P X O D W L Y H F R V W V
. . . . . . . . . . . . . . . .
4 X H U L H V 4 X H U L H V 4 X H U L H V 4 X H U L H V
D 7 L Q \ 0 5 H F D O O E 7 L Q \ 0 5 H F D O O F 6 L I W 0 5 H F D O O G 6 L I W 0 5 H F D O O
Figure 13: Cumulative query cost (start with the indexing time); comparison to methods with/without guarantees.
6 X & R 6 & / 6 + 6 & 3 & $
5 H F D O O
5 H F D O O
5 H F D O O
5 H F D O O
Ns ' L P R I H D F K V X E V S D F H H
D ' L I I H U H Q W V X E V S D F H Q X P E H U E ' L I I H U H Q W V X E V S D F H G L P H Q V L R Q D O L W \ F ' L I I H U H Q W G ' L I I H U H Q W
Figure 14: Query performance of SC-based methods with different data preprocessing techniques on Sift10M.
5.6 Overall Evaluation guarantees (e.g., DET-LSH), SuCo always has a considerable per-
We now evaluate the cumulative indexing and query time cost formance advantage, ranging between 1 and more than 2 orders of
of methods with theoretical guarantees (SuCo and DET-LSH) and magnitude. Even when compared with methods that do not provide
without (OPQ, Annoy, SPTAG, and HNSW). Figure 13 shows the theoretical guarantees (OPQ, Annoy, SPTAG, and HNSW), SuCo
cumulative query costs of all methods, where the cost starts with also has an advantage: it creates the index and answers 40K-80K
the indexing time. Compared with methods that provide theoretical queries before the best competitor (i.e., HNSW) answers its first
query. Note that SuCo performs better on hard datasets: compared
Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search SIGMOD ’25, June 22–27, 2025, Berlin, Germany
with the Sift100M (easy) dataset, SuCo answers more queries on 6 CONCLUSIONS
the Tiny80M (hard) dataset before HNSW answers its first query. In this paper, we first designed SC-score, a metric that follows
the “Pareto principle” and can act as a proxy for the Euclidean
distance between data points. Next, we proposed a novel ANN
search framework called subspace collision, which can achieve high
5.7 Complexity Comparison and Analysis
recall and provide theoretical guarantees on the quality of its results.
Since the index structures and query strategies of the state-of-the- Then, we proposed SuCo, which achieves efficient and accurate
art methods are different (refer to Table 6), it is hard to make a ANN search by designing a clustering-based lightweight index and
direct comparison among them. In our analysis, we will focus on query strategies for the subspace collision framework. Finally, we
the main parts that affect the complexity of each method (ignoring conducted extensive experiments, and the results demonstrate the
secondary terms marked in gray in Table 6, which are not at the superiority of SuCo in indexing and query answering performance.
same complexity level as the main items, e.g., O (log 𝑛) and O (𝑛)) In future work, we will combine deep learning to explore more
and conduct a comparative analysis based on these parts. For all efficient index structures under the subspace collision framework.
methods, 𝑛, 𝑑, 𝛽, 𝑡 have the same meanings as defined in this paper.
In terms of indexing time, Annoy (𝐿 is the number of trees),
ACKNOWLEDGMENTS
HNSW, and SPTAG need more than O (𝑛 log 𝑛) complexity, which
is time-consuming. Although OPQ has the same complexity level X. Lee and B. Peng partially supported by National Natural Sci-
O (𝑛) as SuCo and DET-LSH (𝐿 and 𝐾 are the number and dimen- ence Foundation of China (62202450) and FUXI Institution-CASICT
sionality of projected spaces, and 𝑁𝑟 is the number of regions in Interenet Infrastructure Laboratory (E051570). Z. Liao partially
each projected space), it requires two layers of clustering for quan- supported by National Natural Science Foundation of China (NSFC-
tization (the number of centroids is 𝐾 and 𝑘 ∗ , respectively), so it 62206101, NSFC-12141107), and Guangdong Provincial Key Lab-
takes a long time to build the index. Therefore, SuCo and DET-LSH oratory of Mathematical Foundations for Artificial Intelligence
are suitable for scenarios sensitive to indexing time. In terms of (2023B1212010001). T. Palpanas partially supported by EU Horizon
index space, SuCo and OPQ are cluster-based indexes, and their projects AI4Europe (101070000), TwinODIS (101160009), ARMADA
complexity coefficients 𝑁𝑠 , 𝑚 (the number of subvectors), and 𝑘 ∗ (101168951), DataGEMS (101188416) and RECITALS (101168490).
are relatively small. The tree-based indexes (DET-LSH, Annoy),
graph-based index (HNSW), and hybrid index (SPTAG) have larger REFERENCES
complexity coefficients, i.e., the number of trees (𝐿) and the number [1] 2003. Bounds and Approximations for Moments of Order Statistics. In Order
Statistics. John Wiley & Sons, Ltd, Chapter 4, 59–93. [Link]
of neighbors for each vertex in the graph (𝐸). Therefore, SuCo and 0471722162.ch4
OPQ are suitable for scenarios with limited index space. In terms [2] 2003. Expected Values and Moments. In Order Statistics. John Wiley & Sons,
of query time, HNSW and SPTAG have O (log 𝑛) complexity, while Ltd, Chapter 3, 33–58. [Link]
[3] Alexandr Andoni. 2005. LSH Algorithm and Implementation (E2LSH). https:
other methods rely on re-ranking, with a complexity of O (𝛽𝑛𝑑). //[Link]/andoni/www/LSH/[Link].
Since the subspace collision framework can effectively select candi- [4] Alexandr Andoni and Ilya Razenshteyn. 2015. Optimal data-dependent hashing
date points, SuCo has a smaller re-rank ratio 𝛽 than DET-LSH, OPQ for approximate near neighbors. In Proceedings of the forty-seventh annual ACM
symposium on Theory of computing. 793–801.
(𝛾 is the candidate pool ratio), and Annoy. Therefore, HNSW, SuCo, [5] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN-
and SPTAG are suitable for scenarios sensitive to query time, as Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms.
Information Systems 87 (2020), 101374.
validated by the experimental results in Section 5.4 and Section 5.5. [6] Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2023. ELPIS: Graph-Based
Similarity Search for Scalable Data Science. Proceedings of the VLDB Endowment
16, 6 (2023), 1548–1559.
[7] Ilias Azizi, Karima Echihabi, and Themis Palpanas. 2025. Graph-Based Vector
Search: An Experimental Evaluation of the State-of-the-Art. PACMMOD (2025).
5.8 Impact of Data Preprocessing Techniques [8] Artem Babenko and Victor Lempitsky. 2014. Additive quantization for extreme
Our proposed subspace collision framework consists of two ideas: vector compression. In Proceedings of the IEEE Conference on Computer Vision
and Pattern Recognition. 931–938.
(1) use a simple division strategy to preprocess the raw data into [9] Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. IEEE
subspaces and (2) use 𝛼 and 𝛽 to generate a pool of NN candidates transactions on pattern analysis and machine intelligence 37, 6 (2014), 1247–1260.
[10] Artem Babenko and Victor Lempitsky. 2015. Tree quantization for large-scale
and then pick the best NNs from that pool. We explored the effects similarity search and classification. In Proceedings of the IEEE Conference on
of combining different data preprocessing techniques (LSH for pro- Computer Vision and Pattern Recognition. 4240–4248.
jection, Principal Component Analysis (PCA) for dimensionality [11] Artem Babenko and Victor Lempitsky. 2016. Efficient indexing of billion-scale
datasets of deep descriptors. In Proceedings of the IEEE Conference on Computer
reduction, and our simple division) with the subspace collision Vision and Pattern Recognition. 2055–2063.
framework, as shown in Figure 14. Figure 14 (a) and Figure 14 (b) [12] Jonathan Bac, Evgeny M Mirkes, Alexander N Gorban, Ivan Tyukin, and Andrei
show that SuCo outperforms SC-LSH and SC-PCA in query ac- Zinovyev. 2021. Scikit-dimension: a python package for intrinsic dimension
estimation. Entropy 23, 10 (2021), 1368.
curacy under different subspace settings. In addition, SuCo’s data [13] Jenny A. Baglivo. 2005. Mathematica Laboratories for Mathematical Statistics.
preprocessing speed is 4x and 12x faster than SC-LSH and SC-PCA, Society for Industrial and Applied Mathematics. [Link]
9780898718416
respectively. Figure 14 (c) and Figure 14 (d) explore the query per- [14] Erik Bernhardsson. 2015. Approximate Nearest Neighbors in C++/Python opti-
formance of SC-based methods under different alpha-beta settings: mized for memory usage and loading/saving to disk. [Link]
SuCo exhibits the best performance. Therefore, our proposed simple annoy
[15] Alina Beygelzimer, Sham Kakade, and John Langford. 2006. Cover trees for
division strategy is more beneficial to the subspace collision frame- nearest neighbor. In Proceedings of the 23rd international conference on Machine
work than previously proposed data preprocessing techniques. learning. 97–104.
SIGMOD ’25, June 22–27, 2025, Berlin, Germany Jiuqi Wei, Xiaodong Lee, Zhenyu Liao, Themis Palpanas, and Botao Peng
[16] Gunnar Blom. 1958. Statistical Estimates and Transformed Beta-variables. Wiley. on Very Large Databases. 506–515.
[17] Christian Böhm. 2000. A cost model for query processing in high dimensional [43] Qiang Huang, Jianlin Feng, Yikai Zhang, Qiong Fang, and Wilfred Ng. 2015.
data spaces. ACM Transactions on Database Systems (TODS) 25, 2 (2000), 129– Query-aware locality-sensitive hashing for approximate nearest neighbor search.
178. Proceedings of the VLDB Endowment 9, 1 (2015), 1–12.
[18] Allan Borodin, Rafail Ostrovsky, and Yuval Rabani. 1999. Lower bounds for [44] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravis-
high dimensional nearest neighbor search and related problems. In Proceedings hankar Krishnawamy, and Rohan Kadekodi. 2019. Diskann: Fast accurate
of the thirty-first annual ACM symposium on Theory of computing. 312–321. billion-point nearest neighbor search on a single node. Advances in Neural
[19] Leonid Boytsov and Bilegsaikhan Naidan. 2013. Learning to prune in metric Information Processing Systems 32 (2019).
and non-metric spaces. Advances in Neural Information Processing Systems 26 [45] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization
(2013). for nearest neighbor search. IEEE transactions on pattern analysis and machine
[20] Alessandro Camerra, Jin Shieh, Themis Palpanas, Thanawin Rakthanmanon, intelligence 33, 1 (2010), 117–128.
and Eamonn Keogh. 2014. Beyond one billion time series: indexing and mining [46] Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 2011.
very large time series collections with iSAX2+. Knowledge and information Searching in one billion vectors: re-rank with source coding. In 2011 IEEE
systems 39, 1 (2014), 123–151. International Conference on Acoustics, Speech and Signal Processing (ICASSP).
[21] Lawrence Cayton. 2008. Fast nearest neighbor retrieval for bregman divergences. IEEE, 861–864.
In Proceedings of the 25th international conference on Machine learning. 112–119. [47] Kerstin Johnsson, Charlotte Soneson, and Magnus Fontes. 2014. Low bias
[22] Manos Chatzakis, Panagiota Fatourou, Eleftherios Kosmas, Themis Palpanas, local intrinsic dimension estimation from expected simplex skewness. IEEE
and Botao Peng. 2023. Odyssey: A Journey in the Land of Distributed Data Series transactions on pattern analysis and machine intelligence 37, 1 (2014), 196–202.
Similarity Search. Proceedings of the VLDB Endowment 16, 5 (2023), 1140–1153. [48] Yannis Kalantidis and Yannis Avrithis. 2014. Locally optimized product quan-
[23] Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason tization for approximate nearest neighbor search. In Proceedings of the IEEE
Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for conference on computer vision and pattern recognition. 2321–2328.
fast approximate nearest neighbor search. [49] Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey
[24] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open-
Li, Mao Yang, and Jingdong Wang. 2021. Spann: Highly-efficient billion-scale domain question answering. arXiv preprint arXiv:2004.04906 (2020).
approximate nearest neighborhood search. Advances in Neural Information [50] Haridimos Kondylakis, Niv Dayan, Kostas Zoumpatianos, and Themis Palpanas.
Processing Systems 34 (2021), 5199–5212. 2018. Coconut: A Scalable Bottom-Up Approach for Building Data Series Indexes.
[25] Romain Couillet and Zhenyu Liao. 2022. Random Matrix Methods for Machine Proceedings of the VLDB Endowment 11, 6 (2018).
Learning. Cambridge University Press. [51] Haridimos Kondylakis, Niv Dayan, Kostas Zoumpatianos, and Themis Palpanas.
[26] Sanjoy Dasgupta and Yoav Freund. 2008. Random projection trees and low 2019. Coconut: sortable summarizations for scalable indexes over static and
dimensional manifolds. In Proceedings of the fortieth annual ACM symposium on streaming data series. VLDB J. 28, 6 (2019), 847–869.
Theory of computing. 537–546. [52] Yifan Lei, Qiang Huang, Mohan Kankanhalli, and Anthony KH Tung. 2020.
[27] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Locality-sensitive hashing scheme based on longest circular co-substring. In
Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings Proceedings of the 2020 ACM SIGMOD International Conference on Management
of the twentieth annual symposium on Computational geometry. 253–262. of Data. 2589–2599.
[28] Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor [53] Mingjie Li, Ying Zhang, Yifang Sun, Wei Wang, Ivor W Tsang, and Xuemin
graph construction for generic similarity measures. In Proceedings of the 20th Lin. 2020. I/O efficient approximate nearest neighbour search based on learned
international conference on World wide web. 577–586. functions. In 2020 IEEE 36th International Conference on Data Engineering (ICDE).
[29] Karima Echihabi, Panagiota Fatourou, Kostas Zoumpatianos, Themis Palpanas, IEEE, 289–300.
and Houda Benbrahim. 2022. Hercules against data series similarity search. [54] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and
Proceedings of the VLDB Endowment 15, 10 (2022), 2005–2018. Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional
[30] Karima Echihabi, Kostas Zoumpatianos, and Themis Palpanas. 2020. Scalable data—experiments, analyses, and improvement. IEEE Transactions on Knowledge
Machine Learning on High-Dimensional Vectors: From Data Series to Deep and Data Engineering 32, 8 (2019), 1475–1488.
Network Embeddings. In International Conference on Web Intelligence, Mining [55] Ying Li, Jiuqi Wei, Ziyu Fei, Yufan Fu, and Xiaodong Lee. 2024. DiSAuth: A
and Semantics WIMS. 1–6. DNS-based secure authorization framework for protecting data decoupled from
[31] Karima Echihabi, Kostas Zoumpatianos, Themis Palpanas, and Houda Ben- applications. Computer Networks 254 (2024), 110774.
brahim. 2019. Return of the Lernaean Hydra: Experimental Evaluation of Data [56] Zhenyu Liao, Romain Couillet, and Michael W. Mahoney. 2020. A Random
Series Approximate Similarity Search. Proc. VLDB Endow. 13, 3 (2019), 403–420. Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a
[Link] Precise Phase Transition, and the Corresponding Double Descent. In Advances
[32] Panagiota Fatourou, Eleftherios Kosmas, Themis Palpanas, and George Paterakis. in Neural Information Processing Systems, Vol. 33. Curran Associates, Inc., 13939—
2023. FreSh: A Lock-Free Data Series Index. In 42nd International Symposium 13950.
on Reliable Distributed Systems, SRDS. IEEE, 209–220. [Link] [57] Michele Linardi and Themis Palpanas. 2018. Scalable, variable-length similarity
SRDS60354.2023.00029 search in data series: The ULISSE approach. Proceedings of the VLDB Endowment
[33] Cong Fu, Changxu Wang, and Deng Cai. 2021. High dimensional similarity 11, 13 (2018), 2236–2248.
search with satellite system graph: Efficiency, scalability, and unindexed query [58] Michele Linardi and Themis Palpanas. 2020. Scalable data series subsequence
compatibility. IEEE Transactions on Pattern Analysis and Machine Intelligence 44, matching with ULISSE. VLDB J. 29, 6 (2020), 1449–1474.
8 (2021), 4139–4150. [59] Wanqi Liu, Hanchen Wang, Ying Zhang, Wei Wang, Lu Qin, and Xuemin
[34] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate Lin. 2021. EI-LSH: An early-termination driven I/O efficient incremental c-
nearest neighbor search with the navigating spreading-out graph. Proceedings approximate nearest neighbor search. The VLDB Journal 30 (2021), 215–235.
of the VLDB Endowment 12, 5 (2019), 461–474. [60] Yingfan Liu, Hong Cheng, and Jiangtao Cui. 2017. PQBF: i/o-efficient approx-
[35] Keinosuke Fukunaga and Patrenahalli M. Narendra. 1975. A branch and bound imate nearest neighbor search by product quantization. In Proceedings of the
algorithm for computing k-nearest neighbors. IEEE transactions on computers 2017 ACM on Conference on Information and Knowledge Management. 667–676.
100, 7 (1975), 750–753. [61] Yingfan Liu, Jiangtao Cui, Zi Huang, Hui Li, and Heng Tao Shen. 2014. SK-LSH:
[36] Junhao Gan, Jianlin Feng, Qiong Fang, and Wilfred Ng. 2012. Locality-sensitive an efficient index structure for approximate nearest neighbor search. Proceedings
hashing scheme based on dynamic collision counting. In Proceedings of the 2012 of the VLDB Endowment 7, 9 (2014), 745–756.
ACM SIGMOD international conference on management of data. 541–552. [62] Cosme Louart, Zhenyu Liao, and Romain Couillet. 2018. A Random Matrix
[37] Jianyang Gao and Cheng Long. 2023. High-dimensional approximate nearest Approach to Neural Networks. Annals of Applied Probability 28, 2 (2018), 1190–
neighbor search: with reliable and efficient distance comparison operations. 1248. [Link]
Proceedings of the ACM on Management of Data 1, 2 (2023), 1–27. [63] Kejing Lu and Mineichi Kudo. 2020. R2LSH: A nearest neighbor search scheme
[38] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product based on two-dimensional projected spaces. In 2020 IEEE 36th International
quantization. IEEE transactions on pattern analysis and machine intelligence 36, Conference on Data Engineering (ICDE). IEEE, 1045–1056.
4 (2013), 744–755. [64] Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. 2021. HVS:
[39] Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in hierarchical graph structure based on voronoi diagrams for solving approximate
high dimensions via hashing. In Vldb, Vol. 99. 518–529. nearest neighbor search. Proceedings of the VLDB Endowment 15, 2 (2021),
[40] Robert Gray. 1984. Vector quantization. IEEE Assp Magazine 1, 2 (1984), 4–29. 246–258.
[41] Robert M. Gray and David L. Neuhoff. 1998. Quantization. IEEE transactions on [65] Kejing Lu, Hongya Wang, Wei Wang, and Mineichi Kudo. 2020. VHP: approxi-
information theory 44, 6 (1998), 2325–2383. mate nearest neighbor search via virtual hypersphere partitioning. Proceedings
[42] Alexander Hinneburg, Charu C Aggarwal, and Daniel A Keim. 2000. What is of the VLDB Endowment 13, 9 (2020), 1443–1455.
the nearest neighbor in high dimensional spaces?. In 26th Internat. Conference
Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search SIGMOD ’25, June 22–27, 2025, Berlin, Germany
[66] Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. [91] Yao Tian, Xi Zhao, and Xiaofang Zhou. 2023. DB-LSH 2.0: Locality-Sensitive
2014. Approximate nearest neighbor algorithm based on navigable small world Hashing With Query-Based Dynamic Bucketing. IEEE Transactions on Knowl-
graphs. Information Systems 45 (2014), 61–68. edge and Data Engineering (2023).
[67] Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate [92] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. 2021. A com-
nearest neighbor search using hierarchical navigable small world graphs. IEEE prehensive survey and experimental comparison of graph-based approximate
transactions on pattern analysis and machine intelligence 42, 4 (2018), 824–836. nearest neighbor search. Proceedings of the VLDB Endowment 14, 11 (2021),
[68] Yusuke Matsui, Yusuke Uchida, Hervé Jégou, and Shin’ichi Satoh. 2018. A survey 1964–1978.
of product quantization. ITE Transactions on Media Technology and Applications [93] Qitong Wang, Ioana Ileana, and Themis Palpanas. 2025. LeaFi: Data Series
6, 1 (2018), 2–10. Indexes on Steroids with Learned Filters. Proc. ACM Manag. Data (2025).
[69] Yusuke Matsui, Toshihiko Yamasaki, and Kiyoharu Aizawa. 2015. Pqtable: Fast [94] Qitong Wang and Themis Palpanas. 2021. Deep learning embeddings for data
exact asymmetric distance neighbor search for product quantization using hash series similarity search. In Proceedings of the 27th ACM SIGKDD conference on
tables. In Proceedings of the IEEE International Conference on Computer Vision. knowledge discovery & data mining. 1708–1716.
1940–1948. [95] Qitong Wang and Themis Palpanas. 2023. SEAnet: A Deep Learning Architecture
[70] Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for Data Series Similarity Search. IEEE Trans. Knowl. Data Eng. 35, 12 (2023),
for high dimensional data. IEEE transactions on pattern analysis and machine 12972–12986.
intelligence 36, 11 (2014), 2227–2240. [96] Yang Wang, Peng Wang, Jian Pei, Wei Wang, and Sheng Huang. 2013. A data-
[71] Javier Vargas Munoz, Marcos A Gonçalves, Zanoni Dias, and Ricardo da S Torres. adaptive and dynamic segmentation index for whole matching on time series.
2019. Hierarchical clustering-based graphs for large scale approximate nearest VLDB (2013).
neighbor search. Pattern Recognition 96 (2019), 106970. [97] Zeyu Wang, Peng Wang, Themis Palpanas, and Wei Wang. 2023. Graph- and
[72] Riley Murray, James Demmel, Michael W. Mahoney, N. Benjamin Erichson, Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses,
Maksim Melnichenko, Osman Asif Malik, Laura Grigori, Piotr Luszczek, Michał Comparisons, and Future Directions. IEEE Data Eng. Bull. 47, 3 (2023), 3–21.
Dereziński, Miles E. Lopes, Tianyu Liang, Hengrui Luo, and Jack Dongarra. 2023. [98] Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas,
Randomized Numerical Linear Algebra : A Perspective on the Field With an and Wei Wang. 2024. 𝑺𝒕 𝒆𝒊𝒏𝒆𝒓 -Hardness: A Query Hardness Measure for
Eye to Software. [Link] arXiv:2302.11474 Graph-Based ANN Indexes. PVLDB (2024).
[73] Gonzalo Navarro. 2002. Searching in metric spaces by spatial approximation. [99] Zeyu Wang, Qitong Wang, Peng Wang, Themis Palpanas, and Wei Wang. 2023.
The VLDB Journal 11 (2002), 28–46. Dumpy: A Compact and Adaptive Index for Large Data Series Collections. Proc.
[74] Mohammad Norouzi and David J Fleet. 2013. Cartesian k-means. In Proceedings ACM Manag. Data 1, 1 (2023), 111:1–111:27.
of the IEEE Conference on computer Vision and Pattern Recognition. 3017–3024. [100] Zeyu Wang, Qitong Wang, Peng Wang, Themis Palpanas, and Wei Wang. 2024.
[75] Themis Palpanas. 2015. Data Series Management: The Road to Big Sequence DumpyOS: A data-adaptive multi-ary index for scalable data series similarity
Analytics. SIGMOD Record (2015). search. The VLDB Journal (2024), 1–25.
[76] Themis Palpanas and Volker Beckmann. 48(3), 2019. Report on the First and [101] Roger Weber, Hans-Jörg Schek, and Stephen Blott. 1998. A quantitative analy-
Second Interdisciplinary Time Series Analysis Workshop (ITISA). SIGREC (48(3), sis and performance study for similarity-search methods in high-dimensional
2019). spaces. In VLDB, Vol. 98. 194–205.
[77] Marco Patella and Paolo Ciaccia. 2008. The many facets of approximate similarity [102] Jiuqi Wei. 2024. Subspace Collision: An Efficient and Accurate Framework for
search. In First International Workshop on Similarity Search and Applications High-dimensional Approximate Nearest Neighbor Search. [Link]
(sisap 2008). IEEE, 10–21. WeiJiuQi/SuCo.
[78] Marco Patella and Paolo Ciaccia. 2009. Approximate similarity search: A multi- [103] Jiuqi Wei, Ying Li, Yufan Fu, Youyi Zhang, and Xiaodong Li. 2023. Data In-
faceted problem. Journal of Discrete Algorithms 7, 1 (2009), 36–48. teroperating Architecture (DIA): Decoupling Data and Applications to Give
[79] Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2018. ParIS: The Next Back Your Data Ownership. In 2023 IEEE 47th Annual Computers, Software, and
Destination for Fast Data Series Indexing and Query Answering. IEEE BigData Applications Conference (COMPSAC). IEEE, 438–447.
(2018). [104] Jiuqi Wei, Botao Peng, Xiaodong Lee, and Themis Palpanas. 2024. DET-LSH: A
[80] Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2020. Messi: In-memory Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approxi-
data series indexing. In 2020 IEEE 36th International Conference on Data Engi- mate Nearest Neighbor Search. Proceedings of the VLDB Endowment 17, 9 (2024),
neering (ICDE). IEEE, 337–348. 2241–2254.
[81] Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2020. Paris+: Data series [105] Yan Xia, Kaiming He, Fang Wen, and Jian Sun. 2013. Joint inverted indexing. In
indexing on multi-core architectures. IEEE Transactions on Knowledge and Data Proceedings of the IEEE International Conference on Computer Vision. 3416–3423.
Engineering 33, 5 (2020), 2151–2164. [106] Djamel Edine Yagoubi, Reza Akbarinia, Florent Masseglia, and Themis Palpanas.
[82] Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2021. Fast data series 2017. DPiSAX: Massively Distributed Partitioned iSAX. In IEEE International
indexing for in-memory data. VLDB J. 30, 6 (2021). Conference on Data Mining, ICDM. 1135–1140.
[83] Botao Peng, Panagiota Fatourou, and Themis Palpanas. 2021. SING: Sequence [107] Djamel Edine Yagoubi, Reza Akbarinia, Florent Masseglia, and Themis Palpanas.
Indexing Using GPUs. In 2021 IEEE 37th International Conference on Data Engi- 2020. Massively Distributed Time Series Indexing and Querying. IEEE Trans.
neering (ICDE). IEEE, 1883–1888. Knowl. Data Eng. 32, 1 (2020), 108–120.
[84] Yun Peng, Byron Choi, Tsz Nam Chan, Jianye Yang, and Jianliang Xu. 2023. [108] Peter N Yianilos. 1993. Data structures and algorithms for nearest neighbor
Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases. search in general metric spaces. In Soda, Vol. 93. 311–21.
Proceedings of the ACM on Management of Data 1, 1 (2023), 1–27. [109] Ting Zhang, Chao Du, and Jingdong Wang. 2014. Composite quantization for
[85] J Ben Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen. 2007. Collabora- approximate nearest neighbor search. In International Conference on Machine
tive filtering recommender systems. In The adaptive web: methods and strategies Learning. PMLR, 838–846.
of web personalization. Springer, 291–324. [110] Xi Zhao, Yao Tian, Kai Huang, Bolong Zheng, and Xiaofang Zhou. 2023. Towards
[86] Chanop Silpa-Anan and Richard Hartley. 2008. Optimised KD-trees for fast Efficient Index Construction and Approximate Nearest Neighbor Search in
image descriptor matching. In 2008 IEEE Conference on Computer Vision and High-Dimensional Spaces. Proceedings of the VLDB Endowment 16, 8 (2023),
Pattern Recognition. IEEE, 1–8. 1979–1991.
[87] Yifang Sun, Wei Wang, Jianbin Qin, Ying Zhang, and Xuemin Lin. 2014. SRS: [111] Bolong Zheng, Zhao Xi, Lianggui Weng, Nguyen Quoc Viet Hung, Hang Liu,
solving c-approximate nearest neighbor queries in high dimensional euclidean and Christian S Jensen. 2020. PM-LSH: A fast and accurate LSH framework for
space with a tiny index. Proceedings of the VLDB Endowment (2014). high-dimensional approximate NN search. Proceedings of the VLDB Endowment
[88] Yukihiro Tagami. 2017. Annexml: Approximate nearest neighbor search for 13, 5 (2020), 643–655.
extreme multi-label classification. In Proceedings of the 23rd ACM SIGKDD inter- [112] Yuxin Zheng, Qi Guo, Anthony KH Tung, and Sai Wu. 2016. Lazylsh: Approx-
national conference on knowledge discovery and data mining. 455–464. imate nearest neighbor search for multiple distance functions with a single
[89] Yufei Tao, Ke Yi, Cheng Sheng, and Panos Kalnis. 2009. Quality and efficiency index. In Proceedings of the 2016 International Conference on Management of
in high dimensional nearest neighbor search. In Proceedings of the 2009 ACM Data. 2023–2037.
SIGMOD International Conference on Management of data. 563–576. [113] Kostas Zoumpatianos, Stratos Idreos, and Themis Palpanas. 2014. Indexing
[90] Yao Tian, Ziyang Yue, Ruiyuan Zhang, Xi Zhao, Bolong Zheng, and Xiaofang for interactive exploration of big data series. In International Conference on
Zhou. 2023. Approximate Nearest Neighbor Search in High Dimensional Vector Management of Data, SIGMOD.
Databases: Current Research and Future Directions. IEEE Data Engineering [114] Kostas Zoumpatianos, Stratos Idreos, and Themis Palpanas. 2016. ADS: the
Bulletin 47, 3 (2023). adaptive data series index. The VLDB Journal 25 (2016), 843–866.
You might also like
- Locality-Sensitive Hashing Scheme Based On P-Stable DistributionsNo ratings yetLocality-Sensitive Hashing Scheme Based On P-Stable Distributions10 pages
- DiskANN: Efficient Billion-Point SearchNo ratings yetDiskANN: Efficient Billion-Point Search11 pages
- NeurIPS 2021 Spann Highly Efficient Billion Scale Approximate Nearest Neighborhood Search PaperNo ratings yetNeurIPS 2021 Spann Highly Efficient Billion Scale Approximate Nearest Neighborhood Search Paper14 pages
- LoRANN Low-Rank Matrix Factorization For Approximate Nearest Neighbor SearchNo ratings yetLoRANN Low-Rank Matrix Factorization For Approximate Nearest Neighbor Search33 pages
- Revisiting Kd-Tree For Nearest Neighbor Search: Latest UpdatesNo ratings yetRevisiting Kd-Tree For Nearest Neighbor Search: Latest Updates12 pages
- Efficient Nearest Neighbor Search in High Dimensional Hamming SpaceNo ratings yetEfficient Nearest Neighbor Search in High Dimensional Hamming Space11 pages
- Approximate Nearest Neighbor Search For Modern AI: A Projection-Augmented Graph ApproachNo ratings yetApproximate Nearest Neighbor Search For Modern AI: A Projection-Augmented Graph Approach21 pages
- CD-ANN - Scalable Approximate Nearest Neighbor Search On Client-Side DevicesNo ratings yetCD-ANN - Scalable Approximate Nearest Neighbor Search On Client-Side Devices12 pages
- LK-Index A Learned Index For KNN QueriesNo ratings yetLK-Index A Learned Index For KNN Queries8 pages
- SPFresh: In-Place Updates for Vector SearchNo ratings yetSPFresh: In-Place Updates for Vector Search17 pages
- Approximate Nearest Neighbour Search On Dynamic Datasets: An InvestigationNo ratings yetApproximate Nearest Neighbour Search On Dynamic Datasets: An Investigation11 pages
- Locality-Sensitive Hashing Scheme Based On P-Stable DistributionsNo ratings yetLocality-Sensitive Hashing Scheme Based On P-Stable Distributions10 pages
- [Lecture Notes in Computer Science 2341] Cui Yu (eds.) - High-Dimensional Indexing_ Transformational Approaches to High-Dimensional Range and Similarity Searches (2003, Springer-Verlag Berlin Heidelberg) - li.pdfNo ratings yet[Lecture Notes in Computer Science 2341] Cui Yu (eds.) - High-Dimensional Indexing_ Transformational Approaches to High-Dimensional Range and Similarity Searches (2003, Springer-Verlag Berlin Heidelberg) - li.pdf159 pages
- Near-Optimal LSH for High-Dimensional DataNo ratings yetNear-Optimal LSH for High-Dimensional Data6 pages
- LM-DiskANN: Efficient Disk-Based ANN IndexNo ratings yetLM-DiskANN: Efficient Disk-Based ANN Index10 pages
- Optimizing Maximum Inner Product SearchNo ratings yetOptimizing Maximum Inner Product Search18 pages
- MLSys 2022 Halos Hashing Large Output Space For Cheap Inference PaperNo ratings yetMLSys 2022 Halos Hashing Large Output Space For Cheap Inference Paper16 pages
- Efficient Similarity Indexing and Searching in High DimensionsNo ratings yetEfficient Similarity Indexing and Searching in High Dimensions8 pages
- Efficient 2D GJK Algorithm with BarycodeNo ratings yetEfficient 2D GJK Algorithm with Barycode8 pages
- Books - Google.Co - in Books?Id GnvtngeacaajNo ratings yetBooks - Google.Co - in Books?Id Gnvtngeacaaj1 page
- FAISS: GPU-Accelerated Similarity SearchNo ratings yetFAISS: GPU-Accelerated Similarity Search12 pages
- High-Dimensional Similarity Search IssuesNo ratings yetHigh-Dimensional Similarity Search Issues16 pages
- Mixed Vector-Relational Search OptimizationNo ratings yetMixed Vector-Relational Search Optimization9 pages
- 688 Filtered ANN Search on Vectors With Diverse LabelsNo ratings yet688 Filtered ANN Search on Vectors With Diverse Labels15 pages
- Flash: Efficient Graph Indexing for ANNSNo ratings yetFlash: Efficient Graph Indexing for ANNS17 pages
- In-Place Updates of A Graph Index For Streaming Approximate Nearest Neighbor SearchNo ratings yetIn-Place Updates of A Graph Index For Streaming Approximate Nearest Neighbor Search11 pages
- Adaptive Distance Bounds for High-Dimensional IndexingNo ratings yetAdaptive Distance Bounds for High-Dimensional Indexing8 pages
- CABANA Cluster-Aware Query Batching For Accelerating Billion-Scale ANNS With Intel AMXNo ratings yetCABANA Cluster-Aware Query Batching For Accelerating Billion-Scale ANNS With Intel AMX4 pages
- Pivot Selection for Distance-Based IndexingNo ratings yetPivot Selection for Distance-Based Indexing16 pages
- Evolution of the English Textile IndustryNo ratings yetEvolution of the English Textile Industry10 pages
- Learning Indicators for English TeachersNo ratings yetLearning Indicators for English Teachers98 pages
- Feasibility Study: Car Apartment ProjectNo ratings yetFeasibility Study: Car Apartment Project3 pages
- IGCSE English 0500 Grade Thresholds 2021No ratings yetIGCSE English 0500 Grade Thresholds 20212 pages
- Ancient Astronomy and Celestial DiscoveriesNo ratings yetAncient Astronomy and Celestial Discoveries17 pages
- Mental Health's Impact on Student PerformanceNo ratings yetMental Health's Impact on Student Performance3 pages
- Elite Boarding School Exam Strategy GuideNo ratings yetElite Boarding School Exam Strategy Guide18 pages
- Kabarak University BSCSF Exam: Info SecurityNo ratings yetKabarak University BSCSF Exam: Info Security3 pages
- Sequential File Handling in Visual BasicNo ratings yetSequential File Handling in Visual Basic4 pages
- Pentecostalism's Role in Gilgil EvangelismNo ratings yetPentecostalism's Role in Gilgil Evangelism5 pages