SPF!

"#$: Incremental In-Place Update for

Billion-Scale Vector Search
Yuming Xu1, 2 Hengyu Liang1, 2 Jin Li3, 1, 2∗ Shuotao Xu2 Qi Chen2 Qianxi Zhang2
Cheng Li1 Ziyue Yang2 Fan Yang2 Yuqing Yang2 Peng Cheng2 Mao Yang2
1 University of Science and Technology of China 2 Microsoft Research Asia 3 Harvard University

Abstract ACM Reference Format:

Approximate Nearest Neighbor Search (ANNS) on high di- Yuming Xu, Hengyu Liang, Jin Li, Shuotao Xu, Qi Chen, Qianxi Zhang,
Cheng Li, Ziyue Yang, Fan Yang, Yuqing Yang, Peng Cheng, Mao Yang.
mensional vector data is now widely used in various appli-
2023. SPF!"#$: Incremental In-Place Update for Billion-Scale Vector
cations, including information retrieval, question answering, Search . In ACM SIGOPS 29th Symposium on Operating Systems Prin-
and recommendation. As the amount of vector data grows
arXiv:2410.14452v1 [[Link]] 18 Oct 2024

ciples (SOSP ’23), October 23–26, 2023, Koblenz, Germany. ACM, New
continuously, it becomes important to support updates to York, NY, USA, 17 pages. h!ps://[Link]/10.1145/3600006.3613166
vector index, the enabling technique that allows for e!cient
and accurate ANNS on vectors.
Because of the curse of high dimensionality, it is often 1 Introduction
costly to identify the right neighbors of a new vector, a nec- Today deep learning models can embed almost all types of
essary process for index update. To amortize update costs, data, including speech, vision, and text information, into
existing systems maintain a secondary index to accumulate multi-dimensional vectors with tens or even hundreds of di-
updates, which are merged with the main index by globally mensions. Such vectors are critical for complex semantic
rebuilding the entire index periodically. However, this ap- understanding tasks [42, 49]. To enable e$ective vector anal-
proach has high "uctuations of search latency and accuracy, ysis, vector nearest neighbor search (NNS) systems have be-
not to mention that it requires substantial resources and is come critical system components for an increasing number
extremely time-consuming to rebuild. of online services like search [35] and recommendation [57].
We introduce SPF!"#$, a system that supports in-place To satisfy the strict query latency requirement for these
vector updates. At the heart of SPF!"#$ is LIRE, a lightweight online services, vector search systems often resort to ap-
incremental rebalancing protocol to split vector partitions proximate nearest neighbor search (ANNS) [17, 22, 34, 51,
and reassign vectors in the nearby partitions to adapt to data 56, 59, 65, 69], to locate as many correct results as possible
distribution shifts. LIRE achieves low-overhead vector up- (i.e., query accuracy). At the heart of a large-scale NNS sys-
dates by only reassigning vectors at the boundary between tem is a vector index, a key data structure that organizes
partitions, where in a high-quality vector index the amount high-dimensional vectors e!ciently for high-accuracy low-
of such vectors is deemed small. With LIRE, SPF!"#$ pro- latency vector searches [3, 9, 14, 38, 58, 67].
vides superior query latency and accuracy to solutions based Like traditional indices, a high-quality vector index orga-
on global rebuild, with only 1% of DRAM and less than 10% nizes a quick “navigation map” of vectors based on the vector
cores needed at the peak compared to the state-of-the-art, proximity in a high dimensional space. The proximity mea-
in a billion scale disk-based vector index with a 1% of daily surements are often implemented with “shortcuts”, which
vector update rate. only exist between a pair of vectors with a short distance.
A search query traverses the datasets based on “shortcuts”
CCS Concepts: • Information systems → Information the result set. The quality of the index for e!cient traver-
storage systems; Information retrieval. sal is highly dependent on the quality of shortcuts, where
insu!cient shortcuts miss relevant vectors, and extrane-
Keywords: Vector Search, Incremental Update, Billion-scale
ous shortcuts incur excessive traversal and storage costs.
For high-dimensional data, vector indices require careful
construction to produce a su!cient amount of high-quality
Permission to make digital or hard copies of part or all of this work for “shortcuts”, often as vector partitions [14, 67] or graphs of
personal or classroom use is granted without fee provided that copies are
not made or distributed for pro#t or commercial advantage and that copies
vector data [56, 65].
bear this notice and the full citation on the #rst page. Copyrights for third- To add fuel to #re, there is a strong desire to support fresh
party components of this work must be honored. For all other uses, contact update of vector indices because current systems generate
the owner/author(s). a vast amount of vector data continuously in various set-
SOSP ’23, October 23–26, 2023, Koblenz, Germany tings. For example, 500+ hours of content are uploaded to
© 2023 Copyright held by the owner/author(s).
ACM ISBN 979-8-4007-0229-7/23/10.
h!ps://[Link]/10.1145/3600006.3613166 ∗ Work done during his #nal-year study at USTC and his internship at MSRA.
SOSP ’23, October 23–26, 2023, Koblenz, Germany Xu et al.

YouTube[21] every minute, one billion new images are up- incur changes in itself and its neighboring partitions. Because
dated in [Link] every day [34], and 500PB fresh unstructured the updates are small, the corresponding changes are most
data are ingested to Alibaba during a shopping festival [69]. likely to be limited in a local region. This makes the entire
Fresh updates require vector indices to incorporate new vec- rebalancing process lightweight and a$ordable.
tors at unprecedented scale and speed while maintaining Despite this opportunity, rebalancing is still non-trivial. In
their high-quality to produce low query latency and high particular, LIRE needs to address the following challenges. 1)
query accuracy of approximate vector searches. In order to keep search latency short, LIRE needs to maintain
However, it is non-trivial for vector indices to maintain an even distribution of partition sizes via timely split and
high-quality “shortcuts” when updating vectors with hun- merge. 2) In order to keep search accuracy high, LIRE needs
dreds of dimensions. Graph-based indices have inherent high to identify the smallest set of vectors that cause data im-
cost to update vectors in place, because each insertion or balance in the index. These vectors should be reassigned to
removal of vector datum often requires examining the entire maintain high index quality. 3) An implementation of LIRE
graph to update the edges in a high-dimensional space. One should be lightweight with negligible performance impacts
silver lining to fast vector index update is that cluster-based on the foreground search.
index, which is less costly to update than the graph-based LIRE tackles these challenges by making the following
index. Vector insertion and removal only require constant four contributions:
local modi#cation to vector partitions(s). Nevertheless, as • LIRE keeps partition size distribution uniform by splitting
updates accumulate per vector partition, the index quality and merging partitions proactively and incrementally.
deteriorates because the data distribution skews over time, • LIRE formally identi#es two necessary conditions for vec-
which makes partition sizes uneven and hence hurts both tor reassignment based on the rule of nearest neighbor
query latency and accuracy [34]. posting assignment (NPA). With the necessary conditions,
Because of the di!culty of running vector index updates LIRE opportunistically identi#es a minimal set of neigh-
in place, existing ANNS system support vector updates [34, borhood vectors to adapt to data distribution shifts.
53, 59, 65] out-of-place, by periodic rebuilding of global in- • An implementation of LIRE is decoupled as a two-stage
dex. A batch of vector updates are accumulated and indexed feed-forward pipeline, which moves the background split-
separately, i.e., out-of-place, and are periodically merged to reassign o$ from the critical path of foreground update.
the base index by rebuilding the entire index. Such practices Each pipeline stage is multi-threaded to saturate the high
introduce signi#cant resource overheads to ANNS systems. IOPS of a high-performance NVMe device.
For example, to build a global DiskANN index for a 128G • An SSD-backed user-space storage engine dedicated to
SIFT dataset with a scale of 1 billion, it would require a peak LIRE, which bypasses legacy storage stack, prioritizes par-
memory usage of 1100GB for 2 days, or 5 days under a mem- tition reads, and optimizes for partition appends.
ory usage of 64GB with 32 vCPUs [56]. Such rebuilding can Experiments show SPF!"#$ outperforms state-of-the-art
even consume more resources than the index serving costs ANNS systems that support fresh updates on all fronts, with
(§2.3). In addition, such an out-of-place update method hurts low and constant search/insert latency, high query accuracy,
the search performance of online services because it follows as well as e!cient resource usages for billion-scale vector
a Log-Structured-Merge (LSM) style for updates [53], which datasets. Instead of an additional 1000GB memory and 32
trades read performance for write optimization. cores needed by DiskANN global rebuild, SPF!"#$ outper-
To scale to large vector datasets with lower costs, this forms DiskANN by 2.41↑ lower tail latency on average with
paper presents SPF!"#$, a disk-based vector index that sup- only 10GB memory and 2 cores. Moreover, SPF!"#$ reaches
ports lightweight incremental in-place local updates with- the IOPS limitation with stable performance and resource
out the need for global rebuild. SPF!"#$ is based on the utilization. It simultaneously reaches peak 4K QPS search
state-of-the-art cluster-based vector index design, capable throughput and 2K QPS update throughput on a single NVMe
of incorporating vector index updates online with low over- SSD disk with 15 cores.
heads while maintaining good index quality for high search
performance and accuracy for billion-scale vector datasets. 2 Background and Related Work
The core of SPF!"#$ is LIRE, a Lightweight Incremental RE-
balancing protocol that accumulates small vector updates of In this section, we present the basic operations in ANNS-
based vector search and introduce two mainstream on-disk
local vector partitions, and re-balances local data distribution
vector indices and their respective index update challenges.
at a low cost. Unlike expensive global rebuilds, LIRE is capa-
ble of maintaining index quality by #xing data distribution
abnormalities locally on-the-"y. 2.1 Vector Search and ANNS
The key design rationale behind LIRE is to leverage a A common use-case of vector search involves #nding the
vector index that is already in a well-partitioned state. Small most similar items in a large dataset based on a given query.
vector updates to a high-quality vector partition may only This process is often used in recommendation systems, search
SPF!"#$: Incremental In-Place Update for Billion-Scale Vector Search SOSP ’23, October 23–26, 2023, Koblenz, Germany

engines, and natural language processing tasks. As shown in 1, 3, 5, 4, ..

Figure 1, to #nd similar images from dataset given a query im- 2, 8, 1, 0, ..

age, the system #rst represents each image in the dataset as a 9, 2, 5, 6, ..

high-dimensional vector through a deep learning model. The Vector

Images Model
query image is also encoded into a vector in the same high- Dataset
dimensional space. Then, the system calculates the similarity Similarity
7, 0, 2, 0, ..

between the query vector and each vector in the dataset us- 8, 0, 2, 1, ..
Calculation 8, 0, 3, 1, ..
ing a similarity metric, such as cosine similarity or Euclidean &Rank
Query Query Related Vector
distance. The system ranks the images based on their similar- Image
Model
Vector & Object
ity scores and returns the top results to the user. Essentially,
the search is to #nd the query vector’s nearest neighbors in
Figure 1. An example of vector search: to #nd the most
a high-dimensional space.
similar images in an image dataset. Query images and data
Formally, given a vector set 𝐿 ↓ R𝐿↑𝑀 containing 𝑀 𝑁-
images are all represented as vectors.
dimensional vectors and a query vector q, vector nearest
neighbor search aims to #nd a vector x↔ from 𝐿 such that
x↔ = arg minx↓X Dist(x, q), where Dist is the similarity met- Example vector index solutions based on #ne-grained
ric discussed above. This de#nition can be extended to 𝑂- graphs include neighborhood-graph based methods [15, 16,
nearest neighbor (KNN) search [67]. Modern machine learn- 19, 20, 23, 38, 60, 63] which organize all the vectors into a
ing models typically generate vectors with dimensions rang- neighborhood graph with each vector connected to its near-
ing from 100 to 10,000, or even more. For example, GPT- est vectors, and hybrid methods [26, 27, 62, 68] which consist
3 generates four sizes of embedding vectors with dimen- of space-partition trees and a neighborhood graph to take
sions ranging from 1024 to 12288 [48]. The high dimen- advantage of both tree and graph data structures. Space-
sionality makes it challenging to #nd the exact 𝑂 nearest partition-tree based methods [4, 6, 8, 10, 13, 18, 36, 39, 43, 45,
neighbors e!ciently [12]. To address this issue, recent sys- 46, 55, 64, 72] can be treated as a special kind of #ne-grained
tems commonly rely on approximate nearest neighbor search graphs. They use a tree to represent the space division and
(ANNS) [51, 56, 67] to make the e$ective trade-o$ across re- the vector to subspaces mapping. Most of these solutions are
source cost, result quality, and search latency, thus scaling based on in-memory implementations for performance and
to large vector datasets. are expensive to scale to billion-scale data-sets.
Due to its approximate nature, search result accuracy be- Only a few #ne-grained graph-based vector indices are
comes an important metric to gauge the quality of a vector optimized for secondary storage (e.g., DiskANN [56] and HM-
index. In ANNS, RecallK@K is commonly used to measure ANN [51]). Similar to external graph systems [31, 33, 52, 74],
result quality. For an approximate KNN query, RecallK@K is these #ne-grained graph-based vector indices are stored in
de#ned as |𝑁|𝑂↗𝑂| | , where 𝑃 is the query’s result set, and 𝑄 is two parts: vertex data and edge data as vertex adjacency lists.
the query’s ground truth result set, |𝑃 | = |𝑄 | = 𝑂. Edge data are stored in secondary storage, and vertex data
are either on disk [51] or in memory [56], where in-memory
vertex data speed up computation, i.e. distance calculation
in the case of ANNS [56].
2.2 Vector Index Organization To reduce search costs, DiskANN [56] employs a #xed
A vector index can be abstracted as a logical graph, where graph traversal strategy, where it caches the neighborhood
a vertex represents a vector, and an edge denotes the close of the #xed starting point in memory to speed up graph tra-
proximity of two vectors in terms of distance. And vector versal in the initial stage. DiskANN further maintains an
indices for ANNS can be categorized into !ne-grained graph- in-memory copy of compressed vertex data (using product
based vector indices and coarse-grained cluster-based vector quantization) to speed up distance calculation during graph
indices. These two methods can be applied to both in-memory traversals. In contrast, HM-ANN [51] constructs a hierarchi-
or on-disk scenarios. cal in-memory graph where it can navigate to the nearest
In this paper, we only focus on on-disk vector indices entry point to the main graph on secondary storage, and
since they are more cost-e$ective for large-scale vector-sets. thus e!ciently identify the target region for nearest vectors.
Meanwhile, they pose a unique challenge for vector updates Although e$ective for vector search, graph-based vertex
since disk writes are much more costlier than DRAM writes. indices are unfriendly to updates (details in §2.3).
Fine-grained graph-based vector indices represent each Coarse-grained cluster-based vector indices organize vec-
vector as a vertex, and an edge exists between two vertices tor indices via clustering, where vectors in close proximity
if they are close in distance. Locating 𝑂 nearest vectors of- are kept in the same partition. Logically, vectors in each
ten involves best-#rst graph traversals, where neighboring partition represent a fully-connected graph, while vectors
vertices are explored in ascending distance order. across di$erent partitions have no edge. Since no explicit
SOSP ’23, October 23–26, 2023, Koblenz, Germany Xu et al.

edge data are required, coarse-grained cluster-based vec- Memory CPU Time
tor indices require much smaller storage. Vector search on 1100 GB 32 cores 2 days
DiskANN
cluster-based vector indices #rst identi#es candidate parti- 64GB 16 cores 5 days
tions by measuring the distance to the partitions’ centroids SPANN 260 GB 45 cores 4 days
and then calculates the 𝑂 nearest vectors from the candidate Table 1. Global rebuild costs of disk-based ANNS indices for
partitions via a full scan. billion-scale datasets.
Coarse-grained cluster-based vector indices include hash-
based methods [14, 24, 28, 32, 44, 50, 54, 61, 70, 71] which use
multiple locality-preserved hash functions to do the vector- 1 1
to-partition mapping, and quantization-based methods [5,
0.8
7, 17, 30, 73] which use Product Quantization(PQ) [29] to 0.98

Recall 10@10
compress the vectors and KMeans to generate the vector-to- 0.6

CDF
0.96
partition mapping codebooks. 0.4
A cluster-based vector index should preserve the balance 0.94 0.2
across partitions to achieve low tail search latency. However,
ANNS indices leveraging locality-sensitive hashing [14, 28, 0.92
1 2 3 4 5
0
0 5 10 15 20 25 30
66, 70, 71] and k-means [37] for clustering pay less atten- Latency (ms) Latency (ms)
tion to partition balance. Such ANNS indices often produce Static In-place update
uneven partitions and thus are only adopted by in-memory
systems where the absolute tail latency is much less pro-
Figure 2. Recall and tail latency in two system settings,
nounced than that of an on-disk solution.
namely, static and in-place update. The static setting refers
SPANN [67] is the #rst on-disk vector index that achieves
to an index of 2 million vectors, while the in-place update
low tail search latency through balanced clustering. SPANN
setting refers to an index built by applying 0.5 million vector
divides a vector-set into a large number of balanced parti-
updates to a base index of 1.5 million vectors. The index
tions stored on disk and keeps the centroids of the partitions
system is SPANN, and the dataset is sift [1].
in the memory for quick identi#cation of candidate partitions
during search. It employs several techniques to ensure a well-
balanced partition state (details in §3.1). SPANN achieves To overcome the di!culty of in-place updates, existing
state-of-the-art performance on memory cost, result quality, systems resort to out-of-place updates with periodical global
and search latency across multiple billion-scale datasets. updates. These systems accumulate and index delta vector
Cluster-based vector indices are friendly to updates be- updates in a separate, secondary in-memory index, which
cause each vector insertion or deletion only involves local is periodically merged to the base index by a global index
modi#cations of vector data in the corresponding partition. rebuilding process to maintain good index quality. Many
However, a naive update on local partitions may eventually popular ANNS systems, such as ADBV [69] and Milvus [65],
lead to imbalanced clusters and consequently deteriorate use this method. To defer expensive global updates, Milvus
search tail latency and accuracy (more in §2.3). even introduces multiple delta indices in memory. However,
this approach requires vector search to examine both main
2.3 Freshness Demands and Challenges and secondary indices, which increases resource demands
Modern ANNS systems are required to accommodate billions and hurts search performance. Table 1 shows global rebuilds
of vector updates every day while still preserving low query are both resource-hungry and time-consuming. For exam-
latency and high query accuracy. With the new popular ple, rebuilding a 1-billion vector index [56] for DiskANN, a
OpenAI ChatGPT retrieval plugin [47], some AI applications recent disk-based system, needs 1100GB DRAM, 32 vCPUs,
built atop even require real-time updates to keep up with the for 2 days. When limiting resources to 64GB memory and
updates on their personal documents or contexts, such as 16 vCPUs, the rebuilding time becomes signi#cantly longer,
#les, notes, emails, and chat histories, all in the form of vector, e.g., 5 days for DiskANN. This stressful setting could also
in order to retrieve most relevant snippets as new prompts. lead to a catastrophic drop in query performance because of
However, it is non-trivial for vector indices to maintain index severe computational resource starvation.
quality when updating vectors. Early attempts to in-place update. Compared to out-of-
Out-of-place update. For vector inserts, #ne-grained graph- place vector updates, few systems support in-place updates.
based indices have to connect a new vector to hundreds of Vearch [34] is one of such systems based on cluster-based
neighboring vectors in order to maintain su!cient shortcuts in-memory vector indices, where it inserts a new vector to its
in the high-dimensional space. Deletions of vectors are even nearest partition (a.k.a. posting, the partition is implemented
more expensive as they often involve the total scan of a as a posting list) and supports deletions by maintaining a
unidirectional graph. tombstone bitmap for result #ltering.
SPF!"#$: Incremental In-Place Update for Billion-Scale Vector Search SOSP ’23, October 23–26, 2023, Koblenz, Germany

To understand the impact of Vearch’s design to on-disk

index, we apply Vearch’s design to SPANN, the only partition-
based on-disk vector index system. Figure 2 shows that up-
dating one-third of the vectors degrades the query recall by
more than one point and increases tail latency by 4X, com-
pared to static index building. The reasons are two-fold: 1)
With the growth of the data size, query latency will increase
due to the expansion of the posting length. 2) Since the cen-
troids for each partition are #xed, the recall will decline as
static centroids cannot capture the gradual distribution shift Figure 3. SPANN index data architecture.
in the partition. To conclude, to maintain high index quality
and stabilize search latency, although Vearch and the modi-
#ed SPANN do not require out-of-place data structure, they 3.1 SPANN: A Balanced Cluster-based Vector Index
still require periodical global rebuilds. For instance, Vearch SPANN [67] is a billion-scale cluster-based vector index op-
performs weekly rebuilds. The rebuild overheads might be timized for secondary storage. Figure 3 shows the overall
acceptable for in-memory vector indices. However, for disk- SPANN index structure. SPANN stores the vectors as a large
based indices like SPANN, global rebuilds are expensive, as number of postings∗ on disk, each represents a cluster of
shown in Table 1. close-by vectors. Moreover, SPANN organizes a graph-based
In summary, existing graph-based and cluster-based so- in-memory index, SPTAG [68], for the centroids of all post-
lutions, regardless of in-place or out-of-place, all rely on ings, to quickly identify relevant postings for a query.
periodic global index rebuilding to preserve index quality For a query, it #rst identi#es the closest posting centroids
and stabilize search performance. However, this process en- through the in-memory index, and then loads the corre-
tails considerable resource consumption. sponding postings from disk to memory for further search.
To control the tail latency and maintain high search recall,
2.4 Our Goals SPANN makes postings well balanced by maintaining two
To this date, e!cient fresh update for disk-based vector index key properties. 1) SPANN divides the vectors evenly into a
is still an open challenge. In this paper, we aim to propose a large number of small-sized postings by a fast hierarchical
new disk-based ANNS system to ful#ll the following goals: 1) balanced clustering algorithm, so that each query visits a
low resource cost to maintain the index for large-scale vector similar amount of vectors for bounded search tail latency. 2)
datasets; 2) support high throughput and low latency vector SPANN replicates a few vectors in boundaries across post-
queries for both search and update; and 3) new vectors can ings, which su!ciently maintains high search recalls.
be recalled in high probability. The balanced SPANN index inspires us to propose a new
To achieve this, motivated by the above understandings, lightweight incremental re-balancing (LIRE) protocol. The
we choose to follow the coarse-grained cluster-based ap- intuition here is a single vector update to a well-balanced index
proach to build our on-disk index, but di$er from existing may only incur changes in a local region. This makes the
solutions signi#cantly by avoiding global rebuilds completely. entire rebalancing process lightweight and a$ordable.
The proposed solution, SPF!"#$, performs in-place, incre-
3.2 LIRE: Lightweight Incremental RE-balancing
mental updates in the index data structure to adapt to the
data distribution shift. To this end, SPF!"#$ incorporates A key property of a well-partitioned vector index is the
a Lightweight Incremental RE-balancing (LIRE) protocol, nearest partition assignment (NPA): each vector should be
which e!ciently identi#es a minimal amount of partition put into the nearest posting so that it can be well represented
updates introduced by new vectors for maintaining index by the posting centroid. As continuous vector updates to a
property and thus eliminating visible accuracy loss. Equally posting may degrade query recalls and latency, SPF!"#$ will
importantly, we also address a few system challenges to split a posting after it grows to the preset maximum length.
make LIRE re-balance su!ciently fast and cheap to allevi- However, a naive splitting can violate the NPA property of
ate negative impacts on search latency, in particular, tail the index.
latency. Essentially, LIRE can be considered as an e!cient Figure 4 illustrates a case of NPA violation. Originally,
compaction technique in the high-dimensional space. there were two postings, A and B, near each other, where
the blue dots represent their centroids. At a certain point,
posting A exceeds the length limit upon vector insertions
3 LIRE Protocol Design and is split into two new postings, A1 and A2. The orange
LIRE is built on SPANN [67], the state-of-the-art disk-based dots represent the new centroids of A1 and A2 elected after
vector index system. In this section, we #rst introduce SPANN
brie"y and then elaborate LIRE in detail. ∗We use “posting” and “partition” interchangeably in this paper.
SOSP ’23, October 23–26, 2023, Koblenz, Germany Xu et al.

trigger the split to the target posting. Despite such cascading

e$ects, §3.4 shows that LIRE’s split-reassignment process
will always converge.

3.3 Reassigning Vectors

Figure 4. Posting split violates the NPA property. Reassigning vectors can be expensive, because they require
expensive changes to the on-disk postings for each reas-
signed vector. Thus it is critical to identify the right set
of neighborhoods (neighboring postings) to avoid unneces-
the split. With a naive split, the vectors in posting A will only
sary reassignment. For a merged posting , only vectors from
go to Posting A1 and A2 respectively, based to their distance
deleted posting require reassignment, because the deletion
to new centroids. For illustrative purposes, we assume the
of a centroid does not break NPA compliance of vectors from
yellow dot (a vector) goes to A2.
undeleted postings.
However, the creation of new centroids via a spit makes
On the other hand, a split not only deletes a centroid but
previous NPA-compliance obsolete for vectors in the nearby
creates two new ones. Therefore a split creates more complex
postings, A1, A2 and B. First, the nearest posting of the
scenarios of potential NPA violations. After examining Fig-
yellow dot changes to B, since B’s centroid is closer to the
ure 4, we derive two necessary conditions for reassignment
yellow dot than A2’s centroid. In this case, using the centroid
after splitting, assuming the high-dimensional vector space
of A2 to represent the yellow dot violates NPA. Second, the
is Euclidean.
nearest posting of the green dot, which was B before the
First, a vector 𝑅 in the old posting with centroid 𝑆𝑃 is
split, changes to A2. These two violations degrade the index
required to consider being reassigned if:
quality and result in low recalls.
To #x the NPA violations after splits and maintain the 𝑇 (𝑅, 𝑆𝑃 ) ↘ 𝑇 (𝑅, 𝑆𝑄 ), ≃𝑈 ↓ 1, 2 (1)
high index quality, we design LIRE protocol, which reassigns
where 𝑇 denotes the distance, 𝑆𝑃 represents the old centroid
vectors in nearby postings of a split. At its core, LIRE protocol
before splitting, and 𝑆𝑄 represents any of the two new cen-
consists of #ve basic operations: Insert, Delete, Merge, Split,
troids. This reassignment condition means that if the old
and Reassign.
(deleted) centroid 𝑆𝑃 is the closest centroid to the vector
Insert & Delete: LIRE directly inserts a new vector to the 𝑅, compared to new centroids (𝑆1 and 𝑆2 ), then it cannot
nearest partition following the original SPANN index design. be ruled out the possibility that 𝑅 is closer to a centroid of
LIRE also ensures the deleted vectors will not appear in some nearby posting than new centroids (e.g., 𝑉 in Figure 4).
the search results and will eventually be removed from the Note that this is a necessary condition. On the contrary, if
corresponding postings. 𝑇 (𝑅, 𝑆𝑃 ) > 𝑇 (𝑅, 𝑆𝑄 ), this shows 𝑅 is having a better centroid
Note that Insert and Delete are external interfaces exposed than the old one. In this case, the neighboring certroid (e.g., 𝑉)
to users. The remaining three operations are internal inter- cannot be better than the new ones, i.e., 𝑇 (𝑅, 𝑉) > 𝑇 (𝑅, 𝑆𝑄 )
faces and thus are oblivious to users. These three operations based on the NPA property of 𝑇 (𝑅, 𝑉) > 𝑇 (𝑅, 𝑆𝑃 ). Thus there
work together to keep the size of the posting small and bal- is no need to check reassignment in this case.
anced and to ensure vectors are assigned to the right posting, Second, a vector 𝑅 in the nearby posting with centroid 𝑉
following the NPA property. needs to consider being reassigned if:
Split: When a posting exceeds a length limit, LIRE evenly
splits the oversized posting into two smaller ones. As intro- 𝑇 (𝑅, 𝑆𝑄 ) ↘ 𝑇 (𝑅, 𝑆𝑃 ), ⇐𝑈 ↓ 1, 2 (2)
duced in the previous section, vectors in the neighboring This is a necessary condition for a vector in posting 𝑉 to be re-
postings may violate the NPA property after the split. Thus, assigned to a newly split posting with centroid 𝑆𝑄 . Equation 2
a reassign process (detailed in §3.3) will be triggered for the suggests 𝑅’s new neighboring centroids are getting closer
vectors in the split postings as well as nearby postings. (better) than the old (deleted) one. Therefore it is necessary
Merge: When a posting size is smaller than a lower threshold, to check if the new and closer centroids are in fact closer
LIRE identi#es its nearest posting as candidates for merging. than 𝑅’s existing centroid B (the blue dot w.r.t the green dot
In particular, LIRE’s merge process deletes one posting with in Figure 4). On the other hand, if the two new centroids
its centroid (e.g., the shorter posting), and appends them to are farther away from any vector 𝑅 outside the old posting,
the other posting directly. After that, a reassign process is this means the two centroids are worse than the old one 𝑆𝑃 ,
required for the vectors of the deleted posting because the which is already farther away than 𝑅’s existing centroid. In
deletion of their old centroid might break the NPA rule after this case, there is no need to check the reassignment of 𝑅.
being merged with the other posting. Reassignments will Hence the necessary condition.
not induce splits of the merged posting because vectors can According to the two necessary conditions, a complete
only be reassigned out. However, a reassigned vector may checking process would be extremely expensive, because it
SPF!"#$: Incremental In-Place Update for Billion-Scale Vector Search SOSP ’23, October 23–26, 2023, Koblenz, Germany

requires computing and comparing 𝑇 (𝑅, 𝑆𝑃 ) and 𝑇 (𝑅, 𝑆𝑄 ), 𝑈 ↓

1, 2 for all vectors in the dataset. To minimize the cost, LIRE Memory
only examines nearby postings for reassignment check by SPTAG Index
selecting several 𝑆𝑃 ’s nearest postings, over which two con-
Foreground Read Background Modify Read
dition checks were applied to generate the #nal reassign set.
Experiments in Section 5 show empirically that only a small Updater Local Rebuilder
VID 1 2 3 4 ... Job Queue Send LR Jobs
number of nearby postings for the two necessary condition
Searcher (Split/Reassign)

checks is enough to maintain the index quality. Version Map Threads

After obtaining vector candidates for reassignment, LIRE Version

7bits
Valid
1bit Read
Send LR Jobs
executes the reassignment. For vector candidate 𝑅, LIRE #rst (Split/Merge) &
Read Write Write
searches 𝑅’s new closest posting , then performs NPA check
to get rid of false-positives: if a vector actually does not need Block Controller
reassignment, the reassign operation is aborted. Otherwise, Read Write

LIRE appends 𝑅 in the newly identi#ed posting that is NPA-

compliant and then deletes 𝑅 in the original posting. Storage

3.4 Split-Reassign Convergence

Figure 5. SPF!"#$ architecture (LR means Local Rebuild).
In this section we prove that a split-reassign action to the
vector index, despite the potential of triggering cascading
split-reassign actions, will converge to a #nal state and ter- • |𝑋𝑄+1 | = |𝑋𝑄 |+1: Each split action will delete an old centroid
minate in #nite steps. We #rst formally de#ne the states of from 𝑋𝑄 , and adds two new centroids to it. Therefore, the
vector index and the events triggering state transitions. Then cardinality of 𝑋 always increases by one per split action.
we prove that state transition will converge and terminate. Based on Property 2, |𝑋𝑄+𝑋 | = |𝑋𝑄 | + 𝑎 . And according to
Index State: The state of a vector index for a vector data-set Property 1, 𝑎 ↘ 𝑊 ⇒ |𝑋𝑄 | because |𝑋𝑄+𝑋 | ↘ 𝑊 . Since |𝑊 | is
𝑊 comprises of two parts. #nite, 𝑎 must also be #nite. Therefore the split action must
terminate in #nite steps. ↭
𝑋 : set of posting centroids. (3)

𝑌 : vector membership to centroid(s). (4)

4 SPF!"#$ Design and Implementation
4.1 Overall Architecture
According to LIRE, given 𝑋, each vector in 𝑌 is assigned to
Figure 5 shows the system architecture of SPF!"#$. SPF!"#$
its nearest centroid in 𝑋, i.e., 𝑌 is uniquely determined by 𝑋.
reuses the SPANN SPTAG index (depicted in Figure 3) for
Index-State Transitions: The state transition is triggered fast posting centroid navigation as well as its searcher to
by two types of events: serve queries. It further introduces three new modules to
𝑍𝑄𝐿𝑅𝑆𝑇𝑈 : a vector 𝑅 is inserted into the vector index. (5) implement LIRE, namely, a light-weight In-place Updater, a
low-cost Local Rebuilder, and a fast storage Block Controller.
𝑍𝑉𝑆𝑊𝑆𝑈𝑆 : a vector 𝑅 is deleted into the vector index. (6) Updater appends a new vector at the tail of its nearest post-
ing and maintains a version map to keep track of vector
A reassign of vector 𝑅 is considered as an 𝑍𝑉𝑆𝑊𝑆𝑈𝑆 of 𝑅 followed deletion by setting a corresponding tombstone version to
by an 𝑍𝑄𝐿𝑅𝑆𝑇𝑈 of 𝑅. Note that an event will change the state of prevent deleted vectors from appearing in the search results.
𝑌, however it would not necessarily alter the state of 𝑋. The map is also used to trace the replica of each vector. By
Also note that only an event 𝑍𝑄𝐿𝑅𝑆𝑇𝑈 may incur a split action increasing the version number, it marks the old replicas as
of the vector index, which alters the state of 𝑋 and subse- deleted. The system keeps a global in-memory version map
quently 𝑌. Since 𝑋 uniquely determines 𝑌, we can only and stores vectors along with the version number on disk. A
focus on the state change of 𝑋. vector is stale if the in-memory version number is greater
Split-Reassign Convergence Proof: 𝑍𝑉𝑆𝑊𝑆𝑈𝑆 may eventually than that on the disk. This can be used for garbage collection
trigger a merge during a search process (according to LIRE), caused by reassignment. The use of version can defer and
and the merge obviously will terminate. batch the garbage collection so as to control the I/O overhead
Suppose an 𝑍𝑄𝐿𝑅𝑆𝑇𝑈 triggers a sequence of changes of 𝑋, of vector removal. After vector insertions are completed in-
denoted as 𝑋𝑄 ,𝑋𝑄+1 , ..., 𝑋𝑄+𝑋 . To prove the convergence is to place, the Updater checks the length of the posting and then
show that 𝑎 is a #nite number. sends a split job to Local Rebuilder if the length exceeds the
We note that 𝑋 has the following properties: split limit. The actual data deletions are performed asyn-
• |𝑋 | ↘ |𝑊 |: The cardinality of 𝑋 is bounded and no greater chronously as a batch during local rebuild phase when the
than the cardinality of 𝑊 , i.e., the vector dataset. posting length exceeds the limit.
SOSP ’23, October 23–26, 2023, Koblenz, Germany Xu et al.

Local Rebuilder is the key component to implement LIRE. After splitting, Local Rebuilder puts two new postings back
It maintains a job queue for split, merge, and reassign jobs to the index and deletes the original oversized postings.
and dispatches jobs to multiple background threads for con- Reassign: A reassign job is generated by merge or split jobs.
current execution. It checks if vectors in the new postings and/or their neigh-
• A split job is triggered by Updater when a posting exceeds bors need to be relocated to re-balance the data distributions
the split limit. It cleans deleted vectors in the oversized in the local region. The reassignment check is based on the
posting and splits it into small ones if needed. two necessary conditions in §3.3. Note that neighbor posting
• A merge job is triggered by the Searcher if it #nds some check is not required for merge-triggered reassign.
postings are smaller than a minimum length threshold. It Reassigning a vector without deleting its replicas in the
merges nearby undersized postings into a single one. unexamined postings increases the replica number. This not
• A reassign job is triggered by a split or merge job, which re- only increases storage overheads but also increases split
balances the assignment of vectors in the nearby postings. and reassign frequency since the extraneous replicas take up
When the background split and merge jobs are complete, spaces of postings. In order to e!ciently identify stale vectors
SPF!"#$ will update the memory SPTAG index with the new after reassignment without actual deletes, Local Rebuilder
posting centroids to replace the old one. uses a version map to record the version number for each
Block Controller serves posting read, write, and append vector. A version number takes one byte and is stored in
requests, as well as posting insertion and deletion operators memory to record the version changes of a vector: seven bits
on disk. It uses the raw block interface of SSD directly to for re-assign version and one bit for deletion label. When
avoid unnecessary read/write ampli#cation incurred by some reassigning a vector, we increase its version number in the
general storage engines, such as Log-structured-merge-tree- version map and append the raw vector data with its new
based KV store. Each posting may span multiple SSD blocks, version number to the target posting. All the old replicas
each of which stores multiple vectors (including vector ID, with a stale version number are dropped during the search.
version ID, and raw data). The Block Controller also maintains The replicas will be garbage collected later.
an in-memory mapping from the posting ID to its used SSD
blocks as well as the free SSD blocks pool.
Next, we will discuss the design and implementation of 4.2.2 Concurrent Rebuild. In SPF!"#$, Local Rebuilder is
Local Rebuilder (§4.2) and Block Controller (§4.3) in detail. multi-threaded with e!cient concurrency control of updates
to the in-memory and on-disk data structures. Concurrent re-
4.2 Local Rebuilder Design build can avoid drops of index quality due to slow re-balance.
In order to move split, merge, and re-assign jobs o$ the up- Concurrency Control for Append/Split/Merge: Since ap-
date critical path, SPF!"#$ divides the update process into pend, split, and merge may update the same posting and
two parts, a foreground Updater and a background Local Re- the in-memory block mapping concurrently, We add a #ne-
builder. These two components form a feed-forward pipeline, grained posting-level write lock between these three opera-
where Updater is the producer of requests to the Local Re- tions to ensure a posting change is atomic.
builder. In this pipeline, the background Local Rebuilder is Posting read does not require a lock. Therefore, identifying
a key module that implements merge, split, and reassign vectors for reassignment is lock-free since it only searches
operators of LIRE protocol e!ciently to keep up with the the index and checks the two necessary conditions. Our
foreground Updater. experiments show that even in a skewed workload, write
lock contention is low, i.e., less than 1% contention cases.
4.2.1 Rebuild Operators of LIRE protocol. Local Re- This is because only a small portion of postings are being
builder implements LIRE with three basic operators. edited concurrently.
Merge: To execute a merge job, the Local Rebuilder simply During a reassign process, it is possible that a vector ap-
follows the merge protocol described in §3.2. pends to a stale posting, which happened to be deleted con-
Split: After receiving an oversized posting split job, the Local currently. In such a case, we abort the reassignment and re-
Rebuilder #rst garbage collects deleted vectors in the post- execute the reassign job for this vector. In our experiments,
ing and veri#es whether the posting length after garbage there are only less than 0.001% of total insertion requests
collection still exceeds the split limit. If not, the Local Re- encountering the posting-missing problem caused by split.
builder writes the garbage-collected posting back to storage As a result, the abort and re-execution overhead is minor.
and completes the split job. Concurrent Reassign: SPF!"#$ avoids concurrently reas-
Otherwise, a balanced clustering process is triggered to split signing the same vector at the same time. When collecting
the oversized posting into two smaller ones. In particular, vector candidates for reassignment, Local Rebuilder gathers
Local Rebuilder leverages the multi-constraint balanced clus- the current version of the candidates. Local Rebuilder atomi-
tering algorithm in [67] to generate high-quality centroids cally executes reassignment operations by leveraging atomic
and balanced postings. primitives of compare-and-swapping (CAS) for the version
SPF!"#$: Incremental In-Place Update for Billion-Scale Vector Search SOSP ’23, October 23–26, 2023, Koblenz, Germany

Append: Memory Put: its SSD block o$sets. A posting consists of a list of tuples in
Overwrite
Append v8 to P2 v0,v2,v7,v10,... to P1 the form of <vector id, version number, raw vector>, which
Block Controller typically takes three to four SSD blocks. A block mapping
Block Mapping Free Block Pool entry only consumes 40 bytes of memory. For one billion
P1 B1 B2 B4 Concurrent IO vectors, there only exist 0.1 billion postings. In this case,
P2 B3 B5 B8
[Link] new
blocks
Request Queue block mapping only consumes about 4GB of memory.
Free Block Pool maintains all free SSD blocks. It keeps track
[Link]
[Link] blocks
of the o$sets of all the free blocks to serve disk allocation,
B3 B5 B8
mapping
and garbage collects stale blocks after spilt and reassign.
[Link] blocks [Link] blocks
Concurrent I/O Request Queue is implemented using an
0.1 Read 2.1 Write SPDK circular bu$er, which sends asynchronous read and
write to SSD device for maximized IO throughput and low
B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11
I/O latency.
VID
VID Ver Vector Posting API & Implementation: Block Controller provides
VID Ver
Ver Vector
Vector
Blocks mapped to P1
a set of posting APIs as follows:
Vectors in data
block • GET retrieves posting data by the given ID. The request #rst
Storage looks up the block mapping to identify the corresponding
SSD blocks. Asynchronous I/Os are then sent to the current
Figure 6. SPF!"#$ storage overview. I/O Request Queue. Later, all desired blocks are collected
upon the completion of all I/Os.
• ParallelGET reads multiple postings in parallel to amor-
number. If an atomic CAS operation fails on the vector ver- tize the latency of individual GETs. This ensures fast search
sion map, reassignment is aborted since the vector becomes and update. ParallelGET allows sending a batch of I/O
a stale version. Otherwise, we let the corresponding reassign requests to fetch all the candidate postings, which hides
proceed to the end. the I/O latency and boosts disk utilization.
• APPEND adds a new vector to a posting’s tail. Instead of
4.3 Block Controller Design read-modify-write at the posting-granularity, APPEND only
involves read-modify-write of the last block of a posting,
Block Controller is a light-weight storage engine highly opti-
which reduces the amount of read/write ampli#cation sig-
mized for reading. It o$ers append-only operation on post-
ni#cantly. As shown in Figure ??, APPEND #rst allocates a
ings. This design takes advantage of the characteristics of
new block, reads the original last block if the last block
postings, where old posting data is immutable, and the up-
is not full, appends new values to the values from the
date introduces no additional overheads for reading (unlike a
last block, and then writes it as a new block. After a new
log-structured #le system, where multiple additional out-of-
block is written, it atomically updates the corresponding
place reads are required). It keeps appending vector updates
in-memory Block Mapping entry via a compare-and-swap
to a posting before exceeding a length limit. When a posting
operation to re"ect the change. The old block will be re-
exceeds the length limit, the old posting is destroyed after
leased to the free block pool for later usage.
being split into two new ones. To avoid unnecessary over-
• PUT writes a new posting to SSD. Like APPEND, it allocates
heads in #le systems or other storage engines (e.g., KV store),
new blocks and writes for the entire posting blocks in bulk.
Block Controller operates directly on raw SSD interfaces.
Then it atomically updates the Block Mapping entry. If PUT
SPDK-based Implementation: Figure ?? overviews the stor- overwrites an old posting, it releases old blocks to the Free
age design. Block Controller is implemented on top of SSD. Block Pool.
It leverages the raw block interface o$ered by SPDK [25], a Block Controller provides a common abstraction and imple-
high-performance NVMe SSD library by Intel. SPDK o$ers a mentation, which can be generalized for other read-intensive
set of user-space IO libraries for accessing high-speed NVMe applications (such as widely-used inverted index for search
devices, which allow us to bypass the legacy storage stack engine [2, 11]).
to perform SSD I/Os directly.
Storage Data Layout: As shown in Figure ??, a Block Con-
troller consists of in-memory Block Mapping, a Free Block 4.4 Crash Recovery
Pool, and a Concurrent I/O Request Queue. SPF!"#$ adopts a simple crash recovery solution, which com-
Block Mapping maps a posting ID to its SSD block o$sets. bines snapshot and write-ahead log (WAL). Speci#cally, an
Since the posting ID is a continuous integer, block mapping index snapshot is taken periodically, and all update requests
is implemented as an in-memory dense array, where each between adjacent snapshots are collected into a WAL so that
element stores the block metadata of a posting length and a crash can be recovered from the latest snapshot, followed
SOSP ’23, October 23–26, 2023, Koblenz, Germany Xu et al.

by replaying the WAL. The WAL will be deleted when a new the same settings as in their paper [53]. For update con-
snapshot is generated. #gurations, DiskANN baseline processes streamingMerge,
To take a snapshot for a vector index, we need to record a lightweight global graph rebuild, for every new 30M
both the in-memory and on-disk data structures. For in- vectors, where graph degree 𝑏 equals 64 and insert can-
memory index data, we create snapshots for centroid index, didate list equals 75. For search con#gurations, DiskANN
version maps in Updater, and block mapping and block pool baseline uses the default setting with beamwidth equal to
in Block Controller, and "ush the snapshots to disk. Snapshots 2 and search candidate list L equal to 40 for recall10@10.
are relatively cheap because these data structures take only • SPANN+, a modi#ed version of SPANN [67] which appends
40GB for billion-level dataset, which costs 2~3 seconds for a updates locally to a posting without splitting and reassign-
full "ush on a PCI-e based NVM SSD. For disk data, thanks to ing. This is an append-only version of SPF!"#$ without
our block-level copy-on-write mechanism, we can collect all the Local Rebuilder module.
the released blocks during two snapshots into a pre-release Workloads: Three workloads are used in the experiments.
bu$er, which will be added to the Free Block Pool after the • Workload A simulates a realistic vector update scenario
next snapshot is recorded. Thus all the data blocks modi#ed with 100 million scale of SPACEV vectors. The reason
in the interim can be rolled back to be consistent with the to reduce the scale from 1 billion to 100 million is that
previous snapshot. This solution saves a large amount of disk DiskANN requires several TBs of DRAM to run 1-billion
space since we only delay the space release for old blocks scale fresh updates (shown in Table 1), which exceeds our
during two snapshots. machine’s capacity. In particular, workload A simulates 1%
update daily over 100 days. To generate updates realisti-
5 Evaluation cally, we extract two disjoint SPACEV 100M datasets from
In this section, we conduct experiments to answer the fol- SPACEV1B, where one is used as the base ANNS index
lowing questions: data-set and the other as the update candidate pool. Each
• How does SPF!"#$ compare with state-of-the-art baselines daily update epoch deletes 1% of vectors randomly from
in terms of performances, search accuracy and resource the base ANNS index, and inserts 1% of vectors randomly
usage? (§5.2) selected from the update data pool to the base index.
• What is the maximum performance of SPF!"#$? (§5.3) • Workload B has the same data scale and sampling method
• Can SPF!"#$ solve the data shifting problem illustrated as Workload A but with a 100 million scale of the SIFT
in Figure 2? (§5.4) vector dataset.
• How to properly con#gure SPF!"#$? (§5.5) • Workload C scales up our experiment data-set to be billion-
scale using both the SIFT dataset and the SPACEV dataset.
5.1 Experimental Setup This workload aims at stress testing SPF!"#$, also with a
1% daily update rate.
Platform: All experiments run on an Azure lsv3 [41] VM
instance, which is a storage-optimized virtual machine with Metrics: SPF!"#$ is designed for online ANNS streaming
locally attached high-performance NVMe storage. In partic- scenarios. Thus, our evaluation focuses on the following four
ular, we con#gured the VM with 16 vCPUs from a hyper- categories of metrics.
threaded Intel Xeon Platinum 8370C (Ice Lake) processor • Search Performance: We measure tail (P90, P95, P99, and
and 128GB memory for our experiments. P99.9) latency and query per second (QPS) throughput. In
particular, we have a hard cut of 10ms for SPF!"#$ and all
Datasets: We use two widely-used vector datasets to evalu-
baselines, where the system #nishes the result immediately
ate SPF!"#$:
and returns the current search results.
• SIFT1B [40] is a classical image vector dataset for evalu-
• Search Accuracy: We use the percentage of ground truths
ating the performance of ANNS algorithms that support
recalled by SPF!"#$ system to measure accuracy.
large-scale vector search. It contains one billion of 128-
• Update Performance: insertion and deletion throughputs.
dimensional byte vectors as the base set and 10,000 query
• Resource Usages: the memory and CPU consumption.
vectors as the test set.
• SPACEV1B [1] is a dataset derived from production data
from commercial search engines. It represents a di$erent
form of vector encoding: deep natural language encoding.
It contains one billion of 100-dimensional byte vectors as 5.2 Real-World Update Simulation
a base set and 29,316 query vectors as the test set. In this experiment, we compare all the metrics of SPF!"#$
Baselines: We compare SPF!"#$ with two baselines: with all the baselines on the real-world situation. We use
• DiskANN is the state-of-the-art disk-based fresh ANNS Workload A and B (see §5.1) to simulate 100 days of real-
system [53]. It is based on a graph ANNS index and uses an world updates, and we show that SPF!"#$ outperforms base-
out-of-place update solution. We con#gure DiskANN with lines in all evaluation metrics.
SPF!"#$: Incremental In-Place Update for Billion-Scale Vector Search SOSP ’23, October 23–26, 2023, Koblenz, Germany

Insert Throughput (per Thread) Accuracy Memory Usage

1000 1 120
Throughput (QPS)

800 0.9 100

Memory (GB)
Recall 10@10
80
600 0.8
60
400 0.7
40
200 0.6 20
0 0.5 0
0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100
Batches/Days Batches/Days Batches/Days
SPFresh DiskANN SPANN+
Search P90 Latency Search P95 Latency Search P99 Latency Search P99.9 Latency
20 20 20 20
16 16 16 16
Latency (ms)

Latency (ms)

Latency (ms)

Latency (ms)
12 12 12 12
8 8 8 8
4 4 4 4
0 0 0 0
0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100 0 20 40 60 80 100
Batches/Days Batches/Days Batches/Days Batches/Days

Figure 7. SPF!"#$ overall performance (SPACEV: data distribution shifts over time).

DiskANN SPANN+ SPF!"#$

Insert 3 1 1
delete 1 1 1
5.2.2 Experiment Results. Figure 7 records a daily time
Search 2 2 2
series of the search tail latency, insert throughput per thread,
Background 10 2 2 search accuracy, and memory usage of Workload A. We
Total 16 6 6 can see that SPF!"#$ achieves the best and the most stable
Table 2. Threads allocation for overall performance. performance on all the metrics during the 100 days.
Low and Stable Search Tail Latency: Figure 7 shows that
SPF!"#$ achieves low and stable tail latency in all percentile
5.2.1 System Setup. Table 2 lists the thread allocation for measurements. Since the overall tail latency trends are simi-
each system. Speci#cally, we allocate threads to each sys- lar, we focus our discussion on the most stringent tail latency
tem’s sub-components to meet the processing requirements measurement, P99.9.
of handling update throughput of 600~1200 QPS. The setting Experiments indicate that LIRE is able to keep posting
of update QPS is based on Alibaba’s daily update speed (100 distribution uniform because SPF!"#$ has a stable low search
million each day) [69]. Each system only needs one thread P99.9 latency around 4ms. In comparision, other systems’
to serve delete requests because deletion uses tombstones P99.9 latency is both worse and less stable than SPF!"#$.
to record the deletions, which is lightweight. For DiskANN, DiskANN’s P99.9 latency "uctuates signi#cantly with a
due to its high insert latency, we set its number of insert dramatic increase to more than 20ms during global rebuilds
threads to 3 and the number of background merge threads to because a search thread could be blocked by a global rebuild
10, because it is the minimum to keep up with the update and even with 10ms hard latency cut. The search P99.9 latency of
garbage collection process. Further increasing the number SPANN+ increases signi#cantly from 4ms to more than 10ms
will impact the query performance in the foreground nega- because its posting keeps growing, inducing data skews and
tively. The two remaining threads are used for foreground the increase of I/O and computation cost.
search for DiskANN. Overall, SPF!"#$ maintains 2.41x lower P99.9 latency to
To be comparable with DiskANN, SPF!"#$ and SPANN+ DiskANN on average and expands its latency advantage
also set 2 search threads. Both SPANN+ and SPF!"#$ only to SPANN+. The low and stable search tail latency can be
need one insert thread to serve 600+ QPS insert through- attributed to the LIRE protocol. During the experiment, we
put and two background threads for SPDK I/O and garbage found that only 0.4% insertion will cause rebalancing. Among
collection (or local rebuilder). them, the average split number is 2, and the maximum split
SOSP ’23, October 23–26, 2023, Koblenz, Germany Xu et al.

number is 160, with a cascading length of 3. The merge 6000 700k

frequency is only 0.1% of the update (insertion and deletion). 5000 600k

ery per Second

On average, each time 5094 vectors are evaluated, and only 500k
4000
79 are actually reassigned. 400k

IOPS
3000
High Search Accuracy: SPF!"#$ achieves a higher search 300k
accuracy compared to baselines. Both SPANN+ and SPF!"#$ 2000 200k
would not violate the NPA of a cluster-based index. Therefore, 1000 100k
the accuracy of SPANN+ and SPF!"#$ grows gradually since 0 0k
1 2 4 8 10 12
newly inserted vectors are all assigned to a subset of postings ThreadNum
due to the data shifting. Therefore, queries to these new QPS IOPS
vectors can easily hit since search and insertion follow the
same search path to get the nearest postings. Figure 8. Search throughput/disk IOPS vs # of SPF!"#$
Although SPANN+ search accuracy increases in a similar search threads on Azure lsv instance [41].
trend like SPF!"#$, the gap in accuracy increases over time.
The increasing gap between these two systems is because the
#threads #threads
index quality of SPANN+ degrades as partition distributions
Delete/Re-insert 4 Search 8
skew over time.
Background 3 Total 15
DiskANN proposes an algorithm to reduce the overhead
of global rebuild by eliminating outdated edges from all Table 3. Thread allocation for SPF!"#$ in billion-scale tests.
vertices and populating edges for a new vertex using the
neighborhood of its deleted neighbors. This method aims to
reduce the decline in accuracy due to a decreased number
of edges caused by vector deletions without reconstructing quality as that of SPF!"#$ because its posting distribution
its graph-based index completely. However, experiments does not shift much.
show that such a method cannot prevent DiskANN’s search
accuracy from decreasing over time. 5.3 Billion-Scale Stress Test
High and Stable Update Performance: SPF!"#$ achieves We scale up vector data size to billion-level and con#gure the
1.5ms average insert latency and stable tail latency. On the system to show the best performance SPF!"#$ achieves with
other hand, DiskANN su$ers from the heavy computation the given resource. We use Workload C (see §5.1) to simulate
caused by in-memory graph traversal, and thus results in a 20-day real-world update scenario. We demonstrate that
higher latency and lower throughput. Compared to SPANN+, SPF!"#$ has fully saturated SSD’s bandwidth and performed
we can see that SPF!"#$’s lightweight Local Rebuilder will well with stable resource utilization.
not a$ect the foreground insert performance.
5.3.1 System Setup. Table 3 lists thread allocation for
Low Resource Utilization: For resource usage, SPF!"#$
SPF!"#$’s stress tests. To fully achieve the IOPS of SSD,
achieves as low as 5.30X lower memory usage than baselines
our setting maximizes search throughput while supporting
during the whole update process. DiskANN occupies an extra
maximum update throughput.
60G memories for background streamingMerge and 15GB
Azure lsv3 has a max guaranteed NVMe IOPS of 400K [41].
for the second in-memory index for the update. SPANN+
We #rst run an experiment to #nd out the max search through-
needs much larger block-mapping entries to allow a larger
put lsv3 can handle. As Figure 8 shows, the IOPS and search
posting length. SPF!"#$ keeps the memory under 20GB,
throughput almost reach the peak at 8 search threads on a
which only grows slightly over time because new metadata
single SSD disk.
are created for each new posting triggered by splits. SPF!"#$
When search thread count is set to 8 for max search
also maintains a reasonable disk size. In the index, we #nd
throughput, a fore-ground thread count of 4 saturates the
that 86% of the total vectors have more than one replica, and
update throughput. Therefore we set the thread counts as
on average, one vector has 5.47 replicas, which is similar to
in Table 3 for this experiment. Search is the most important
the index built statically.
part of ANNS service, so the stress test we will maximize
We also ran the same experiment on Workload B and
our search throughput while support the maximum update
reached a similar conclusion with DiskANN. Note that SPANN+
throughput. Since Azure document[41] note that the max
achieves similar performance with SPF!"#$ on the SIFT
NVMe disk throughput is 400K and can go higher but not
dataset, which is almost uniformly distributed. This is ex-
be guaranteed to keep the IOPS higher than 400K, we make
pected because background garbage collection should be able
a simple test on lsv3 NVMe SSD by running SPF!"#$ Search
to prune stale vectors on SPANN+ without splits on uniform
On Azure lsv3 to #nd out that the MAX performance of lsv3
data-set. Consequently, SPANN+ achieves a similar index
NVMe SSD. and we can see on #gure 8 that when we set
SPF!"#$: Incremental In-Place Update for Billion-Scale Vector Search SOSP ’23, October 23–26, 2023, Koblenz, Germany

Search P99.9 Latency Search P99.9 Latency

7 7
Latency (ms)

Latency (ms)
6 6
5 5
4 4
3 3
Throughput Throughput
4k 4k
ery per Second

ery per Second

3k 3k
2k 2k
1k Search Throughput 1k Search Throughput
Insert Throughput Insert Throughput
0 0
IOPS IOPS
500k 500k
IOPS

IOPS
400k 400k
Guaranteed Limit Guaranteed Limit
0 2 4 6 8 10 12 14 16 18 20 0 2 4 6 8 10 12 14 16 18 20
Batches/Days Batches/Days
Stress Test of SIFT (Uniform Dataset) Stress Test on SPACEV (Skewed Dataset)

Figure 9. Billion-scale stress test on uniform and skew datasets. SPF!"#$ saturates the I/O with a stable P99.9 latency while
keeping accuracy stable and higher than 0.862 for uniform dataset and 0.807 for skew dataset by searching nearest 64 postings,
the memory and CPU utilization keep in about 74 GB and 1300% in both uniform and skew datasets.

search thread to 8, the QPS of SPF!"#$ and the IOPS of Disk 1

will no more grows, so in stress test we will set search thread
to 8 and then maximize the update throughput, and we #nd 0.98
out that when fore-ground thread set to 4 the IOPS will reach
Recall 10@10

the peak during the update. 0.96

In-place Update + Split/Reassign
0.94 In-place Update + Split Only
In-place Update
5.3.2 Experiment Results. Figure 9 records a daily time Static
series of the search P99.9 latency on both uniform and skew 0.92
1 1.5 2 2.5 3 3.5 4
datasets, search/insert throughput, and the IOPS of Work- Latency (ms)
Load C. We can see that SPF!"#$ reaches the IOPS limitation
with stable performance and resource utilization throughout Figure 10. The trade-o$ on search accuracy and latency with
the entire run. various update techniques under an increasingly skewed data
High NVMe SSD IOPS Utilization: As we can see from distribution.
Figure 9, SPF!"#$ always fully utilizes the NVMe’s band-
width, even exceeding the max guaranteed IOPS of Azurelsv3.
Thanks to LIRE’s lightweight protocol, we can see SPF!"#$’s 5.4 Data Distribution Shifting Micro-benchmark
bottleneck is in the disk IOPS, before reaching the CPU and In this experiment, we replay the experiment in §2.3 to
memory resource limit. demonstrate that LIRE is required to re-balance the shifting
Stable Search and Update Performance: As the data scale data distribution. We compare four systems in this experi-
grows from 100M to 1B, the search latency is stable, just like ment, where Static is our target since it has no updates. For
that in §5.2. There is some slight increase of P99.9 latency the rest of the three systems, we start with a naive system
in the beginning when the #rst split jobs are triggered. In with in-place update only, i.e., SPANN+, and gradually add
this case, the P99.9 latency increases slightly because of the sub-components of LIRE into the system.
gradual growth of in-memory index size, which makes the Experiment Results: Figure 10 shows the recall and latency
in-memory computation more costly over time. trade-o$ result. With a relaxed search latency, the #gure
Stable Accuracy: During the entire stress test, the accuracy shows that recall improves for all four systems. Meanwhile,
of SPF!"#$ remains stable, which is higher than 0.862 for the as the curve moves northwest, the system shows a higher
uniform dataset and 0.807 for the skew dataset by searching ANNS index quality with a more accurate recall and a lower
the nearest 64 postings. latency. An in-place update-only solution may have a high
SOSP ’23, October 23–26, 2023, Koblenz, Germany Xu et al.

1 6000

4500

Throughput
0.98
Recall 10@10

3000

0.96 1500
Reassign top0
Reassign top8 0
Reassign top64 1 2 4 8 1 2 4
0.94
Reassign top128 Foreground Update Background Update
Thread Num Thread Num
1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 3
Latency (ms) Foreground Background

Figure 11. Parameter Study: Reassign Range, top64 (nearest Figure 12. Foreground Scalability (Background Thread Num-
64 postings) is enough for reassign scanning. ber = 1) and Background Scalability (Foreground Thread
Number = 8).
recall but at the expense of high latency. Adding a split
component into the in-place update decreases the search As the left part of Figure 12 shows, a single-threaded back-
latency with the same accuracy. Adding the reassignment ground Local Rebuilder can keep up the foreground In-place
component further decreases the search latency. As shown in Updater until foreground threads are set to 2. Similarly, as on
Figure 10, the performance of SPF!"#$ with in-place update the right side of Figure 12, an 8-threaded foreground In-place
+ split/reassign is the closest one to the Static’s results, which Updater needs at least four threads for foreground In-place
represent the ideal cases. Updater to generate enough requests for the Local Rebuilder.
Based on the result, SPF!"#$ sets a thread ratio of 2:1 be-
5.5 Parameter Study tween the foreground In-place Updater and the background
In this experiment, we investigate the proper parameter con- Local Rebuilder balances the feed-forward pipeline.
#gurations for SPF!"#$ to achieve maximum performance.
Experiment results show that the Reassignment only requires 6 Conclusion
checking a limited scope of proximate postings for scanning SPF!"#$ supports incremental in-place update for billion-
to attain a good index quality. Furthermore, SPF!"#$ de- scale vector search. It implements LIRE, a Lightweight In-
mands a minimal increase in computational resources, specif- cremental RE-balancing protocol to split overly large post-
ically in terms of threads, to accomplish high throughput ings and reassign vectors across neighboring postings when
while also demonstrating good scalability. necessary. Experiments show that SPF!"#$ can incorporate
Reassign Range: The #rst parameter we examine is the re- continuous updates faster with signi#cantly lower resources
assign range, i.e., the size of the local rebuild range. Reassign than existing solutions while maintaining high search re-
range is measured by the number of nearby postings to check calls by (1) LIRE identi#es a minimal set of neighborhood
for vector reassignment after a new posting list is created. vectors in the large index space for updating to adapt to data
In this experiment, we use the same setting as in §2.3. distribution shift; (2) the index re-balancing operations and
In Figure 11, we vary reassign range from the nearest 0, the foreground queries are decoupled, and handled by e!-
i.e., only process reassign in the split posting, to the near- cient concurrency control mechanisms, avoiding operation
est 128 postings. As the reassign range increases, accuracy interference. SPFresh’s solid single-node performance builds
also increases with the same search time budget because a strong foundation for the future distributed version.
more NPA-violating vectors are identi#ed and reassigned.
The accuracy increase rate wanes o$ as the reassign range Acknowledgments
increases, where there is only a marginal increase from range We thank all the anonymous reviewers for their insightful
64 to 128. Consequently, we chose 64 as SPF!"#$’s default feedback, and our shepherd, Nitin Agrawal, for his guidance
reassign range. during the preparation of our camera-ready submission. This
Fore/Back-ground Update Resource Balance: The fore- work is supported in part by the National Natural Science
ground In-place Updater and background Local Rebuilder Foundation of China under Grant No.: 62141216, 62172382
work as a feed-forward pipeline as detailed in §4.2. In this and 61832011, and the University Synergy Innovation Pro-
experiment, we examine the proper resource ratio for In- gram of Anhui Province under Grant No.: GXXT-2022-045.
place Updater and Local Rebuilder to make their processing Cheng Li and Qi Chen are the corresponding authors.
speed balanced in the pipeline. Speci#cally, we con#gure
the foreground and background threads and measure the
throughput to see when the update resource is balanced.
SPF!"#$: Incremental In-Place Update for Billion-Scale Vector Search SOSP ’23, October 23–26, 2023, Koblenz, Germany

References 1145/355744.355745
[1] Hervé Jégou. Romain Tavenard. Matthijs Douze. Laurent Amsaleg. [19] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Ap-
2011. Datasets for approximate nearest neighbor search. h!p://corpus- proximate Nearest Neighbor Search With The Navigating Spreading-
[Link]/. out Graphs. PVLDB 12, 5 (2019), 461 – 474.
[2] Apache. [n. d.]. Apache Lucene is a high-performance, full-featured [20] K Ruben Gabriel and Robert R Sokal. 1969. A new statistical approach
text search engine library written in Java. h!ps://[Link]/apache/ to geographic variation analysis. Systematic zoology 18, 3 (1969), 259–
lucene. 278.
[3] Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. [21] Google. [n. d.]. Youtube. h!ps://[Link]/press/.
2018. HD-Index: Pushing the Scalability-Accuracy Boundary for Ap- [22] Rentong Guo, Xiaofan Luan, Long Xiang, Xiao Yan, Xiaomeng Yi, Jigao
proximate KNN Search in High-Dimensional Spaces. Proc. VLDB Luo, Qianya Cheng, Weizhi Xu, Jiarui Luo, Frank Liu, Zhenshan Cao,
Endow. 11, 8 (apr 2018), 906–919. h!ps://[Link]/10.14778/3204028. Yanliang Qiao, Ting Wang, Bo Tang, and Charles Xie. 2022. Manu: a
3204034 cloud native vector database management system. Proceedings of the
[4] Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, VLDB Endowment 15 (08 2022), 3548–3561. h!ps://[Link]/10.14778/
and Angela Y. Wu. 1998. An optimal algorithm for approximate nearest 3554821.3554843
neighbor searching #xed dimensions. J. ACM 45, 6 (1998), 891–923. [23] Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong
h!ps://[Link]/10.1145/293347.293348 Zhang. 2011. Fast Approximate Nearest-Neighbor Search with k-
[5] Artem Babenko and Victor Lempitsky. 2014. The inverted multi-index. Nearest Neighbor Graph. In IJCAI 2011, Proceedings of the 22nd Inter-
IEEE transactions on pattern analysis and machine intelligence 37, 6 national Joint Conference on Arti!cial Intelligence, Barcelona, Catalonia,
(2014), 1247–1260. Spain, July 16-22, 2011. AAAI Press, 1312–1317. h!ps://[Link]/10.
[6] Artem Babenko and Victor Lempitsky. 2017. Product Split Trees. 5591/978-1-57735-516-8/IJCAI11-222
In 2017 IEEE Conference on Computer Vision and Pattern Recognition [24] Junfeng He, Wei Liu, and Shih-Fu Chang. 2010. Scalable Similarity
(CVPR). 6316–6324. h!ps://[Link]/10.1109/CVPR.2017.669 Search with Optimized Kernel Hashing. In Proceedings of the 16th ACM
[7] Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 2018. Revisiting SIGKDD International Conference on Knowledge Discovery and Data
the inverted indices for billion-scale approximate nearest neighbors. Mining (Washington, DC, USA) (KDD ’10). Association for Computing
In Proceedings of the European Conference on Computer Vision (ECCV). Machinery, New York, NY, USA, 1129–1138. h!ps://[Link]/10.1145/
Springer-Verlag, Berlin, Heidelberg, 202–216. 1835804.1835946
[8] J.S. Beis and D.G. Lowe. 1997. Shape indexing using approximate [25] Intel. [n. d.]. SPDK: Storage Performance Development Kit. h!ps:
nearest-neighbour search in high-dimensional spaces. In 1997 Confer- //[Link]/.
ence on Computer Vision and Pattern Recognition {CVPR}’97, June 17-19, [26] Masajiro Iwasaki. 2016. Pruned bi-directed k-nearest neighbor graph
1997, San Juan, Puerto Rico. IEEE Computer Society, USA, 1000–1006. for proximity search. In International Conference on Similarity Search
h!ps://[Link]/10.1109/CVPR.1997.609451 and Applications. Springer, Springer International Publishing, Cham,
[9] Jon Louis Bentley. 1975. Multidimensional Binary Search Trees Used 20–33.
for Associative Searching. Commun. ACM 18, 9 (sep 1975), 509–517. [27] Masajiro Iwasaki and Daisuke Miyazaki. 2018. Optimization of In-
[10] Jon Louis Bentley. 1975. Multidimensional binary search trees used dexing Based on k-Nearest Neighbor Graph for Proximity Search in
for associative searching. Commun. ACM 18, 9 (1975), 509–517. h!ps: High-dimensional Data. arXiv:1810.07355 [[Link]]
//[Link]/10.1145/361002.361007 [28] P. Jain, B. Kulis, and K. Grauman. 2008. Fast image search for learned
[11] Elasticsearch B.V. [n. d.]. Elasticsearch. h!ps://[Link]/. metrics. In 2008 IEEE Conference on Computer Vision and Pattern Recog-
[12] Kenneth L Clarkson. 1994. An algorithm for approximate closest-point nition. 1–8.
queries. In Proceedings of the tenth annual symposium on Computational [29] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product
geometry. Association for Computing Machinery, New York, NY, USA, quantization for nearest neighbor search. IEEE transactions on pattern
160–164. analysis and machine intelligence 33, 1 (2010), 117–128.
[13] Sanjoy Dasgupta and Yoav Freund. 2008. Random Projection Trees [30] Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg.
and Low Dimensional Manifolds. In Proceedings of the Fortieth Annual 2011. Searching in one billion vectors: re-rank with source coding.
ACM Symposium on Theory of Computing (Victoria, British Columbia, In 2011 IEEE International Conference on Acoustics, Speech and Signal
Canada) (STOC ’08). Association for Computing Machinery, New York, Processing (ICASSP). IEEE, 861–864.
NY, USA, 537–546. h!ps://[Link]/10.1145/1374376.1374452 [31] Sang-Woo Jun, Andy Wright, Sizhuo Zhang, Shuotao Xu, and Arvind.
[14] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2018. GraFboost: Using Accelerated Flash Storage for External Graph
2004. Locality-sensitive Hashing Scheme Based on P-stable Distribu- Analytics. In Proceedings of the 45th Annual International Symposium
tions. In Proceedings of the Twentieth Annual Symposium on Computa- on Computer Architecture (Los Angeles, California) (ISCA ’18). IEEE
tional Geometry (Brooklyn, New York, USA) (SCG ’04). Association for Press, 411–424. h!ps://[Link]/10.1109/ISCA.2018.00042
Computing Machinery, New York, NY, USA, 253–262. [32] Brian Kulis and Kristen Grauman. 2009. Kernelized locality-sensitive
[15] B. N. Delaunay. 1934. Sur la sphère vide. Bull. Acad. Sci. URSS 1934, 6 hashing for scalable image search. In Computer Vision, 2009 IEEE 12th
(1934), 793–800. International Conference on. IEEE, Elsevier Science Publishers B. V.,
[16] Wei Dong, Moses Charikar, and Kai Li. 2011. E!cient k-nearest NLD, 2130–2137.
neighbor graph construction for generic similarity measures. In Pro- [33] Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi:
ceedings of the 20th International Conference on World Wide Web, Large-Scale Graph Computation on Just a PC. In Proceedings of the 10th
WWW 2011, Hyderabad, India, March 28 - April 1, 2011. Association USENIX Conference on Operating Systems Design and Implementation
for Computing Machinery, New York, NY, USA, 577–586. h!ps: (Hollywood, CA, USA) (OSDI’12). USENIX Association, USA, 31–46.
//[Link]/10.1145/1963405.1963487 [34] Jie Li, Haifeng Liu, Chuanghua Gui, Jianyu Chen, Zhenyuan Ni, Ning
[17] Facebook. 2020. Faiss. h!ps://[Link]/facebookresearch/faiss. Wang, and Yuan Chen. 2018. The Design and Implementation of a Real
[18] Jerome H. Freidman, Jon Louis Bentley, and Raphael Ari Finkel. 1977. Time Visual Search System on JD E-Commerce Platform. In Proceed-
An Algorithm for Finding Best Matches in Logarithmic Expected Time. ings of the 19th International Middleware Conference Industry (Rennes,
ACM Trans. Math. Software 3, 3 (1977), 209–226. h!ps://[Link]/10. France) (Middleware ’18). Association for Computing Machinery, New
York, NY, USA, 9–16. h!ps://[Link]/10.1145/3284028.3284030
SOSP ’23, October 23–26, 2023, Koblenz, Germany Xu et al.

[35] Sen Li, Fuyu Lv, Taiwei Jin, Guli Lin, Keping Yang, Xiaoyi Zeng, Xiao- Processing Systems (Vancouver, BC, Canada) (NIPS’20). Curran Asso-
Ming Wu, and Qianli Ma. 2021. Embedding-Based Product Retrieval ciates Inc., Red Hook, NY, USA, Article 895, 13 pages.
in Taobao Search. In Proceedings of the 27th ACM SIGKDD Conference [52] Amitabha Roy, Ivo Mihailovic, and Willy Zwaenepoel. 2013. X-Stream:
on Knowledge Discovery & Data Mining (KDD ’21). Association for Edge-Centric Graph Processing Using Streaming Partitions. In Pro-
Computing Machinery, New York, NY, USA, 3181–3189. h!ps://doi. ceedings of the Twenty-Fourth ACM Symposium on Operating Sys-
org/10.1145/3447548.3467101 tems Principles (Farminton, Pennsylvania) (SOSP ’13). Association
[36] Ting Liu, Andrew W Moore, Alexander Gray, and Ke Yang. 2004. for Computing Machinery, New York, NY, USA, 472–488. h!ps:
An investigation of practical approximate nearest neighbor al- //[Link]/10.1145/2517349.2522740
gorithms. Advances in Neural Information Processing Systems [53] Aditi Singh, Suhas Jayaram Subramanya, Ravishankar Krishnaswamy,
17 [Neural Information Processing Systems, {NIPS} 2004, Decem- and Harsha Vardhan Simhadri. 2021. FreshDiskANN: A Fast and
ber 13-18, 2004, Vancouver, British Columbia, Canada] (2004), 825– Accurate Graph-Based ANN Index for Streaming Similarity Search.
832. h!p://[Link]/paper/2666-an-investigation-of-practical- arXiv:2105.09613 [[Link]]
approximate-nearest-neighbor-algorithms [54] Jingkuan Song, Yi Yang, Zi Huang, Heng Tao Shen, and Richang
[37] S. Lloyd. 1982. Least squares quantization in PCM. IEEE Transactions Hong. 2011. Multiple Feature Hashing for Real-Time Large Scale
on Information Theory 28, 2 (1982), 129–137. h!ps://[Link]/10.1109/ near-Duplicate Video Retrieval. In Proceedings of the 19th ACM Inter-
TIT.1982.1056489 national Conference on Multimedia (Scottsdale, Arizona, USA) (MM ’11).
[38] Yu A. Malkov and D. A. Yashunin. 2020. E!cient and Robust Approx- Association for Computing Machinery, New York, NY, USA, 423–432.
imate Nearest Neighbor Search Using Hierarchical Navigable Small h!ps://[Link]/10.1145/2072298.2072354
World Graphs. IEEE Transactions on Pattern Analysis and Machine [55] Robert F. Sproull. 1991. Re#nements to nearest-neighbor searching
Intelligence 42, 4 (2020), 824–836. h!ps://[Link]/10.1109/TPAMI.2018. in k-dimensional trees. Algorithmica 6, 1-6 (1991), 579–589. h!ps:
2889473 //[Link]/10.1007/BF01759061
[39] Mark McCartin-Lim, Andrew McGregor, and Rui Wang. 2012. Approx- [56] Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar
imate Principal Direction Trees. In Proceedings of the 29th International Krishaswamy, and Harsha Vardhan Simhadri. 2019. DiskANN: Fast
Coference on International Conference on Machine Learning (Edinburgh, Accurate Billion-Point Nearest Neighbor Search on a Single Node. Curran
Scotland) (ICML’12). Omnipress, Madison, WI, USA, 1611–1618. Associates Inc., Red Hook, NY, USA.
[40] microsoft. 2020. SPACEV1B: A billion-Scale vector dataset for text de- [57] Jan Suchal and Pavol Navrat. 2010. Full Text Search Engine as Scalable
scriptors. h!ps://[Link]/microso"/SPTAG/tree/master/datasets/ k-Nearest Neighbor Recommendation System. In International Confer-
SPACEV1B. ence on Arti!cial Intelligence in Theory and Practice, Vol. 331. 165–173.
[41] microsoft. 2023. lsv3-series. h!ps://[Link]".com/en-us/azure/ h!ps://[Link]/10.1007/978-3-642-15286-3_16
virtual-machines/lsv3-series. [58] Yifang Sun, Wei Wang, Jianbin Qin, Ying Zhang, and Xuemin Lin.
[42] Tomas Mikolov, Kai Chen, Greg Corrado, and Je$rey Dean. 2013. 2014. SRS: Solving c-Approximate Nearest Neighbor Queries in High
E!cient Estimation of Word Representations in Vector Space. Dimensional Euclidean Space with a Tiny Index. Proc. VLDB Endow. 8,
arXiv:1301.3781 [[Link]] 1 (sep 2014), 1–12. h!ps://[Link]/10.14778/2735461.2735462
[43] Andrew W Moore. 2000. The Anchors Hierarchy: Using the Trian- [59] Narayanan Sundaram, Aizana Turmukhametova, Nadathur Satish,
gle Inequality to Survive High Dimensional Data. In {UAI} ’00: Pro- Todd Mostak, Piotr Indyk, Samuel Madden, and Pradeep Dubey. 2013.
ceedings of the 16th Conference in Uncertainty in Arti!cial Intelligence, Streaming Similarity Search over One Billion Tweets Using Paral-
Stanford University, Stanford, California, USA, June 30 - July 3, 2000, lel Locality-Sensitive Hashing. Proc. VLDB Endow. 6, 14 (sep 2013),
Vol. I. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1930–1941. h!ps://[Link]/10.14778/2556549.2556574
397–405. h!ps://dslpi!.org/uai/[Link]?mmnu= [60] Godfried T Toussaint. 1980. The relative neighbourhood graph of a
1{&}smnu=2{&}article{_}id=47{&}proceeding{_}id=16 #nite planar set. Pattern recognition 12, 4 (1980), 261–268.
[44] Yadong Mu and Shuicheng Yan. 2010. Non-Metric Locality-Sensitive [61] Jun Wang, Sanjiv Kumar, and S. Chang. 2012. Semi-Supervised Hashing
Hashing.. In AAAI. AAAI Press, 539–544. for Large-Scale Search. IEEE transactions on pattern analysis and
[45] Marius Muja and David G. Lowe. 2014. Scalable Nearest Neighbour machine intelligence 34 (02 2012). h!ps://[Link]/10.1109/TPAMI.2012.
Algorithms for High Dimensional Data. IEEE Transactions on Pattern 48
Analysis and Machine Intelligence 36, 11 (2014), 2227–2240. h!ps: [62] Jingdong Wang and Shipeng Li. 2012. Query-Driven Iterated Neighbor-
//[Link]/10.1109/TPAMI.2014.2321376 hood Graph Search for Large Scale Indexing. In Proceedings of the 20th
[46] David Nistér and Henrik Stewénius. 2006. Scalable recognition with a ACM International Conference on Multimedia (Nara, Japan) (MM ’12).
vocabulary tree. 2006 {IEEE} Computer Society Conference on Computer Association for Computing Machinery, New York, NY, USA, 179–188.
Vision and Pattern Recognition {(CVPR} 2006), 17-22 June 2006, New York, h!ps://[Link]/10.1145/2393347.2393378
NY, {USA} 2 (2006), 2161–2168. h!ps://[Link]/10.1109/CVPR.2006.264 [63] Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, and
[47] OpenAI. 2022. ChatGPT Retrieval Plugin. h!ps://[Link]/openai/ Shipeng Li. 2012. Scalable k-nn graph construction for visual descrip-
chatgpt-retrieval-plugin. tors. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE
[48] OpenAI. 2022. GPT3 Embedding. h!ps://[Link]/docs/ Conference on. IEEE, IEEE Computer Society, USA, 1106–1113.
guides/embeddings. [64] Jingdong Wang, Naiyan Wang, You Jia, Jian Li, Gang Zeng, Hong-
[49] Je$rey Pennington, Richard Socher, and Christopher Manning. 2014. bin Zha, and Xian Sheng Hua. 2014. Trinary-projection trees for
Glove: Global Vectors for Word Representation. EMNLP 14, 1532–1543. approximate nearest neighbor search. IEEE Transactions on Pat-
h!ps://[Link]/10.3115/v1/D14-1162 tern Analysis and Machine Intelligence 36, 2 (2014), 388–403. h!ps:
[50] Maxim Raginsky and Svetlana Lazebnik. 2009. Locality-sensitive bi- //[Link]/10.1109/TPAMI.2013.125
nary codes from shift-invariant kernels. In Advances in neural infor- [65] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun
mation processing systems. Curran Associates Inc., Red Hook, NY, USA, Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun
1509–1517. Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang
[51] Jie Ren, Minjia Zhang, and Dong Li. 2020. HM-ANN: E!cient Billion- Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles
Point Nearest Neighbor Search on Heterogeneous Memory. In Pro- Xie. 2021. Milvus: A Purpose-Built Vector Data Management System.
ceedings of the 34th International Conference on Neural Information In Proceedings of the 2021 International Conference on Management of
Data (Virtual Event, China) (SIGMOD ’21). Association for Computing
SPF!"#$: Incremental In-Place Update for Billion-Scale Vector Search SOSP ’23, October 23–26, 2023, Koblenz, Germany

Machinery, New York, NY, USA, 2614–2627. h!ps://[Link]/10.1145/ search. In 2011 International Conference on Computer Vision. IEEE
3448016.3457550 Computer Society, USA, 1631–1638. h!ps://[Link]/10.1109/ICCV.
[66] Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, and Heng Tao 2011.6126424
Shen. 2018. A Survey on Learning to Hash. IEEE Transactions on [72] Peter N Yianilos. 1993. Data Structures and Algorithms for Nearest
Pattern Analysis and Machine Intelligence 40, 4 (2018), 769–790. Neighbor Search in General Metric Spaces. Proceedings of the Fourth
[67] Qi Chen. Bing Zhao. Haidong Wang. Mingqin Li. Chuanjie Liu. Annual {ACM/SIGACT-SIAM} Symposium on Discrete Algorithms, 25-
Zengzhong Li. Mao Yang. Jingdong Wang. 2021. SPANN: Highly- 27 January 1993, Austin, Texas. (1993), 311–321. h!p://[Link]/
e!cient Billion-scale Approximate Nearest Neighbor Search. In 35th [Link]?id=313559.313789
Conference on Neural Information Processing Systems (NeurIPS 2021). [73] Minjia Zhang and Yuxiong He. 2019. GRIP: Multi-Store Capacity-
[68] Qi Chen. Haidong Wang. Mingqin Li. Gang Ren. Scarlett Li. Je$ery Zhu. Optimized High-Performance Nearest Neighbor Search for Vector
Jason Li. Chuanjie Liu. Lintao Zhang. Jingdong Wang. 2018. SPTAG: Search Engine. In Proceedings of the 28th ACM International Conference
A library for fast approximate nearest neighbor search. h!ps://github. on Information and Knowledge Management, CIKM 2019, Beijing, China,
com/Microso"/SPTAG. November 3-7, 2019, Wenwu Zhu 0001, Dacheng Tao, Xueqi Cheng,
[69] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Peng Cui 0001, Elke A. Rundensteiner, David Carmel, Qi He, and
Feifei Li, and Yuanzhe Cai. 2020. AnalyticDB-V: A Hybrid Analytical Je$rey Xu Yu (Eds.). Association for Computing Machinery, New York,
Engine towards Query Fusion for Structured and Unstructured Data. NY, USA, 1673–1682. h!ps://[Link]/10.1145/3357384.3357938
Proc. VLDB Endow. 13, 12 (aug 2020), 3152–3165. h!ps://[Link]/10. [74] Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E.
14778/3415478.3415541 Priebe, and Alexander S. Szalay. 2015. FlashGraph: Processing Billion-
[70] Yair Weiss, Antonio Torralba, and Rob Fergus. 2009. Spectral hashing. Node Graphs on an Array of Commodity SSDs. In Proceedings of the
In Advances in neural information processing systems. Curran Asso- 13th USENIX Conference on File and Storage Technologies (Santa Clara,
ciates Inc., Red Hook, NY, USA, 1753–1760. CA) (FAST’15). USENIX Association, USA, 45–58.
[71] Hao Xu, Jingdong Wang, Zhu Li, Gang Zeng, Shipeng Li, and Nenghai
Yu. 2011. Complementary hashing for approximate nearest neighbor