arXiv:2605.10135v1 [cs.DB] 11 May 2026
ScaleGANN: Accelerate Large-Scale ANN Indexing by Cost-effective Cloud GPUs Lan Lu
Peiqi Yin
Isaac Yang
Tao Luo
University of Pennsylvania [email protected]
CUHK [email protected]
Duke Kunshan University [email protected]
University of Pennsylvania [email protected]
Hua Fan
Wenchao Zhou
Feifei Li
Boon Thau Loo
Alibaba Cloud [email protected]
Alibaba Cloud [email protected]
Alibaba Cloud [email protected]
University of Pennsylvania [email protected]
Abstract—Graph-based ANNS algorithms have gained increasing research interest and market adoption due to their efficiency and accuracy in retrieval. Existing approaches primarily rely on CPUs for graph index construction and retrieval, but this often requires significant time, especially for large-scale and high-dimensional datasets. Some studies have explored GPUbased solutions. However, GPUs are costly and their limited memory makes handling large datasets challenging. In this paper, we propose a novel end-to-end system ScaleGANN that enables users to efficiently construct graph indexes for largescale, high-dimensional datasets by leveraging low-cost spot GPU resources in a distributed cloud system. ScaleGANN utilized the idea of divide-and-merge, with an optimized vector partitioning algorithm to further improve the indexing time and space efficiency while guaranteeing good index quality. Its novel resource allocation strategy realized multi-GPU indexing parallelism and overall cost-effectiveness for both build and query. Besides, we designed a task scheduler and cost model for better spot instance management and evaluation. We tested our system on large real-world datasets. Experiment results show that our approach can significantly accelerate the index build time to up to 9x times at even 6x lower price compared with the state-of-theart extendable ANNS benchmark DiskANN, while we preserve the same scalability and similar search quality as DiskANN.
I. I NTRODUCTION Approximate Nearest Neighbor Search (ANNS) is a fundamental technique in vector databases. By building an index over the dataset and limiting the search to vectors similar to a given query, ANNS significantly enhances retrieval speed, with a minor sacrifice in accuracy. It has been widely adopted across multiple domains including information retrieval [1], [2], pattern recognition [3], [4], recommendation systems [5], [6], and machine learning [7], [8]. Among various types of index, graph-based indexes [2], [9]–[12] generally achieve better search quality [4], [9] due to fine granularity graph traversal. Therefore, they are widely adopted in practice. Scaling graph indexing to large datasets. An increasing number of applications operate over large-scale datasets, posing new challenges for ANNS. For example, e-commerce platforms and social medias routinely store data at the billionscale [13], [14], often with thousands of dimensions or even higher. Many of these services demand frequent index updates
and reconstructions to maintain accurate query results, such as web search engines and recommendation systems [15]. Yet, efficiently constructing graph indexes for large datasets remains challenging due to limited storage, and the timeconsuming extensive distance computations required for edge discovery. For billion-scale, high-dimensional datasets, index construction can take multiple terabytes of memory, and last for several days to weeks to complete [16], [17]. Partition-based scalability and problems. The typical solution to graph indexing with high storage demands is data sharding, while trading off build and query performance. Incorporated with disk storage, DiskANN [16] replicates each vector across shards to maintain global connectivity and facilitates shard index merging after the subgraphs are built. However, replication increases I/O and lengthens buildtime roughly in proportion to the number of vectors replicated [11], [18]. In contrast, other approaches split the dataset into independent shards without replication or merging, such as GGNN [19]. Yet, during querying, each shard must be searched independently, increasing latency and compute. GPU-based accelerations and challenges. To accelerate index building, existing works proposed GPU-based implementations [11], [19]–[21] in construction and querying. However, limited GPU VRAM, frequent GPU-CPU transfers, and higher on-demand pricing make them hard to use cost-effectively at scale. According to AWS [22] and Alibaba cloud [23] pricing, adding four 16GB V100 GPUs to a machine with 32 vCPUs and 256 GiB RAM can increase the cost by 6–7×. The costs can escalate with higher memory capacity, greater computational performance, or additional GPUs. Balancing index build and search performance. Besides, existing ANNS systems run entirely on CPUs or GPUs for both index construction and query. The former slows index construction, while the latter increases serving latency relative to CPU-based ones [7], [24]. Especially, GPU-based shard querying for large datasets incurs additional distance computations and frequent GPU-CPU data transfers. Furthermore, the unpredictable distribution and frequency of queries in realworld applications often limit batching and parallelism oppor-
tunities, leading to expensive but suboptimal GPU utilization during search. Most notably, CPU-based querying throughput meets the performance requirements of most applications [7], [24], making GPU-based querying unnecessary in many cases. Our solution: ScaleGANN. Therefore, we present ScaleGANN, a novel GPU-CPU hybrid and cloud-native framework that enables efficient and disk-resident scalable graph ANNS indexing for large-scale, high-dimensional datasets, which also balances cost and search performance. ScaleGANN propose use of cloud GPUs (especially costeffective spot instances up to 10x cheaper [22], [23], [25]) exclusively for accelerating the one-time (or periodic) index construction, while delegating long-running, latency-sensitive query serving [15] to CPUs. This design choice reflects the nature of the workload: index construction is typically a onetime, compute-intensive process, while query serving is longrunning and highly cost-sensitive. This also enables resource isolation between build and query, ensuring stable query performance, while allowing the built index to be replicated for scalable serving across multiple machines. At its core, ScaleGANN extends a disk-incorporated partition-and-merge design with enhanced selective replication to reduce disk I/Os, memory usage and build time, while maintaining global graph connectivity and quality. Unlike DiskANN which duplicates each point at least once with a uniform count across the dataset, ScaleGANN effectively replicates only the most essential vectors based on our proposed pruning techniques. Once obtaining the partitioned vector shards, ScaleGANN’s decoupled indexing tasks are further accelerated by multi-GPU parallelism. We also parallel the vector assignment to shards, and design a disk buffer state check during index merge to handle the non-deterministic vector order within each shard caused by thread parallelism. To address the inherent instability and evaluate the costeffectiveness of preemptive spot instances, we introduce a spot instance task scheduler and a intuitive cost model. We specify spot GPU instance use only for shard indexing tasks which are parallel and small in size limited by GPU memory limit, and leave the tightly-coupled partition and merge on non-spot machines. Then we deploy a spot instance task scheduler on CPUs to manage the assignment of each shard indexing task to an available GPU spot instance. By estimating task execution time which is proportional to the shard size, the scheduler tries to allow task assignment only to spot instances with sufficient remaining availability. Lastly, we design a intuitive cost model for evaluating the expense of different resources, and illustrate the cost-effectiveness of spot instance with an example in experiments. While ScaleGANN’s general framework allows the integration with diverse indexing algorithms, in this work, we integrate it with the state-of-the-art GPU-based CAGRA [11] algorithm, and demonstrate its scalability, performance, retrieval quality, and cost-effectiveness on real-world datasets ranging from millions to billions of vectors. Notably, ScaleGANN significantly reduces index construc-
tion time relative to disk-incorporated CPU-based baselines, while maintaining similar search quality at matched recall. On high-dimensional Laion100M dataset and index build degree R=128, we observe up to 9× overall acceleration over DiskANN. Besides, compared to GPU-based approach, ScaleGANN realizes affordable indexing time for large datasets, while the partition-merge-based ScaleGANN achieves ∼3× acceleration in search latency at same recall compared to the partition-based Extended CAGRA (we extend CAGRA for large datasets) and GGNN. While ScaleGANN achieves even ∼3× overall build acceleration over GGNN on Laion100M (R=128), its GPU build-only time (without partition and merge time) on the replicated dataset always remains <2× that of Extended CAGRA, benefiting from our enhanced selective vector replication for both the build efficiency and search quality. Importantly, these improvements can be achieved at much lower dollar cost (up to 6x cheaper than DiskANN) if using GPU spot instances. In summary, our main contributions are as follows: • We propose the first end-to-end spot-instance-aware GPU system for graph ANNS indexing, which is highly efficient, scalable, and extendable to cost-effective cloud resources. • We design a novel resource allocation strategy which supports multi-GPU parallelism for decoupled indexing tasks and CPU-based querying, to balance build efficiency, search latency and cost-effectiveness. • We improve the partition-merge-based construction approach especially with selective vector replication and parallelism to save indexing time and memory usage while ensuring global connectivity. Search performance remains unaffected or even improved after replication pruning. • We design a spot instance scheduler and cost model to manage task assignment and analyze the cost-effectiveness. • We integrate ScaleGANN with CAGRA, and validate it on real-world, large-scale high-dimensional datasets. Compared to DiskANN, ScaleGANN brings a significant acceleration in index build at a considerable low expense, while maintaining similar high search performance. II. BACKGROUND A. Graph-based ANNS Index Among various ANNS index structures [4], [26]–[28], the graph-based index [2], [9], [10], [12] is considered the most effective due to its high accuracy and low computational cost. It builds a proximity graph [2], [9], [10] over the vector dataset, typically using k-nearest-neighbor [11], [29], [30] or small world graphs [10], [12] , where each node represents a vector and is connected to its similar vectors. Existing graphbased indexes use different construction techniques, such as NSG [9] and HNSW [10], to balance the trade-off between index quality and construction overhead. Additionally, SONG [20], CAGRA [11], and GANNS [21] leverage GPUs to speed up the graph construction. The extensive distance calculations between nodes and their neighbors can be efficiently parallelized by GPU using matrix multiplication (matmul). While CAGRA [11] achieves 2.2–27×
speedups compared to leading CPU-based methods such as HNSW [10], all these works currently support only datasets that fit entirely within a single GPU’s memory. Vamana, introduced by DiskANN [16], enables graph construction at billion-scale through a partition-and-merge approach. It begins by dividing the database into multiple shards using K-means clustering. To maintain overall graph connectivity, each node is assigned to multiple shards (typically two), serving as a link between partitions. Each subgraph construction is then sequentially executed and parallelized by multiple CPU threads, enabling independent and efficient subgraph construction. Once the individual subgraphs are built, they are merged into a single, connected graph over the complete dataset via edge union, preserving the local structure within shards while ensuring global connectivity. By leveraging disk storage to overcome memory constraints during partition and merge, DiskANN enables support for billion-scale datasets. GGNN [19] partitions the graph into smaller shards, assigning each GPU to construct the graph for a single shard. Unlike Vamana, which partitions before construction and merges after, GGNN performs partitioning during graph construction and merging during the search phase. Its partitioning strategy avoids node duplication, since each node appears in only one subgraph and each subgraph resides independently in GPU memory. During similarity search, GGNN exploits GPU parallelism by having each GPU search for the local topk results within its subgraph. These local results are then aggregated across GPUs to compute the final top-k results. B. Spot Instance Modern cloud providers offer spot GPU instance products (e.g., Alibaba Cloud ECS [23], Azure spot VMs [31] and AWS spot instances [22]), with a much cheaper price compared to on-demand instances (up to 90% price reduction). However, these spot instances are preemptible, and cloud providers may terminate the service at any time. When the spot service is terminated or preempted by other on-demand instances, the user will generally receive a notification ahead (i.e., 5 minutes by Alibaba ECS [23]). Users can migrate their working jobs during that period. Besides, most spot instances have a safe duration time at initialization (i.e., 1 hour [23]), while spot instances without such a protection period are even cheaper. III. M OTIVATION As large-scale ANNS applications become prevalent, efficient graph index construction is ever more critical. In this section, we present several case studies to analyze the bottlenecks in graph indexing for large datasets and explore potential optimization directions, thereby motivating the design of our framework. We conduct a simple sampling analysis on the Sift1B and Laion1B datasets. The dimensionality and data types of these datasets are summarized in Table II. The unit of time is second (s) in this section. Slow Graph Index Construction on Large Datasets, and Shard Index Build Dominates the Time. Table I presents the time breakdown of graph index construction on the Sift100M
TABLE I T IME B REAKDOWN ( S ) OF D ISK ANN I NDEX C ONSTRUCTION . Sift100M (R=32, L=64) Sift100M (R=64, L=128)
Disk Partition 129.1
Index Build on shards 3021.8
Disk Merge 978.5
157.5
7847.9
1591.8
TABLE II I NDEX B UILD T IME ( S ) OF CAGRA AND D ISK ANN. Dataset
Dimension
Data Type
Sift1M Laion1M
128 768
uint8 float
CAGRA (R=32, L=64) 12.7 25.8
DiskANN (R=32, L=64) 13.2 112.4
dataset using DiskANN. Given a memory cap of 16 GB, DiskANN performs partitioned index construction and merging. We conduct experiments using 80 parallel CPU threads, with two different configurations of graph construction parameters where final index degree R and intermediate graph degree L are set to (32, 64) and (64, 128), respectively. We observe that DiskANN takes a considerable amount of time to complete index construction on Sift100M. As the parameters L and T increase, the construction time becomes even longer. Furthermore, as shown in Table II, the Sift dataset is relatively simple compared to others such as Laion. When the same number of vectors are sampled from different datasets, we find that higher data dimensionality and a shift from integer to floating-point data types significantly increase DiskANN’s index construction time. This is primarily due to the larger number and higher cost of distance computations in highdimensional spaces with floating-point operations. In addition, we observe that index building on data shards is the dominant time contributor, compared to data partitioning and disk merging. As the parameters L and R increase, the proportion of time spent on index building becomes even larger—again, due to the increasing cost of distance computations. These findings clearly demonstrate the necessity of accelerating the graph index build process, especially for large-scale datasets. GPU Accelerates the Index Build. Table II compares the graph index construction time between the GPU-based CAGRA algorithm and the CPU-based DiskANN algorithm on the Sift1M and Laion1M datasets. Due to GPU memory limitations (typically 16–80 GB), CAGRA can only support smallscale datasets for index construction. Therefore, we restrict the comparison to 1M-scale datasets. In this setting, DiskANN is able to directly construct the graph index in memory without partitioning and merging, and so can CAGRA. Thus, both methods operate under the same assumption that there is no need for partitioned indexing or post-processing merge steps. We conduct experiments using an NVIDIA V100 GPU with 16 GB memory and 5120 threads. During index construction, we fix the final index degree R and the intermediate graph degree L to 32 and 64, respectively. Our results show that, compared to CPU-based DiskANN, GPU-based CAGRA significantly accelerates the index build process for datasets with higher dimensionality and floating-point data types, where distance
Vector Dataset
Active Cloud Instance List Instance 1
1
Partition Data Shard
Disk 2
Available
Instance …
Instance n
Available
Index Build
Activate
Deactivate
Spot GPU Instance
Regular GPU Instance
Index Build Task Scheduling
Data Index Shard 3
Task Allocation
Instance 2
Index Build
Merge
Local CPU Server Graph Index
Task Status
Cloud GPU Instance Pool
Remote GPU Instances
Fig. 1. Illustration of ScaleGANN’s build Framework.
computations are denser and more computationally expensive. These observations confirm the feasibility and effectiveness of using GPUs to accelerate graph index construction for large datasets with high dimensionality. Scalable Datasets Brings Storage Limitation. Large-scale and high-dimensional datasets can span several or more terabytes [32], while graph index itself introduces additional storage overhead. In contrast, CPU and GPU memory are limited: modern GPUs often offer only 16–80GB, far below the requirements for index construction. Besides, the partitionand-merge based approaches like DiskANN further tighten this constraint by uniformly duplicating every vector. GPU Querying Leads to High Latency and Expense. Limited accelerator memory forces GPU-based querying to operate over partitioned index subgraphs. In GGNN, shards are queried independently with subsequent sorting and merging, whereas swap-based approaches induce frequent host–device transfers. These introduce high search latency. Moreover, unlike the one-time cost of index construction, production-level querying necessitates maintaining GPU availability for stochastic arrivals, which is typically cost-inefficient and yields suboptimal resource utilization relative to CPU-based deployments. Based on the above findings, we motivate both the necessity and feasibility of using GPUs to accelerate graph index construction for large-scale datasets, while also highlighting why GPUs are not suitable for index querying. In response, we propose a novel framework that accelerates graph index construction using GPU resources under a partition-and-merge paradigm, while relying on CPUs to perform index querying. This design strikes a balance between efficiency and costeffectiveness, leveraging the parallelism of GPUs for intensive index building tasks, and the flexibility and scalability of CPUs for handling dynamic, on-demand query workloads. IV. F RAMEWORK OF S CALE GANN We illustrate the overview of ScaleGANN’s build framework in Figure 1. Given an input vector dataset, ScaleGANN uses two types of computational resources, local CPU resources and remote cloud GPU instances, to construct the output merged index. In particular, ScaleGANN prefers GPU spot instances when available rather than regular GPU services for
better cost-effectiveness. It also implements a cloud instance task scheduler to manage task-instance assignment, and disksupported data handling for memory efficiency. Workflow: The end-to-end index construction workflow consists of three key stages: data partitioning, shard-wise index construction using GPU instances, and index merging. (1) Data Partitioning: Given a large input dataset necessary for partitioning, we apply k-means clustering and assign vectors to data shards. Vectors are selectively replicated and wisely assigned across shards to preserve global connectivity and shard locality, while reducing memory usage and processing overhead. We also realize parallel implementation for partition efficiency. The detailed partitioning mechanism is presented in Sec V. (2) Index Build: We use remote GPU instances to construct indexes for data shards, leveraging parallel execution to speed up the distance computations. Each available GPU instance is assigned an independent shard-level indexing task, and invokes a GPU-based indexing algorithm such as CAGRA. Since each per-shard subgraph is built independently, no backforth CPU-CPU communication or inter-GPU communication is necessary during index building. This design not only eliminates redundant CPU-GPU data transfers, but also enables efficient parallelism of multiple idle GPUs for accelerating the otherwise time-consuming index construction process. We also implement a task scheduler for task assignments to appropriate cloud GPU instances, which will be described later. (3) Index Merging: Finally, constructed shard-level indexes are merged into a unified global index, using replicated vectors across shards as connections, as discussed in prior work [16]. Resource Allocation: Our framework utilizes two types of computational resources: local CPUs and remote GPUs. We employ local CPU resources not only for querying, but also for the tightly-coupled data partitioning and index merging. Meanwhile, the remote cloud GPU resources, in particular idle spot instances, are used to accelerate the decoupled shard-level indexing with intensive distance computation. Although certain steps in partitioning and merging could theoretically benefit from GPU acceleration, we deliberately choose to execute them on CPUs for two main reasons: 1. Non-bottleneck nature: Compared to index construction, the time spent on partitioning and merging does not constitute the system’s performance bottleneck. Additionally, transferring data between CPU and GPU memory introduces extra overhead that may offset any potential acceleration benefits. 2. Disk-intensive and highly-coupled logic: Both partitioning and merging involve frequent interactions with disk storage and contain substantial non-parallel, tightly-coupled logic beyond distance computations. These characteristics make them less suitable for GPU acceleration, which is optimized specifically for large-scale parallel numeric operations. By reserving GPU resources for the most computation-intensive index construction, we achieve an effective balance between performance and resource utilization. Cloud Instance Task Scheduler: When constructing shardwise indexes using cloud GPU instances, we require a task scheduler to assign appropriate index construction tasks to
available GPU instances. Specifically, the scheduler needs to maintain two key components: A task list that tracks all pending index construction tasks for data shards, and a cloud instance list that manages active remote GPU instances especially the spot GPU instances and records their status. The cloud instance list records the following statuses for each GPU instance: (1) Active: A GPU instance that has been successfully rented from cloud service provider’s instance pool is marked as active and added to the instance list. Conversely, if the instance service is terminated, it is marked as inactive and removed from the list. (2) Available: Within the cloud instance list, if a GPU is currently executing a task, it is marked as unavailable; otherwise, it is available. (3) Time remaining: For each GPU instance especially the spot instances, if we have accurate information about its remaining active lifetime, we record it accordingly. Note that ScaleGANN always prefers activating the spot GPU instances at a low price given idle spot instances from the cloud. We allocate tasks according to the following two scheduling policies: (1) Availability-based scheduling: Tasks in the task list will not be assigned to any unavailable GPU instance that is already executing a task. (2) Time-based scheduling: We estimate the runtime required for each index construction task, and avoid assigning tasks to instances whose remaining active time is insufficient to complete them. We first sample multiple tiny subsets from the dataset and measure their index construction time. Since construction time scales linearly with dataset size under the same algorithm, hardware configuration and dataset characteristics, we use these results and shard sizes to estimate the build time of larger partitioned data shards under the same indexing settings. Given this, if we know or the cloud provider notifies that a spot instance will be terminated in several minutes, the scheduler prioritizes assigning tasks with estimated run-times less than that to this instance. If no such instances, the scheduler will not assign any task to it. Lastly, if a GPU instance is unfortunately terminated with a unfinished task running on it, the task scheduler will reallocate this task to another suitable instance in the cloud instance list. Spot instance cost analysis: To estimate the cost saving of using spot instances, we design a spot instance cost model. Generally, the graph indexing cost of a given dataset can be evaluated by the machine active time multiplied by the machine price. We assume all the spot GPU instances we use have the same price for simple illustration. In ScaleGANN, throughout the entire index-construction process, the CPU machine remains active, to handle not only shard partitioning and merging, but also shard indexing task scheduling across multiple GPU machines. In contrast, each GPU machine is activated only when it is assigned a shardindex construction task. It is worth noting that multi-GPU parallelism can speed up the overall index-construction time and reduces the CPU-active period. However, for GPU cost consumption, multiple cards within the same GPU machine do not incur additional charges, but multiple GPU machine instances running in parallel are billed separately. Therefore, the cost of using multiple GPU machines should be calculated
Fig. 2. Illustration of Assignment Policy.
as the unit price of a single GPU machine multiplied by the total active time across all GPU machines. In addition, because we rely on cloud resources, the total machine usage time must also account for the network transfer time for shard data communication between CPU and remote GPUs. Overall, the total cost for ScaleGANN if using GPU spot instance(s) is computed as: (overall construction time + data transfer time) × CPU price + (aggregated GPU active time + data transfer time) × GPU spot instance price. Note that in this work, we apply time-based scheduling policy to guide task assignment which tries to avoid unexpected termination. Therefore, the above cost model currently does not consider the cost of spot instance interruption and task rescheduling, and Sec VI presents a simple cost analysis under this assumption. V. A DAPTIVE V ECTOR PARTITIONING To construct a union and connected index for large dataset, we proposed an adaptive disk-resident data partitioning strategy with selective vector replication for both index quality after merge and build efficiency considering storage and time. Given limited GPU and CPU memory, prior partitionand-merge-based indexing work partitions the large dataset into multiple smaller data shards using k-means clustering, replicates all the vectors once or more times across partitions to ensure global connectivity, and then builds index on each partition and merge shard indices. However, there are two issues. (1) Vectors are loaded and processed block-by-block from disk, and those in earlier blocks may saturate clusters too early, preventing later vectors from being assigned to their nearest clusters. To illustrate, we show three cluster centroids c1 , c2 , c3 , and three vectors v1 , v2 , v3 depicted in Figure 2, with their respective cluster preferences as follows: (c1 > c3 > c2 ), (c2 > c3 > c1 ), (c3 > c1 > c2 ). Suppose each vector is replicated at least once, with cluster capacity limit 2, and block order v1 , v2 , v3 . v1 replicas will be assigned to c1 and c3 , then v2 replicas to c2 and c3 , saturating cluster c3 . As a result, v3 can no longer be fairly assigned to its closest cluster c3 , despite being the most appropriate. (2) Since each vector has at least one replica, the dataset size at least doubles, leading to significant memory and processing time overheads. A. Blockwise-adaptive Assignment To ensure fairness in partitioning, we need to mitigate the impact of vector processing order on assignment. We distinguish two types of assignments: assigning (1) an original
vector to its nearest available cluster, and (2) its replicas to other clusters. The first guarantees that every vector belongs to at least one cluster, ensuring dataset completeness and locality. The second improves inter-cluster connectivity, but also introduces distant vectors into other clusters. Each cluster must reserve capacity for original vectors processed later for fairness and locality, while also accepting a certain number of replicas for connectivity. To balance fairness, locality, and connectivity, we introduce a tunable threshold that controls the proportion of cluster space available for replicas. Once this limit is reached, the cluster can only accept original vectors and decline future replicas. Each cluster can have its own replica threshold, adjusted by the data distribution: dense clusters often serve as the nearest choice for many vectors, so they use smaller thresholds to preserve space for unprocessed original vectors. We further support blockwise runtime adaptive adjustment of thresholds. After each block is processed, we update the data distribution information and thresholds for each cluster based on observed vector assignments. Note that during the whole assignment process, to avoid costly disk I/O, the dataset is read only once: for each block, we first assign original vectors to their nearest available clusters, then update cluster distribution statistics and thresholds, finally allocate replicas based on the latest thresholds, and then move to the next block. B. Selective Replication To further reduce data redundancy while maintaining intershard connectivity and enhancing shard locality, we introduce a selective replication strategy. In addition to increased memory and time overhead for storing, manipulating, and indexing the duplicated vectors, full-scale replication introduces redundant assignments. Vectors close to the centroid of their nearest clusters may be unnecessarily replicated to distant clusters, as its neighbors are likely to be only within the cluster and assigning replicas to remote clusters would even create spurious edges. To address these issues, we perform only necessary assignments. Given vector v and its closest centroid c with distance d, for any existing cluster c′ with radius r′ and distance d′ to v, the assignment of v to c′ is necessary if and only if it obeys two constraints. (1) Distance Constraint: d′ < ϵ · d, and (2) Radius Constraint: d′ < ϵ · r′ , where ϵ is a tunable parameter. The intuition is as follows. If d′ is much larger than d or ′ r , it can be implied that v is either close to the center of c, or far from that of c′ , rendering the assignment to c′ unnecessary. Based on this strategy, we replicate vectors only to sufficiently close neighboring clusters. Algorithm 1 illustrates the assignment of replicas with selective replication. Here ω denotes the maximum number of clusters a vector can appear in, and ϵ is a tunable parameter controlling pruning strength. For each loaded block B, we first record the assignment between each vector and its nearest available cluster (Line 2). We also update each cluster’s replica
Algorithm 1 Selective Replica Assignment Input: Vector block B, Number of Clusters k, Cluster replica threshold θ, Cluster radius R, Clusters (set of assigned vectors) S, ω, ϵ, τ Output: Updated clusters S 1: for v ∈ B do 2: c ← loadCentroid(v) # original vector assignment 3: d ← dist(v, c) 4: 5: 6: 7: 8: 9: 10: 11:
assigned ← 1 for c′ ∈ sorted(Centroids, key = dist(v, c′ )) do if assigned ≥ ω then break if c′ ̸= c and checkSizeLimit(c′ , θ) then d′ ← dist(v, c′ ) if d′ < ϵ · d and d′ < ϵ ∗ τ ∗ R[c′ ] then Sc′ ← Sc′ ∪ v assigned ← assigned + 1
threshold θ and radius R based on the block data, which serves as inputs for the assignment. As in Line 5-6, a vector v’s assignment ends once all k clusters have been iterated, or cluster replica limit ω has been reached. For each vector v in the current block, we iterate through the clusters in an ascending order of distances from v shown in Line 5. In Line 7-11, we check the size and remaining replica space of the target cluster c′ , and perform replica assignment from v to c′ if it passes both size check and the selective pruning. During block-by-block manipulation, we observed that in the early stage with fewer processed blocks, the radius of each cluster can be smaller than its actual value. Therefore, we introduce a dynamic radius parameter τ that is initially large and decreases as the number of processed blocks increases, to remedy the actual radius for a more accurate radius-based pruning as shown in Line 9. Recall the example in Figure 2. v1 are replicated on c1 and c3, while v2 is assigned only to c2 , as it lies close to its center. Similarly, v3 is assigned only to c3 because its distance from c1 exceeds the pruning threshold. This not only ensures expected assignment of v3 to its nearest cluster c3 , it also improves memory and time efficiency during index builds. C. Parallelism We further accelerate the partitioning algorithm using multithreading on the CPU, primarily in the following three components: (1) The distance computation between vectors and centroids can be executed in parallel. (2) The assignment of multiple vectors can be processed simultaneously. (3) The data distribution of multiple clusters can be updated concurrently. Previous work such as DiskANN only leveraged multithreading for the distance computation between vectors and centroids. One reason for this limitation is that, although using multiple threads can significantly speed up vector assignment and data partitioning, it also results in a non-deterministic processing order. That is, the order in which vectors are processed and written into data shards becomes random, thus the arrangement of vectors within each shard no longer matches the order in the original dataset. During shard-level
TABLE III DATASET. Sift100M Deep100M MicrosoftTuring100M Laion100M Sift1B
Size 100,000,000 100,000,000 100,000,000 100,000,000 1000,000,000
TABLE IV S IFT 100M I NDEX T IME ( S ) AT D IFFERENT S ELECTIVITY ϵ. Dimension 128 96 100 768 128
Data Type uint8 float float float uint8
index merging, DiskANN relies on sequential disk reads to efficiently utilize read buffers. If the vector ordering is inconsistent across data shards, it leads to index information being read and merged incorrectly. To address this, we extend the original implementation by adding a simple buffer state check, enabling us to safely support random disk reads while still maintaining efficient buffer utilization. This ensures that the vector reading order during index merging matches the true original vector order. VI. E XPERIMENTS Our default experimental setup includes a 40-core 80-thread Intel(R) Xeon(R) Gold 6133 CPU @ 2.50GHz with 251G RAM and 2T SanDisk SDSSDH3, and the Tesla V100-SXM216GB GPU(s) with a total of 5120 threads. In our experiments, we compare four different implementations: • ScaleGANN: Our proposed GPU-based system for largescale ANNS index construction where the dataset is selectively replicated and partitioned, followed by parallel block-wise GPU index construction, and finally merging of shard indexes. Queries are served on CPUs for high throughput and low latency. • GGNN: A state-of-the-art GPU-based ANNS system designed for large-scale datasets. It partitions the dataset without replication, constructs a graph index for each block independently, and performs queries on each block separately. Final results are obtained by merging and ranking the per-block query results. • Extended CAGRA: A baseline adaptation based on CAGRA, a cutting-edge GPU ANNS system for small datasets. We extend it using GGNN’s block-partitioning and block-wise querying approach to enable it to handle large-scale datasets. For each block, Extended CAGRA performs graph index construction and querying, followed by result aggregation and re-ranking. • DiskANN: A leading CPU-based ANNS solution for largescale datasets. It replicates and partitions the dataset, constructs a graph index for each block on CPU, and merges these indexes into a global index. Queries are executed on the merged index. The datasets used in our experiments are listed in Table III. Sift, Deep, and SimSearchNet (with query sets) are from the BIGANN benchmarks [33]. Laion100M is a sampled subset of Laion5B [32], [34], and the query set is created by sampling 10,000 items from Laion5B, following VectorDBBench [35]. In principle, our framework is capable of scaling to the full
ScaleGANN Proportion Overall Time (s) Build-Only Time (s)
ϵ = 1.1 33.3% 4216 2220
ϵ = 1.2 54.3% 4726 2570
ϵ = 1.5 81.8% 3428 3025
Original 100% 5837 3564
Laion5B dataset, provided sufficient disk space is available. However, due to the computational demands and hardware limitations, processing the entire dataset would require prohibitively long runtimes on our current setup. Therefore, for experimental analysis, we sample 100M vectors, which already requires 2.5 times more raw storage than Sift1B. More importantly, since index construction time scales linearly with dataset size [11], [18], [19], results on 100M-scale datasets can serve as reliable estimates for billion-scale performance. Codes and results are available in an anonymous repo [36]. A. Overall Result In this section, we illustrate the effectiveness of our partition with selective replication based on ScaleGANN and the other partition-and-merge approach DiskANN. Then we present the build and search results of four benchmarks, and comprehensively analyze ScaleGANN’s performance in both indexing and querying. 1) Selective Vector Partitioning: Compared to DiskANN’s default setting where each vector is replicated once, we show a wise choice of selectivity ϵ can reduce 20%-70% vector replication, thus saving disk and memory usage, reducing data processing and indexing time. While accelerating the index build, the search quality is maintained or even improved instead of trading off one for the other. Table IV presents ScaleGANN’s build performance under different selectivity ϵ. ”Proportion” denotes the percentage of replicated input vectors, while ”Overall Time” and ”BuildOnly Time” represent the total indexing time and shard indexing time respectively (excluding both partitioning and merging). In addition, Figure 3 illustrates ScaleGANN’s corresponding query performance under varying duplication rates. As the replication proportion decreases, we can save more index build time. In particular, ”Build-Only Time” shows an even near-linear reduction corresponding to the decrease in overall data size. Interestingly, a moderate choice of ϵ can maintain or even improve query quality at the same time. At ϵ = 1.1 with a replica reduction of up to 66.7%, both search latency and query per second are improved, due to the elimination of assigning distant vectors to clusters during replication explained in Section V-B. Besides, when applying this approach to DiskANN’s Vamana index, the conclusion still holds, which is also shown in Figure 3. This further demonstrates the generality of our selective duplication across different indexing algorithms. 2) Indexing Time and Quality: We compare the index construction time of all the benchmarks on a single machine (CPU/GPU) with a 16 GB memory budget, as shown in Table V. Corresponding search efficiency of these indexes are
20000 10000
Query Per Second
75
80
85
90
95
Recall@10 DiskANN
100
E=1.1 E=1.2 E=1.5 Original
30000 20000 10000 85
90
95
100
Average Latency (ms)
E=1.1 E=1.2 E=1.5 Original
Average Latency (ms)
Query Per Second
ScaleGANN 30000
ScaleGANN
20
E=1.1 E=1.2 E=1.5 Original
15 10 5 75
15 10
80
85
90
95
Recall@10 DiskANN
100
E=1.1 E=1.2 E=1.5 Original
5 85
90
95
Recall@10 Recall@10 Fig. 3. Sift100M Search Quality at Different Selectivity ϵ.
100
TABLE V I NDEX C ONSTRUCTION T IME ( S ). Dataset Sift100M Deep100M MSTuring 100M Laion100M Sift1B
Overall Build-Only Overall Build-Only Overall Build-Only Overall Build-Only Overall Build-Only
Extended CAGRA 1790 1693 1775 1673 2063 1871 5483 3850 18155 17362
GGNN 1287 1287 2004 1840 10977 10744 44735 43131 13899 13025
DiskANN 9597 7848 21159 19155 20221 18089 62109 57163 119039 83732
ScaleGANN 4727 2570 5222 2797 6672 3480 11259 6504 70617 27676
provided in Figure 4 and Figure 5, fairly based on a unified CPU query algorithm following DiskANN’s search strategy. In Table V, the default build degree and intermediate build degree are 64 and 128, which is the widely adopted setting for large datasets. For GGNN, we adopt a build degree of 20 for Sift and 24 for Deep, following the settings in its paper. During partition, DiskANN and ScaleGANN allows one replication for a vector while ScaleGANN uses a selectivity factor of ϵ = 1.2 to remove unnecessary replicas. For Extended CAGRA and GGNN, datasets are naively splitted without vector replication. We propose two metrics ”Overall Time” and ”Build-Only Time” for a comprehensive performance comparison. For DiskANN and ScaleGANN, the overall index construction time includes data partitioning, shard index construction and index merging. While for CAGRA and GGNN, only partitioning and shard indexing are considered in overall time. Besides, the ”Build-Only” times represent the shard indexing time only for all the approaches, excluding both partitioning and merging. For search experiments, due to limited space, we compare only the top-10 recall with query per second (QPS) and average latency as in Figure 4. For high-dimensional large-scale Laion100M, we perform a disk-based search in Figure 5, and use the average number of distance computed as a proportional proxy for both QPS and latency. Though we could compress Laion100M using vector quantizations and thus enable inmemory search, search optimization is not the focus of this work. Therefore, we leave it for future search enhancements. ScaleGANN vs Extended CAGRA and GGNN. We first compare the partition-and-merge based ScaleGANN with splitonly Extended CAGRA and GGNN, where all approaches use
GPU for index construction acceleration. With selective vector replication and index merging, ScaleGANN substantially improves search performance without introducing prohibitive index construction overhead. Both Extended CAGRA and GGNN exhibit higher search latency and significantly lower QPS than ScaleGANN at equivalent recall. For example, as in Figure 4, at 95% recall, the two split-only methods incur over 3× higher latency and achieve roughly only 1/3 the QPS of the split-and-merge methods. The results on Laion100M in Figure 5 confirm the same trend. Note that for split-only methods, though GPUbased querying can potentially boost the QPS, latency and excessive vector reads still remain to be bottlenecks without index merging. ScaleGANN’s indexing time is better than GGNN if at the same build degrees, with up to 4x overall improvement on Laion100M. However, GGNN can be faster on lowdimensional datasets like Sift100M, Deep100M and Sift1B, where GGNN builds the graph index using small build degrees (20 and 24, respectively). Notably, if both were configured with the same build degree of 64, GGNN’s build time would increase by nearly 5×, making it slower than ScaleGANN. Compared to Extended CAGRA, ScaleGANN requires roughly 2–3× the total construction time, mainly because the dataset is duplicated to ensure shard connectivity, effectively doubling its size and processing time, along with additional disk-based complex data partitioning and index merging. This overhead is magnified in Sift1B given increased slow disk operations. However, since ScaleGANN performs a selective replication to to minimize vector replication, the build-only time which reflects only the graph index construction time on GPU is always less than 2× that of CAGRA. This strategy also reduces the time of partitioning and merging to a certain extent, benefited by saved computation, disk read and write. ScaleGANN vs DiskANN. We then compare the GPUbased ScaleGANN with CPU-based DiskANN, both adopting the split-and-merge strategy. Compared to DiskANN, ScaleGANN achieves an significant overall speedup in index construction, and up to 5.5× overall acceleration on high-dimensional Laion100M. This improvement stems from two key factors: (1) the use of GPU acceleration, which significantly improves distance computation efficiency in high-dimensional spaces, and (2) our selective replication strategy, which reduces unnecessary data duplication to lower data processing and indexing overhead. Meanwhile, since both DiskANN and ScaleGANN rely on CPU and costly disk-based implementations for partitioning and merging large datasets, which incur similar and nonnegligible overhead towards the ”overall” time. Therefore, if isolating the shard index construction stage, the actual index build-only time speedup of ScaleGANN over DiskANN increases to almost 9x. Importantly, ScaleGANN is anticipated to maintain its advantage on other billion-scale datasets instead of just Sift1B, since the ”build-only” indexing time scales approximately linearly with dataset size. Though the ”overall” time of Scale-
85
90
Recall@10 Sift100M
95
30 20 10 0
80
85
90
Recall@10
95
10000
100
Naive CAGRA GGNN DiskANN ScaleGANN
40
20000
100
Average Latency (ms)
80
GGNN DiskANN ScaleGANN Naive CAGRA
30000
0
75
80
80
85
90
Recall@10 Deep100M
95
40 20 0
75
80
85
90
Recall@10
100000 50000 0
82.5 85.0 87.5 90.0 92.5 95.0
Recall@10
95
100
GGNN DiskANN ScaleGANN Naive CAGRA
20000 15000
Laion100M 105 104
Naive CAGRA GGNN DiskANN ScaleGANN
82.5 85.0 87.5 90.0 92.5 95.0
Recall@10
Fig. 5. Search Performance of Laion100M.
10000 5000
100
Naive CAGRA GGNN DiskANN ScaleGANN
60
ScaleGANN 9477 11259 16311
Naive CAGRA GGNN DiskANN ScaleGANN
MicrosoftTuring100M Query Per Second
10000
Query Per Second
20000
0
DiskANN 29309 62109 149065
Deep100M GGNN DiskANN ScaleGANN Naive CAGRA
30000
Average Latency (ms)
Query Per Second
Sift100M
GGNN 20309 44735 49708
Avg # of Dist
Extended CAGRA 5022 5483 7142
Average Latency (ms)
Graph Degree R=32, L=64 R=64, L=128 R=128, L=256
Laion100M
150000
Log (Avg # of Dist)
TABLE VI OVERALL C ONSTRUCTION T IME ( S ) OF L AION 100M.
0
125 100 75 50 25 0
75
80
85
90
95
Recall@10 MicrosoftTuring100M Naive CAGRA GGNN DiskANN ScaleGANN
75
80
85
90
Recall@10
95
Fig. 4. Search Performance of Low-dimensional Datasets.
GANN indicates potential improvement space for disk-based data processing procedures in the future. Besides, though under the current settings, ScaleGANN’s search performance is slightly worse than DiskANN’s, this is mainly due to differences between the indexing algorithms, instead of trading-off the search performance for construction time. DiskANN uses Vamana graph, while CAGRA builds KNN graphs. However, this is orthogonal to our framework which actually can integrate with any of these indexing methods. In fact, search performance of the same given index can even be improved by adjusting ScaleGANN ’s parameters, especially the selectivity factor ϵ which should be tuned for different datasets and is further explored in Sec VI-A1. B. Results under Various Settings 1) Increased Build Degree: According to Table VI, we observe an increase on the overall index construction time as build degree becomes large, though the growth rate varies across different methods considering their different data processing overhead. Under a larger index degree, the GPU based approaches can bring larger acceleration due to the increased proportion of distance computation tasks. At the same time, ScaleGANN with selective replication maintains its affordable replication overhead (∼2x) compared to Extended CAGRA, and performs better than GGNN. On Laion100M, for instance, when the build degree is set to 128 and the intermediate degree is set to 256, ScaleGANN achieves up to 9× overall speedup over DiskANN, and 3x over GGNN. 2) Multi-GPU parallelism: Multi-GPU parallelism can further accelerate index construction. As shown in Table VII, using 2 and 4 V100 GPUs achieves near-linear speedup for shard index build stage compared to a single GPU under the same build parameters R = 64, L = 128 and ϵ = 1.2. Note that speedup is not exactly linear due to system overhead and uneven shard sizes. However, if with larger datasets and more
TABLE VII I NDEX B UILD -O NLY T IME ( S ) OVER GPU PARALLELISM . 1 GPU 2 GPU 4 GPU
Sift100M 2570 1495 877
Deep100M 2797 1557 882
MSTuring100M 3480 1992 1158
Laion100M 6504 3394 2003
shards, task distribution could become more balanced, and the acceleration could become ideal scaling. This confirms that our graph index construction framework which divides the workload into many small and independent tasks is highly suitable for multi-GPU parallelism. Each GPU will independently process one or more data shards, while each separate shard construction takes only a few minutes. For example, with Sift100M, the dataset is divided into 16 shards, each taking approximately 160 seconds to build. In this case, if using 4 GPUs, each GPU handles 4 shards in average, leading to efficient parallel construction. This design further makes our system naturally adaptable to cloud-native spot instance environments where small and fast tasks can be flexibly scheduled across dynamic cheap GPU resources. C. Spot Instance Cost Analysis Lastly, we provide a simple cost analysis of DiskANN and ScaleGANN based on the cost model in Sec IV. In this study, DiskANN uses a regular CPU machine with similar conditions to our local machine, while ScaleGANN uses one GPU spot instance (with 4 V100 GPU cards) for shard index construction and the same CPU machine for partitioning and merging. According to AWS ECS [22], a regular Linux CPU machine with around 80 threads, 200G RAM and 2T disk (e.g., c5d.24xlarge) is at $3.9-4.6/h, while a Linux GPU machine with 4 16G V100 (e.g., p3.8xlarge) has regular price $13.7/h and spot instance price changing normally between $1.223.67/h. While all the instances offer at least 10Gbps network bandwidth, we estimate the total data transfer time as: number of shards × 16GB / network bandwidth. This is because each shard transfer task consists of shard data sent to GPU and the index returned to CPU, which involves at most 16GB data bounded by the GPU memory. Using Laion100M index construction in Table V as an example, it generates less than 100 shards, indicating a 1600G upper bound for data transfer amount and correspondingly at most 160s, namely 0.045h, data transfer time. Besides, we observe that DiskANN’s overall build time is 17.25h in Table V, while Laion100M takes 0.56h to build the index using 4 V100 parallelism in Table VII. Then we also obtain ScaleGANN’s
partition and merge time calculated by its overall time minus the index build-only time, which is 1.32h as shown in Table II. Thus, the overall build time of ScaleGANN is 1.88h (0.56h+1.32h). Therefore, the cost estimate for DiskANN with regular CPU is at least $67.3 (17.25×3.9), while ScaleGANN costs at most $11.1 ((1.88+0.045)×4.6+(0.56+0.045)×3.67) which is even 6x cheaper than DiskANN. Notably, in this scenario, even on-demand cloud GPUs can be more cost-effective than CPUs. This is primarily due to the efficiency of GPU acceleration on high-dimensional datasets, which substantially reduces runtime and, consequently, the overall cost. For low- and mid-dimensional datasets, using GPU spot instances still offers indexing speedups while greatly lowering the cost. Moreover, although older regular GPUs are already relatively affordable, newer GPUs with larger memory and more threads enable faster and more stable indexing by reducing the number of shards and speeding up distance computations. In such cases, spot instances of the latest GPUs can achieve better performance at the same or even lower cost than older regular GPUs. VII. R ELATED W ORK Storage Management. To serve large-scale vector indexing and search, DiskANN [16] offloads data to disk and preserves 10-20% memory for efficiency. Starling [17] further reorders the disk layout to improve locality and reduce search disk access. Besides, LM-DiskANN [37] and AiSAQ [38] propose disk-only designs that do not rely on memory in extreme senarios. Alternative ANNS systems including SPANN [39] and FusionANNS [40] adopt IVF indexes for disk-resilient design. In particular, FusionANNS optimize index build on CPUs by reducing random I/O via layout and I/O de-duplication. Furthermore, some ANNS systems offload data to emerging memory devices such as PMEM [41], CXL [42], UPMEM PIM [24], and SmartSSD [43]. All are orthogonal to our study. Acceleration. Distance calculation can be accelerated through CPU parallelism (e.g., DiskANN [16]) or GPU parallelism (e.g., GANNS [21] and CAGRA [11]), though the latter is constrained by memory of a single GPU. Besides, asynchronous GPU data transfer help hide transffering time [44], [45], while quantization techniques [46] (e.g. PQ, SQ, and PCA) further reduce memory footprint and trade some accuracy for speed. For large datasets across multiple machines, methods explore partitioning, multi-shard parallelism, and load balancing: examples include GPU-based GGNN, CPU-based Starling [17], and distributed shard builds in SOGAIC [47]. ScaleGANN adopts a more flexible, cost-efficient approach by leveraging GPU spot instances in parallel while maintaining a CPU union index to balance efficiency and cost. Graph Update. Streaming scenarios with frequent vector updates (insertions and deletions) motivate specialized ANNS systems: SPFresh [48] extends SPANN, while IPDiskANN [49] and FreshDiskANN [50] enhance DiskANN with update capabilities. However, as changes and updates
accumulate over time, index rebuilding is still necessary to maintain search quality, especially for graph-based indices. Systems with spot instances. Spot instances are widely employed on various workloads for cost-effectiveness, such as ML training [51], MapReduce tasks [52], and MPI applications [53]. Specifically, recent AI serving systems like SkyServe [54] and SpotServe [25] consider spot GPU instances, with LLM specific parallelization configurations. Meanwhile, mechanisms [55]–[57] of check-pointing, migration and node replicas are proposed to handle unexpected terminations of spot instances. To the best of our knowledge, ScaleGANN is the first ANNS graph indexing system to exploit spot GPU instances for both cost efficiency and performance. VIII. C ONCLUSION In this paper, we propose an end-to-end GPU-based cloudnative ANNS graph index construction framework, ScaleGANN, that is highly efficient, scalable, and cost-effective. We enhance ScaleGANN’s disk-resident extendable partition-andmerge strategy with adaptive vector assignment and selective replication, optimizing time and storage efficiency while preserving the overall search quality. In addition, ScaleGANN’s framework with a novel resource allocation strategy achieves both efficiency and cost-effectiveness. We use spot GPUs exclusively for the one-time computation-intensive shard indexing tasks which are also compatible to multi-GPU parallelism, while still leaving partitioning, merging and longterm querying on CPUs. Lastly, while our framework can be integrated with any graph index build algorithm, in this paper we apply CAGRA to our implementation. Experiment results show that our approach can bring up to 9x acceleration at a even lower cost compared with DiskANN, while maintaining similar search QPS and latency at the same recall. Our work also lays the foundation for several valuable future directions. A natural extension is to address the instability of spot instances by developing more robust task recovery mechanisms. For example, live migrating unfinished tasks to another instance, or designing checkpoint-based task resuming methods to avoid full re-execution upon interruption. Additionally, our current setup assumes homogeneous spot instance types, Therefore, it opens up opportunities for specific designs for task re-allocation and cost analysis under heterogeneous settings with available instances varying in GPU memory size and compute capacity. Lastly, our approach demonstrates how cost-effective, pay-as-you-go cloud resources can be leveraged to complete one-time, compute-intensive ANNS index construction, encouraging further exploration of cloud-native or serverless solutions for scalable vector search. R EFERENCES [1] M. Flickner, H. Sawhney, W. Niblack, J. Ashley et al., “Query by image and video content: The qbic system,” computer, vol. 28, no. 9, pp. 23– 32, 1995. [2] M. Wang, X. Xu, Q. Yue, and Y. Wang, “A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search,” arXiv preprint arXiv:2101.12631, 2021. [3] T. Cover and P. Hart, “Nearest neighbor pattern classification,” IEEE transactions on information theory, vol. 13, no. 1, pp. 21–27, 1967.
[4] W. Li, Y. Zhang, Y. Sun, W. Wang et al., “Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement,” IEEE Transactions on Knowledge and Data Engineering, vol. 32, no. 8, pp. 1475–1488, 2019. [5] P. Covington, J. Adams, and E. Sargin, “Deep neural networks for youtube recommendations,” in Proceedings of the 10th ACM conference on recommender systems, 2016, pp. 191–198. [6] R. Chen, B. Liu, H. Zhu, Y. Wang et al., “Approximate nearest neighbor search under neural similarity metric for large-scale recommendation,” in Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022, pp. 3013–3022. [7] D. Liu, M. Chen, B. Lu, H. Jiang et al., “Retrievalattention: Accelerating long-context llm inference via vector retrieval,” arXiv preprint arXiv:2409.10516, 2024. [8] N. Li, B. Kang, and T. De Bie, “Skillgpt: a restful api service for skill extraction and standardization using a large language model,” arXiv preprint arXiv:2304.11060, 2023. [9] C. Fu, C. Xiang, C. Wang, and D. Cai, “Fast approximate nearest neighbor search with the navigating spreading-out graph,” arXiv preprint arXiv:1707.00143, 2017. [10] Y. A. Malkov and D. A. Yashunin, “Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs,” IEEE transactions on pattern analysis and machine intelligence, vol. 42, no. 4, pp. 824–836, 2018. [11] H. Ootomo, A. Naruse, C. Nolet, R. Wang et al., “Cagra: Highly parallel graph construction and approximate nearest neighbor search for gpus,” in 2024 IEEE 40th International Conference on Data Engineering (ICDE). IEEE, 2024, pp. 4236–4247. [12] Y. Malkov, A. Ponomarenko, A. Logvinov, and V. Krylov, “Approximate nearest neighbor algorithm based on navigable small world graphs,” Information Systems, vol. 45, pp. 61–68, 2014. [13] J. Arthurs, S. Drakopoulou, and A. Gandini, “Researching youtube,” pp. 3–15, 2018. [14] C. Schuhmann, R. Beaumont, R. Vencu, C. Gordon et al., “Laion-5b: An open large-scale dataset for training next generation image-text models,” Advances in neural information processing systems, vol. 35, pp. 25 278– 25 294, 2022. [15] Y. Shi, Y. Sun, J. Du, X. Zhong et al., “Scalable overload-aware graph-based index construction for 10-billion-scale vector similarity search,” ArXiv, vol. abs/2502.20695, 2025. [Online]. Available: https://api.semanticscholar.org/CorpusID:276725449 [16] S. Jayaram Subramanya, F. Devvrit, H. V. Simhadri, R. Krishnawamy et al., “Diskann: Fast accurate billion-point nearest neighbor search on a single node,” Advances in neural information processing Systems, vol. 32, 2019. [17] M. Wang, W. Xu, X. Yi, S. Wu et al., “Starling: An i/o-efficient diskresident graph index framework for high-dimensional vector similarity search on data segment,” Proceedings of the ACM on Management of Data, vol. 2, no. 1, pp. 1–27, 2024. [18] CVPR. (2023) Cvpr 2023 tutorial. [Online]. Available: https://matsui528.github.io/cvpr2023 tutorial neural search/ assets/pdf/billion scale ann.pdf [19] F. Groh, L. Ruppert, P. Wieschollek, and H. P. Lensch, “Ggnn: Graphbased gpu nearest neighbor search,” IEEE Transactions on Big Data, vol. 9, no. 1, pp. 267–279, 2022. [20] W. Zhao, S. Tan, and P. Li, “Song: Approximate nearest neighbor search on gpu,” in 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020, pp. 1033–1044. [21] Y. Yu, D. Wen, Y. Zhang, L. Qin et al., “Gpu-accelerated proximity graph approximate nearest neighbor search and construction,” in 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 2022, pp. 552–564. [22] AWS. (2024) Amazon ec2 spot instances. [Online]. Available: https://aws.amazon.com/cn/ec2/spot/ [23] A. Cloud. (2025) Alibaba cloud elastic compute service. [Online]. Available: https://www.alibabacloud.com/help/en/ecs/user-guide/ what-is-a-spot-instance [24] S. Chen, A. C. Zhou, Y. Shi, Y. Li, and X. Yao, “Memanns: Enhancing billion-scale anns efficiency with practical pim hardware,” arXiv preprint arXiv:2410.23805, 2024. [25] X. Miao, C. Shi, J. Duan, X. Xi et al., “Spotserve: Serving generative large language models on preemptible instances,” in Proceedings of the 29th ACM International Conference on Architectural Support for
Programming Languages and Operating Systems, Volume 2, 2024, pp. 1112–1127. [26] M. Douze, A. Guzhva, C. Deng, J. Johnson et al., “The faiss library,” arXiv preprint arXiv:2401.08281, 2024. [27] M. R. Abbasifard, B. Ghahremani, and H. Naderi, “A survey on nearest neighbor search methods,” International Journal of Computer Applications, vol. 95, no. 25, 2014. [28] T. Liu, A. Moore, K. Yang, and A. Gray, “An investigation of practical approximate nearest neighbor algorithms,” Advances in neural information processing systems, vol. 17, 2004. [29] C. Fu and D. Cai, “Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph,” arXiv preprint arXiv:1609.07228, 2016. [30] K. Hajebi, Y. Abbasi-Yadkori, H. Shahbazi, and H. Zhang, “Fast approximate nearest-neighbor search with k-nearest neighbor graph,” in IJCAI Proceedings-International Joint Conference on Artificial Intelligence, vol. 22, no. 1, 2011, p. 1312. [31] Azure. (2024) Use azure spot virtual machines. [Online]. Available: https://learn.microsoft.com/en-us/azure/virtual-machines/spot-vms [32] “Laion5b,” https://laion.ai/blog/laion-5b/. [33] “Big ann benchmarks,” https://big-ann-benchmarks.com/neurips21.html. [34] “Laion5b data,” https://the-eye.eu/public/AI/cah/laion5b/embeddings/ laion1B-nolang/img emb/. [35] “Vectordbbench,” https://github.com/zilliztech/VectorDBBench. [36] Anonymous. (2025) Scalegann anonymous code repo. [Online]. Available: https://github.com/AnonymousAuthor1111/ICDCS26 [37] Y. Pan, J. Sun, and H. Yu, “Lm-diskann: Low memory footprint in disknative dynamic graph-based ann indexing,” in 2023 IEEE International Conference on Big Data (BigData). IEEE, 2023, pp. 5987–5996. [38] K. Tatsuno, D. Miyashita, T. Ikeda, K. Ishiyama et al., “Aisaq: Allin-storage anns with product quantization for dram-free information retrieval,” arXiv preprint arXiv:2404.06004, 2024. [39] Q. Chen, B. Zhao, H. Wang, M. Li et al., “Spann: Highly-efficient billion-scale approximate nearest neighborhood search,” Advances in Neural Information Processing Systems, vol. 34, pp. 5199–5212, 2021. [40] B. Tian, H. Liu, Y. Tang, S. Xiao et al., “Towards high-throughput and low-latency billion-scale vector search via cpu/gpu collaborative filtering and re-ranking,” in FAST ’25: Proceedings of the 23rd USENIX Conference on File and Storage Technologies, 2025, pp. 171–185. [41] J. Ren, M. Zhang, and D. Li, “Hm-ann: Efficient billion-point nearest neighbor search on heterogeneous memory,” Advances in Neural Information Processing Systems, vol. 33, pp. 10 672–10 684, 2020. [42] J. Jang, H. Choi, H. Bae, S. Lee et al., “{CXL-ANNS}:{SoftwareHardware} collaborative memory disaggregation and computation for {Billion-Scale} approximate nearest neighbor search,” in 2023 USENIX Annual Technical Conference (USENIX ATC 23), 2023, pp. 585–600. [43] B. Tian, H. Liu, Z. Duan, X. Liao et al., “Scalable billion-point approximate nearest neighbor search using {SmartSSDs},” in 2024 USENIX Annual Technical Conference (USENIX ATC 24), 2024, pp. 1135–1150. [44] P. Bhatotia, R. Rodrigues, and A. Verma, “Shredder: Gpuaccelerated incremental storage and computation,” in 10th USENIX Conference on File and Storage Technologies (FAST 12). San Jose, CA: USENIX Association, feb 2012. [Online]. Available: https://www.usenix.org/conference/fast12/ shredder-gpu-accelerated-incremental-storage-and-computation [45] T.-Y. Yang, Y. Chen, Y. Liang, and M.-C. Yang, “Seraph: Towards scalable and efficient fully-external graph computation via ondemand processing,” in 22nd USENIX Conference on File and Storage Technologies (FAST 24). Santa Clara, CA: USENIX Association, feb 2024, pp. 373–387. [Online]. Available: https: //www.usenix.org/conference/fast24/presentation/yang-tsun-yu [46] M. Wang, H. Wu, X. Ke, Y. Gao et al., “Accelerating graph indexing for anns on modern cpus,” arXiv preprint arXiv:2502.18113, 2025. [47] Y. Shi, Y. Sun, J. Du, X. Zhong et al., “Scalable overload-aware graphbased index construction for 10-billion-scale vector similarity search,” arXiv preprint arXiv:2502.20695, 2025. [48] Y. Xu, H. Liang, J. Li, S. Xu et al., “Spfresh: Incremental in-place update for billion-scale vector search,” in Proceedings of the 29th Symposium on Operating Systems Principles, 2023, pp. 545–561. [49] H. Xu, M. D. Manohar, P. A. Bernstein, B. Chandramouli et al., “In-place updates of a graph index for streaming approximate nearest neighbor search,” arXiv preprint arXiv:2502.13826, 2025.
[50] A. Singh, S. J. Subramanya, R. Krishnaswamy, and H. V. Simhadri, “Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search,” arXiv preprint arXiv:2105.09613, 2021. [51] J. Duan, Z. Song, X. Miao, X. Xi et al., “Parcae: Proactive,{LiveputOptimized}{DNN} training on preemptible instances,” in 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), 2024, pp. 1121–1139. [52] N. Chohan, C. Castillo, M. Spreitzer, M. Steinder et al., “See spot run: Using spot instances for {MapReduce} workflows,” in 2nd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 10), 2010. [53] M. Taifi, J. Y. Shi, and A. Khreishah, “Spotmpi: A framework for auction-based hpc computing using amazon spot instances,” in International Conference on Algorithms and Architectures for Parallel Processing. Springer, 2011, pp. 109–120. [54] Z. Mao, T. Xia, Z. Wu, W.-L. Chiang et al., “Skyserve: Serving ai models across regions and clouds with spot instances,” in Proceedings of the Twentieth European Conference on Computer Systems, 2025, pp. 159–175. [55] J. Danysz, V. Del Rosal, and H. González-Vélez, “Aws ec2 spot instances for mission critical services,” in Proceedings of the 34th ECMS International Conference on Modelling and Simulation (ECMS 2020). European Council for Modeling and Simulation, 2020. [56] C. Wang, Q. Liang, and B. Urgaonkar, “An empirical analysis of amazon ec2 spot instance features affecting cost-effective resource procurement,” ACM Transactions on Modeling and Performance Evaluation of Computing Systems (TOMPECS), vol. 3, no. 2, pp. 1–24, 2018. [57] K. Kim and K. Lee, “Making cloud spot instance interruption events visible,” in Proceedings of the ACM Web Conference 2024, 2024, pp. 2998–3009.