JOURNAL OF LATEX CLASS FILES, VOL. 14, NO.

8, AUGUST 2021 1

A Comprehensive Survey on Vector Database:

Storage and Retrieval Technique, Challenge
Le Ma∗ , Ran Zhang∗ , Yikun Han∗ , Shirui Yu, Zaitian Wang, Zhiyuan Ning, Jinghan Zhang, Ping Xu,
Pengjiang Li, Wei Ju, Chong Chen, Dongjie Wang, Kunpeng Liu, Pengyang Wang, Pengfei Wang,
Yanjie Fu, Chunjiang Liu † , Yuanchun Zhou, Chang-Tien Lu

Abstract—Vector databases (VDBs) have emerged to manage attributes [9]. Depending on the complexity and granularity of
high-dimensional data that exceed the capabilities of traditional the underlying data, the dimensions of these high-dimensional
database management systems, and are now tightly integrated
arXiv:2310.11703v2 [[Link]] 16 Jun 2025

vectors usually range from dozens to thousands. Unlike tra-

with large language models as well as widely applied in modern
artificial intelligence systems. Although relatively few studies ditional relational databases, VDBs provide efficient mecha-
describe existing or introduce new vector database architectures, nisms for large-scale storage, management, and search of high-
the core technologies underlying VDBs, such as approximate dimensional vectors [10]–[12]. These mechanisms bring vari-
nearest neighbor search, have been extensively studied and are ous efficient functions to VDBs, such as supporting semantic
well documented in the literature. In this work, we present a similarity search, efficiently managing large-scale data, and
comprehensive review of the relevant algorithms to provide a
general understanding of this booming research area. Specifically, providing low-latency responses. These functions make VDBs
we first provide a review of storage and retrieval techniques in increasingly integrated into AI-based applications.
VDBs, with detailed design principles and technological evolution. VDBs have two core functions: vector storage and vector re-
Then, we conduct an in-depth comparison of several advanced trieval. The vector storage function relies on techniques such as
VDB solutions with their strengths, limitations, and typical appli- quantization, compression, and distributed storage mechanisms
cation scenarios. Finally, we also outline emerging opportunities
for coupling VDBs with large language models, including open to improve efficiency and scalability. The retrieval function
research problems and trends, such as novel indexing strategies. of VDBs relies on specialized indexing techniques, including
This survey aims to serve as a practical resource, enabling tree-based methods, hashing methods [13], graph-based mod-
readers to quickly gain an overall understanding of the current els, and quantization-based techniques [14]. These indexing
knowledge landscape in this rapidly developing area. techniques optimize high-dimensional similarity search by
Index Terms—Vector Database, Retrieval, Storage, Large Lan- reducing computational cost and improving search perfor-
guage Models. mance. In addition, hardware acceleration and cloud-based
technologies have further enhanced the capabilities of VDBs,
I. I NTRODUCTION making them suitable for large-scale and real-time applications
Vectors, particularly those in high-dimensional spaces, are [15]–[17].
mathematical representations of data, encoding the semantic Therefore, compared with traditional databases, vector
and contextual information of entities such as text, images, databases (VDBs) have three significant advantages: (1) Vector
audio, and video [1], [2]. These vectors are generally gen- databases possess efficient and accurate vector retrieval
erated through some related machine learning models, and capabilities. The core function of VDBs is to retrieve relevant
the generated vectors are usually high-dimensional and can vectors through vector similarity (distance), and this function
be used for similarity comparison. The step of converting is also the core of applications such as natural language pro-
original unstructured data into vectors is the foundation of cessing (NLP), computer vision, and recommendation systems
many artificial intelligence (AI) applications (including large [18], [19]. In contrast, traditional databases can only query
language models (LLMs) [3], question-answering systems data based on exact matching or predefined conditions, and
[4], [5], image recognition [6], recommendation systems [7], this kind of query method is relatively slow and often does
[8], etc.). However, in terms of managing and retrieving not consider the semantic information of the data itself. (2)
high-dimensional vector data, traditional databases designed Vector databases support the storage and query of complex
for handling structured data are often inadequate. Vector and unstructured data. VDBs can store and search data with
databases, on the other hand, provide a specialized solution high complexity and granularity, such as text, images, audio,
to these challenges. video, etc. However, traditional databases, such as relational
Vector Databases (VDBs) are tools specifically designed to databases, are difficult to store this kind of data informa-
efficiently store and manage high-dimensional vectors. Specif- tion well [20]. (3) Vector databases have high scalability
ically, VDBs store information as high-dimensional vectors, and real-time processing capabilities. Traditional databases
which are mathematical representations of data features or face challenges in effectively handling unstructured data and
large volumes of real-time datasets [21]. However, VDBs can
∗ Equal contribution. † Corresponding author.
process vector data at large scale and in real time, which
This paper was produced by the IEEE Publication Technology Group. They
are in Piscataway, NJ. is crucial for modern data science and artificial intelligence
Manuscript received April 19, 2021; revised August 16, 2021. applications [22]. By using technologies such as sharding [23],
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 2

partitioning, caching, and replication, VDBs can distribute ical evolution.

workloads and optimize resource utilization across multiple • We provide a detailed comparative analysis of existing
machines or clusters. Traditional databases, on the other hand, VDB solutions, highlighting their strengths, limitations,
may face scalability bottlenecks, latency issues, or concurrency and typical application scenarios.
conflicts when handling big data [19]. • We synthesize the main challenges, recent advancements,
Recent surveys on VDBs primarily cover fundamental con- and future directions for VDBs, including open research
cepts and practical applications of VDBs and vector database problems and trends such as novel indexing strategies,
management systems. Some studies [12], [19], [24] focus on adaptive query optimization, and integration with ad-
the workflow and technical challenges of VDBs, including key vanced AI capabilities.
aspects such as query processing, optimization, and execution This paper comprehensively summarizes the technologies re-
techniques. And some works [25] explore the critical role lated to vector databases, and systematically tests the per-
of VDBs in modern generative AI applications and provide formance of existing open-source vector databases. It also
an outlook on the future of VDBs. While these studies have provides an outlook on the challenges that vector databases
their respective focuses, they do not provide a comprehensive will face in the future. Through the summary of this paper,
survey of the overall storage and search technologies in VDBs, researchers can deepen their understanding of the field of
nor deliver a thorough analysis comparing the capabilities vector databases. Figure 1 shows the overall framework of the
of existing VDBs. Furthermore, there is limited exploration paper, and we also construct a classification system of storage
of how these systems can integrate with rapidly advancing and search technologies for VDBs, as shown in Figure 2.
AI technologies, such as large language models (LLMs), to
support modern data-intensive applications.
This gap shows the need for a comprehensive survey to II. S TORAGE
consolidate current knowledge and uncover key research chal- Efficient data management strategies are essential for the
lenges related to VDB. To address this, our survey makes the performance and scalability of VDBs. This section explores
following core contributions: four key techniques: sharding and partitioning for data distri-
• We systematically review storage and retrieval techniques bution, caching for reducing query latency, and replication for
in VDBs, outlining their design principles and technolog- ensuring availability and fault-tolerance.

Features VS
Multiple
Sharding
Sharding Geographic Sharding
Machines Range- Hash- Loading capacity
based based
Single List- K-Means
Partitioning
Machines Based Partitioning
Search performance

Cache Eviction Algorithms Caching Method

Caching
FIFO MRU LFU Partitioned Cache

Index Support for Distributed

Leader-Follower Multi-Leader Construction and
Leaderless Heterogeneou Parallel
Searching High
Replication Dimensional s Vector Data Processing
Vectors Types Support

Integration with Integration

Mainstream Data security
with emerging
Machine and privacy
Learning application
protection
Frameworks scenarios
Brute Force Tree-Based
Nearest Neighbor Search Approach Approach

Approximate Nearest Neighbor Search Key Approaches

Quantization-
Graph-Based Hash-Based
Based
Vector Databases for LLMs LLMs for Vector Databases
Product Hierarchical Local-Sensitive
Quantization Navigable Hashing
Small Worlds DB Management Tasks
RAG Memory
Vector Data Handling

A General LLMs and Vector Databases Synergized Framework

Fig. 1. Framework overview of this survey structure covering Storage Techniques, Search Techniques, Database Comparison, Challenges, and the Synergy of
Large Language Models (LLMs) with VDBs. Each section represents a fundamental facet of the operation and integration of modern VDBs within advanced
AI technologies.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 3

A. Sharding “Asia”). This method is particularly useful for latency-sensitive

localized queries, such as recommendation systems or geospa-
Sharding is a technique that distributes a VDB across tial analytics. By storing data in shards physically closer to
multiple machines or clusters, called shards, based on specific users, geo-sharding reduces cross-region network latency and
criteria, such as a hash function or a key range. It is a foun- helps comply with data sovereignty regulations. Additionally,
dational strategy for achieving scalability, load balancing, and combined with dynamic load balancing, it can adapt to shifting
fault tolerance in distributed systems by dividing the dataset geographic access patterns for optimal performance.
into smaller, manageable units. Different sharding methods are
designed to address specific challenges, such as balancing data
distribution, minimizing hotspots, reducing query latency, and B. Partitioning
supporting dynamic scaling. This section covers three widely Partitioning typically refers to dividing data within a single
adopted strategies: range-based sharding, hash-based sharding, database instance into multiple logical subsets based on rules
and geographic sharding. such as range, list, and K-Means, where all partitioned data
Range-Based Sharding. The most straightforward sharding remains within the same physical system. This approach im-
method is range-based sharding, which partitions vector data proves query efficiency, facilitates parallel processing, and op-
across shards by dividing it into non-overlapping key intervals, timizes resource usage by organizing data into logical groups.
or ranges, based on sorted keys [26]. For example, users can For instance, users can partition a VDB by color values such
shard a VDB by dividing the ID column of the vector data into as red, yellow, and blue, where each partition contains vector
different ranges, such as 0-999, 1000-1999, 2000-2999, and so data associated with a specific “color” column value. Queries
on, with each range assigned to a specific shard. Each range can then target specific partitions, avoiding unnecessary scans
corresponds to a shard. This way, users can query the vector of unrelated data and improving performance. While sharding
data more efficiently by specifying the shard name or range. focuses on distributing data across multiple machines in a
Range-based sharding is simple to implement and provides distributed environment, partitioning primarily organizes data
efficient query performance for range-based queries, such as within a single machine or node. These two techniques serve
retrieving all vectors within a specific time period or ID range. different purposes but can be used together synergistically. In
However, this method often leads to data skew and uneven load practical applications, sharding achieves horizontal scalability
distribution if key values are not uniformly distributed. Range- by distributing data across nodes, while partitioning optimizes
based sharding is particularly suitable for use cases where data local data organization within each node. By combining the
access patterns are predictable, such as time-series analytics two, systems can balance global scalability and localized
or sequential ID-based queries. query performance—sharding handles load distribution for
Hash-Based Sharding. Another common sharding method large datasets, and partitioning ensures efficient data access
in VDBs is hash-based sharding [26]–[28], which assigns within individual shards. Partitioning strategies vary depending
vector data into different shards based on the hash value on the characteristics of the data and application requirements.
of a key column or a set of columns. For example, users This section discusses four common partitioning methods:
can shard a VDB by applying a hash function to the ID range partitioning, list partitioning, k-means partitioning, and
column of the vector data. For example, users can distribute hash-based Partitioning.
the vector data evenly across the shards and avoid hotspots. Range-based Partitioning. Range-based partitioning is a
However, traditional hash-based methods, such as modulo method widely used in VDBs, where data is divided into non-
hashing, introduce challenges during cluster scaling, suffering overlapping key ranges to form partitions [34], [35]. Each
from significant data redistribution when adding or removing range corresponds to a specific subset of data based on a
shards. To address this, consistent hashing is often employed sorted key (e.g., timestamps, numeric IDs). Similar to the
in distributed VDBs. Unlike traditional hashing, consistent strength of range-based sharding, range-based partitioning is
hashing maps both data and nodes to a ring-like hash space. particularly efficient for range-based queries, as it allows the
This ensures that only a small fraction of data (O(1/N)) is system to target specific partitions directly. For example, users
remapped when nodes are added or removed. Consistent hash- can partition a VDB by date ranges, such as monthly or
ing minimizes reorganization overhead during cluster scaling quarterly. This way, users can query the vector data more
while maintaining balanced data distribution. Additionally, efficiently by specifying the partition name or range.
virtual nodes (replicas of physical nodes on the hash ring) List-based Partitioning. Another way that partitioning
further enhance load balancing, mitigating hotspots. Although works in VDB is by using a list partitioning method, which
consistent hashing introduces slight computational complexity, assigns vector data to different partitions based on their value
its advantages in dynamic environments make it a preferred lists of a key column or a set of columns [36], [37]. For
choice for modern distributed systems [29]–[31] example, users can partition a vector database by color values,
Geographic Sharding. Another approach is geographic such as red, yellow, and blue. Each partition contains vector
sharding (also known as geo-sharding), which distributes vec- data that have a given value of the color column. This way,
tor data across shards based on geographic attributes [32], users can query the vector data more easily by specifying the
[33], such as user region or location. For instance, a VDB can partition name or list.
be partitioned by a “region” field, assigning each shard to a K-Means Partitioning. A third partitioning method for
specific geographic zone (e.g., “North America,” “Europe,” or VDBs is k-means partitioning [20], which divides vector data
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 4

Storage

Sharding Partitioning Caching Replication

Range- Least Leader-

Range First-In
Based [16] [27] [28] [41] [42] [79] Frequently Follower [84]
Partitioning First-Out [62] [89]
Sharding Used Replication

Hash- Least Multi-

[16] [24] [31] List
Based [50] [51] Recently [79] Partitioned Leader [37] [38]
[57] [58] [80] Partitioning [81]
Sharding Used Cache Replication

Geographic K-Means Most Leaderless

[98] [115] Partitioning [87] Recently [14] [26]
Sharding [43] Replication
Used

Hash-based
Partitioning [1] [2] [45]

Nearest Neighbor Search

Tree-Based KD-Tree Ball-Tree R-Tree

[17] [40] [30] [71] [83] [47] M-Tree [23]
Approach
[24]

Approximate Nearest Neighbor Search

Hash-Based Tree-Based Graph-Based Quantization-Based Approach

Approach Approach Approach

Local- Approxim
Navigable Scalable
[8] [9] [10] [11] [19] Small
Inverted
Sensitive [90] [113] [114] [72] Nearest [46] [97]
[25] [53] -ate World
File Index
Hashing Neighbor
Nearest [32]
Neighbor- Product Inverted
Spectral Hierachic-
s Oh Yeah Quantizati- [55] [78] File
[109] al
Hashing on
Product [45] [103]
Navigable [76]
Small Optimized quantizati
Spherical Best Bin World Product -on
[49] [68] [94] [39] [66]
Hashing First Quantizati-
on

Deep [4] [69] [74] K-means Online

[86] Product
Hashing [75] Tree [3] [112]
Quantizati-
on

Fig. 2. Taxonomy of Vector Database (VDB) Storage and Search Technologies.

into a predetermined number (k) of clusters. Each cluster belongs to. In VDBs, the hash value is typically calculated
represents a partition, with vectors within the same cluster based on certain features of the vector (for example, values of
being similar to each other and vectors between clusters specific dimensions or the entire vector). The hash function
differing significantly. Similar vectors are placed in the same can evenly distribute data across partitions, preventing any
partition, which improves query efficiency. However, for large- single partition from storing too much data. However, when
scale datasets, the computational cost of k-means clustering the data distribution is uneven, it may lead to some partitions
can be high, especially when frequent updates necessitate re- becoming overloaded. Additionally, when the node number
clustering. changes, hash-based partitioning may require the redistribution
Hash-based Partitioning. Alternatively, some VDBs adopt of the large dataset, which can incur significant overhead.
hash-based partitioning, such as consistent or uniform hash-
ing [38]–[40]. Specifically, the hashing partitioning strategy C. Caching
uses a hash function to map data to different partitions. The Caching is a technique that stores frequently accessed or
hash value of each data point determines which partition it recently used data in a fast and accessible memory, such as
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 5

RAM, to reduce latency and improve data retrieval perfor- reuse of recently accessed vectors is unlikely. However, MRU
mance. Caching can be used in VDBs to speed up similarity is suboptimal for workloads with strong temporal locality, as
search and vector retrieval. In traditional database systems, it may prematurely evict data that will soon be accessed again.
utilizing in-memory key-value stores (e.g., Redis) as a caching Least Frequently Used (LFU). The LFU algorithm is a
layer represents a widely adopted approach. This methodology frequency-based cache eviction mechanism that determines
generates cache keys by combining query parameters (such removal priority by continuously tracking the access count
as specific column values for matching). When a target key of each vector data item. The LFU algorithm maintains a
is found in the cache, Redis serves the corresponding data; frequency table and evicts the least frequently accessed items
otherwise, a cache miss occurs, necessitating database queries when the cache is full. A typical implementation requires
to fetch the required information. However, this key-value maintaining an access counter for each cached item, often
paradigm proves unsuitable for VDBs, as they store high- using a min-heap data structure to efficiently identify the
dimensional vector data rather than structured data, making it lowest-frequency items with a time complexity of O(log n)
virtually impossible to reuse identical vectors across queries. [45], [46]. However, the LFU algorithm can be susceptible to
To address these challenges, it is important to explore general cache pollution, as items frequently accessed in the past may
caching algorithms and their applicability to VDBs. This linger in the cache even when they are no longer needed. Thus,
section discusses four common caching methods: first-in first- LFU is suitable for applications with stable and long-lived
out (FIFO), least recently used (LRU), most recently used spot data patterns (e.g., popular product recommendations,
(MRU), and least frequently used (LFU). high-frequency user profile queries), while its effectiveness
First-In First-Out (FIFO). FIFO algorithm is a funda- diminishes in environments with rapidly evolving access dis-
mental cache eviction strategy that operates on the principle tributions.
of “first in, first out”: when the cache space is exhausted, it Partitioned Cache. Partitioned caching is a common ap-
prioritizes removing the earliest stored vector data [41], [42]. proach in VDBs, wherein vector data are divided into multiple
This algorithm maintains a simple queue structure: new data partitions based on specific criteria [47], such as geographic
is always appended to the tail, while eviction removes the location, category, or access frequency. Each partition can
oldest data from the head [43]. FIFO is particularly suitable be allocated a distinct cache size and may employ different
for vector data scenarios with stable access patterns and no eviction policies according to the respective demand and usage
distinct hotspots, such as time-series vector data collected at patterns. This enables the cache to retain the most relevant
fixed intervals. While its implementation is simple and effi- vector data for each partition, thereby improving resource
cient (with O(1) time complexity), it may inadvertently evict utilization and overall cache effectiveness. For example, Esri,
frequently used data due to disregarding access frequency. A a leading geographic information system (GIS) company,
typical application includes real-time processing systems for leverages the partitioned cache to efficiently store vector data
industrial sensor data, where the timeliness of historical vector and support high-performance map rendering.
data often outweighs its reuse value.
Least Recently Used (LRU). One commonly employed
D. Replication
caching strategy in VDBs is the least recently used (LRU)
policy, which evicts the least recently accessed vector data Replication is a technique that creates multiple copies of
when the cache reaches its capacity. This approach ensures the vector data and stores them on different nodes or clus-
that the cache retains the most relevant or frequently queried ters. Replication can improve the availability, durability, and
vectors, thereby improving the likelihood of cache hits [43]. performance of VDB. This section discusses three common
For example, Redis, a widely used in-memory database, im- replication methods: leader-follower replication, multi-leader
plements LRU caching to manage vector data and facilitate replication, and leaderless replication.
efficient vector similarity search. However, LRU may not Leader-Follower Replication. Leader-Follower replication
effectively retain data with long-term or periodic popularity, designates one node as the leader and the others as the
as it only considers recent access history. LRU is particularly followers, and allows only the leader to accept write requests
suitable for scenarios with strong temporal locality, such as and propagate them to the followers [48]. Leader-follower
recommendation systems and real-time search applications, replication can ensure strong consistency and simplify the
where recently accessed vectors are highly likely to be queried conflict resolution of VDB. However, it may also introduce
again. availability issues and require failover mechanisms to handle
Most Recently Used (MRU). The Most Recently Used leader failures.
(MRU) [44] algorithm is another caching strategy employed Multi-Leader Replication. Multi-Leader replication ex-
in VDBs that prioritizes evicting the most recently accessed tends the traditional leader-follower model by designating
vector data when cache capacity is reached. This approach multiple nodes as leaders, each capable of independently
operates under the assumption that recently queried vectors accepting and processing write requests [49], [50]. In this
are less likely to be accessed again in the short term, thereby architecture, all leader nodes can concurrently handle write
retaining less recently used data that may be needed in the operations and asynchronously propagate changes to other
future. MRU has been adopted in certain storage systems and nodes in the system.
applications with transient or one-time access patterns, such Leaderless Replication. Leaderless replication does not
as data streaming or processing workloads, where immediate distinguish between leader and follower nodes, and allows any
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 6

node to accept write and read requests [51], [52]. Leaderless distances to the query point and tracking the closest one. This
replication can avoid single points of failure and improve the algorithm guarantees to find the true nearest neighbor for any
scalability and reliability of VDB. However, it may also intro- query point, but it has a high computational cost. The time
duce consistency issues and require coordination mechanisms complexity of a brute force algorithm for NNS problem is
to resolve conflicts. O(n), where n is the size of the dataset. The space complexity
is O(1), since no extra space is needed.
III. S EARCH 2) Tree-Based Approach: Four tree-based methods will be
VDBs are designed to facilitate efficient similarity search presented here, namely k-dimensional tree (KD-Tree), Ball-
over high-dimensional vector data, an essential operation in Tree, R-Tree, and M-Tree.
many AI and machine learning applications. This similarity KD-Tree [57] . It is a technique for organizing points
search is typically implemented through nearest neighbor in a k-dimensional space, where k is usually a very big
search algorithms, which can be further divided into exact number. It works by building a binary tree in which every
nearest neighbor search (NNS) and approximate nearest neigh- node is a k-dimensional point. Every non-leaf node in the
bor search (ANNS) methods. tree acts as a splitting hyperplane that divides the space into
NNS is the optimization problem of finding the point in a two parts, known as half-spaces. The splitting hyperplane is
given set that is closest (or most similar) to a given point. perpendicular to the chosen axis, which is associated with one
Closeness is typically expressed in terms of a dissimilarity of the k dimensions. The splitting value is usually the median
function: the less similar the objects, the larger the function or the mean of the points along that dimension.
values. For example, users can use NNS to find images that The algorithm maintains a priority queue of nodes to visit,
are similar to a given image based on their visual content sorted by their distance to the query point. At each step, the
and style, or documents that are similar to a given document algorithm pops the node with the smallest distance from the
based on their topic and sentiment. ANNS is a variation queue, and checks if it is a leaf node or an internal node. If it is
of NNS that allows for some error or approximation in the a leaf node, the algorithm compares the distance between the
search results. ANNS can trade off accuracy for speed and query point and the data point stored in the node, and updates
space efficiency, which can be useful for large-scale and high- the current best distance and nearest neighbor if necessary.
dimensional data. For example, users can use ANNS to find If it is an internal node, the algorithm pushes its left and
products that are similar to a given product based on their right children to the queue, with their distances computed as
features and ratings, or users that are similar to a given user follows:
based on their preferences and behaviors.
Observing the current division for NNS and ANNS algo-
(
0 if qN .axis ≤ [Link]
rithms, the boundary is precisely their design principle, such dL (q, N ) =
as how they organize, index, or hash the dataset, how they (qN .axis − [Link])2 if qN .axis > [Link]
search or traverse the data structure, and how they measure or (1)
estimate the distance between points. NNS algorithms tend to (
use more exact or deterministic methods, such as partitioning 0 if qN .axis ≥ [Link]
dR (q, N ) =
the space into regions by splitting along one dimension (k-d ([Link] − qN .axis )2 if qN .axis < [Link]
tree) or enclosing groups of points in hyperspheres (ball tree), (2)
and visiting only the regions that may contain the nearest where q is the query point, N is the internal node, [Link]
neighbor based on some distance bounds or criteria. ANNS is the splitting axis of N , and [Link] is the splitting value
algorithms tend to use more probabilistic or heuristic methods, of N . The algorithm repeats this process until the queue is
such as mapping similar points to the same or nearby buckets empty or a termination condition is met.
with high probability (locality-sensitive hashing), visiting the The advantage of KD-tree is that it is conceptually simpler
regions in order of their distance to the query point and and often easier to implement than some of the other tree
stopping after a fixed number of regions or points (best structures. The performance of KD-tree depends on several
bin first), or following the edges that lead to closer points factors, such as the dimensionality of the space, the number of
in a graph with different levels of coarseness (hierarchical points, and the distribution of the points. These factors affect
navigable small world). the trade-off between accuracy and efficiency, as well as the
In fact, a data structure or algorithm that supports NNS complexity and scalability of the algorithm. There are also
can also be applied to ANNS, and for ease of categorization, some challenges and extensions of KD-tree, such as dealing
such methods are included under the section on NNS. And with the curse of dimensionality when the dimensionality
in recent years, several new algorithms for high-dimensional is high, introducing randomness in the splitting process to
vector NNS have emerged [13], [53]–[56]. Although these improve robustness, or using multiple trees to increase recall.
algorithms have not yet been widely adopted by VDBs, they This is a variation of KD-tree named randomized KD-tree,
hold significant potential for future applications. that introduces some randomness in the splitting process,
which can improve the performance of KD-tree by reducing
A. Nearest Neighbor Search its sensitivity to noise and outliers [58].
1) Brute Force Approach: A brute force algorithm for the Ball-Tree [59], [60], [61]. It is a technique for finding the
NNS problem scans all points in the dataset, computing their nearest neighbors of a given vector in a large collection of
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 7

vectors. It works by building a ball-tree, which is a binary The R-tree algorithm also uses two metrics to measure the
tree that partitions the data points into balls, i.e. hyperspheres quality of a node split: area and overlap. The area of a node is
that contain a subset of the points. Each node of the ball- the area of its MBR, and the overlap of two nodes is the area
tree defines the smallest ball that contains all the points in its of the intersection of their MBRs. The formula for computing
subtree. The algorithm then searches for the closest ball to the the area of a node N is:
query point, and then searches within the closest ball to find
the closest point to the query point.
area(N ) = ([Link] − [Link] ) × (N · ymax − N · ymin )
To query for the nearest neighbor of a given point, the
(5)
ball tree algorithm uses a priority queue to store the nodes
where [Link] , [Link] , [Link] , and [Link] are the coordi-
to be visited, sorted by their distance to the query point. The
nates of the MBR of node N .
algorithm starts from the root node and pushes its two children
The advantage of R-tree is that it can support spatial
to the queue. Then, it pops the node with the smallest distance
queries, such as range queries or nearest neighbor queries, on
from the queue and checks if it is a leaf node or an internal
data points that represent geographical coordinates, rectangles,
node. If it is a leaf node, it computes the distance between the
polygons, or other spatial objects. R-tree search performance
query point and each data point in the node, and updates the
depends on roughly the same factors as B-tree, and also faces
current best distance and nearest neighbor if necessary. If it is
similar challenges as B-tree.
an internal node, it pushes its two children to the queue, with
M-Tree [63]. It is a technique for finding the nearest
their distances computed as follows:
neighbors of a given vector in a large collection of vectors.
It works by building an M-tree, which is a tree data structure
dL (q, N ) = max(0, [Link] − ∥q − [Link]∥) that partitions the data points into balls, i.e. hyperspheres that
(3)
dR (q, N ) = max(0, ∥q − [Link]∥ − [Link]) contain a subset of the points. Each node of the M-tree defines
where q is the query point, N is the internal node, [Link] the smallest ball that contains all the points in its subtree. The
is the center of the ball associated with N , and [Link] is the algorithm then searches for the closest ball to the query point,
radius of the ball associated with N . The algorithm repeats this and then searches within the closest ball to find the closest
process until the queue is empty or a termination condition is point to the query point.
met. The M-tree algorithm uses the concept of covering radius to
The advantage of ball-tree is that it can perform well represent the spatial objects in the tree. The covering radius of
in high-dimensional spaces, as it can avoid the curse of a node is the maximum distance from the node’s routing object
dimensionality that affects other methods such as KD-tree. The to any of its children objects. The formula for computing the
performance of ball-tree depends on several factors, such as covering radius of a node N is:
the dimensionality of the data, the number of balls per node,
and the distance approximation method used. These factors r(N ) = max d([Link], [Link]) (6)
C∈[Link]
affect the trade-off between accuracy and efficiency, as well as
the complexity and scalability of the algorithm. There are also where [Link] is the routing object of node N , [Link] is
some challenges and extensions of ball-tree search, such as the set of child nodes of node N , [Link] is the routing
dealing with noisy and outlier data, choosing a good splitting object of child node C, and d is the distance function.
dimension and value for each node, or using multiple trees to The M-tree algorithm also uses two metrics to measure the
increase recall. quality of a node split: area and overlap. The area of a node
R-Tree [62]. It is a technique for finding the nearest is the sum of the areas of its children’s covering balls, and the
neighbors of a given vector in a large collection of vectors. It overlap of two nodes is the sum of the areas of their children’s
works by building an R-tree, which is a tree data structure that overlapping balls. The formula for computing the area of a
partitions the data points into rectangles, i.e. hyperrectangles node N is:
that contain a subset of the points. Each node of the R- X
tree defines the smallest rectangle that contains all the points area(N ) = πr(C)2 (7)
in its subtree. The algorithm then searches for the closest C∈ [Link]

rectangle to the query point, and then searches within the where π is the mathematical constant, and r(C) is the covering
closest rectangle to find the closest point to the query point. radius of child node C.
The R-tree algorithm uses the concept of minimum bound- The advantage of M-tree is that it can support dynamic
ing rectangle (MBR) to represent the spatial objects in the operations, such as inserting or deleting data points, by updat-
tree. The MBR of a set of points is the smallest rectangle that ing the tree structure accordingly. M-tree search performance
contains all the points. The formula for computing the MBR depends on roughly the same factors as B-tree, and also faces
of a set of points P is: similar challenges as B-tree.
   
M BR(P ) = min px , max px × min py , max py (4) B. Approximate Nearest Neighbor Search
p∈P p∈P p∈P p∈P
1) Hash-Based Approach: The core idea of the hash-
where px and py are the x and y coordinates of point p , and based approach is to reduce search complexity by mapping
× denotes the Cartesian product. high-dimensional data to lower-dimensional hash codes with
 Hash
Code N
Vector Space
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 8

Hash Code 1 where a is a random vector, b is a random scalar, and w is

a parameter that controls the size of the hash bucket. The
Query
similarity function for this family of hash functions is:
Vector Hash Code 2
d(p, q)
f (d(p, q)) = 1 − (10)
πw
Hash where d(p, q) is the Euclidean distance between p and q.
Method
Hash Code N
The advantage of LSH is that it can reduce the memory
Vector footprint and the search time by comparing the binary codes
Space
instead of the original vectors, also adapt to dynamic data sets,
by inserting or deleting codes from the hash table without
Fig. 3. The process of approximate nearest neighbor search based on hash affecting the existing codes [69].
technique
approach
harding
rding Multiple Machines
Range-based The performance of LSH depends on several factors, such as
Hash-based
artitioning Single Machines

Cache Eviction Algorithms

Primary approaches
the dimensionality of the data, the number of hash functions,
aching
FIFO MRU LFU Partitioned Cache

carefully designed hash functions, while preserving similarity the number of bits per code, and the desired accuracy and
Leader-Follower Multi-Leader
eplication

between data points. As shown in Figure 3, each high- recall. These factors affect the trade-off between accuracy and
dimensional vector is transformed into a low-dimensional hash efficiency, as well as the complexity and scalability of the
code. Similar points are mapped to the same or neighboring algorithm. There are also some challenges and extensions of
codes, so the search only needs to examine a small subset of LSH, such as dealing with noisy and outlier data, choosing
codes, greatly improving efficiency. Based on this idea, four a good hash function family, or using multiple hash tables to
representative methods will be introduced: locality-sensitive increase recall. It is improved by [70], [71], [72].
hashing, spectral hashing, Spherical Hashing, and deep hash- Spectral Hashing [73]. It is a technique for finding the
ing. The idea is to reduce the memory footprint and the search approximate nearest neighbors of a given vector in a large
time by comparing the binary codes instead of the original collection of vectors. It works by using spectral graph theory
vectors [64]. to generate hash functions that minimize the quantization
Local-Sensitive Hashing [65], [66]. It is a technique for error and maximize the variance of the binary codes. Spectral
finding the approximate nearest neighbors of a given vector hashing can perform well when the data points lie on a low-
in a large collection of vectors. It works by using a hash dimensional manifold embedded in a high-dimensional space.
function to transform the high-dimensional vectors into com- The spectral hashing algorithm works by solving an opti-
pact binary codes, and then using a hash table to store and mization problem that balances two objectives: (1) minimizing
retrieve the codes based on their similarity or distance. In the variance of each binary function, which ensures that the
LSH, hash functions are designed to preserve the locality of data points are evenly distributed among the hypercubes,
vectors. Unlike traditional hash functions, LSH increases the and (2) maximizing the mutual information between differ-
probability that similar items are mapped to the same code, ent binary functions, which ensures that the binary code is
thus increasing collisions among similar vectors. A trace of informative and discriminative. The optimization problem can
algorithm description and implementation for locally sensitive be formulated as follows:
hashing can be seen on the home page [67]. n
The LSH algorithm works by using a family of hash
X
min V ar (yi ) − λI (y1 , . . . , yn ) (11)
functions that use random projections or other techniques y1 ,...,yn
i=1
which are locality sensitive, meaning that similar vectors are
more likely to have the same or similar codes than dissimilar where yi is the i-th binary function, V ar (yi ) is its variance,
vectors [68], which satisfy the following property: I (y1 , . . . , yn ) is the mutual information between all the binary
functions, and λ is a trade-off parameter.
The advantage of spectral hashing is that it can perform
Pr[h(p) = h(q)] = f (d(p, q)) (8)
well when the data points lie on a low-dimensional mani-
where h is a hash function, p and q are two points, d is a fold embedded in a high-dimensional space. Spectral hashing
distance function, and f is a similarity function. The similarity search performance depends on roughly the same factors as
function f is a monotonically decreasing function of the local-sensitive hashing. There are also some challenges and
distance, such that the closer the points are, the higher the extensions of spectral hashing, such as dealing with noisy and
probability of collision. outlier data, choosing a good graph Laplacian for the data
manifold, or using multiple hash functions to increase recall.
There are different families of hash functions for different
Spherical Hashing. Spherical hashing is a binary encod-
distance functions and similarity functions. For example, one
ing technique based on hyperspheres, designed for efficient
of the most common families of hash functions for Euclidean
ANNS. Unlike traditional hyperplane-based methods, it parti-
distance and cosine similarity is:
tions the data space using hyperspheres, which define tighter
and more compact regions through their centers and radii.
 
a·p+b
h(p) = (9) Each spherical hashing function, as described by Heo [74], is
w
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 9

characterized by (pk ∈ RD ) and a distance threshold tk ∈ R+ , neural network, the loss function used to train the network, and
as detailed below: the number of bits per code. These factors affect the trade-off
( between accuracy and efficiency, as well as the complexity and
−1 when d (pk , x) > tk scalability of the algorithm. There are also some challenges
hk (x) = (12)
+1 when d (pk , x) ≤ tk and extensions of deep hashing, such as dealing with noisy and
outlier data, choosing a good initialization for the network, or
where d(·, ·) is the Euclidean distance between two points using multiple hash functions to increase recall.
in D-dimensional real space; however, alternative distance 2) Tree-Based Approach: The main idea of the tree-based
metrics, such as the Lp-norms, could also be employed in approach is to build hierarchical or recursively partitioned data
place of the Euclidean distance. The output of each spherical structures, such as trees, to break high-dimensional datasets
hashing function hk (x) determines if the point x resides into smaller subsets. This method improves query efficiency
within the hypersphere that has pk as its center and tk by reducing the number of points that need to be searched.
as its radius. To improve similarity measurement, spherical Along this line, three tree-based methods will be presented:
hashing introduces the spherical Hamming distance, which approximate nearest neighbors oh yeah, best bin first, and k-
accounts for the number of shared hyperspheres. The spherical means tree. The idea is to reduce the search space by following
Hamming distance is formulated as follows: the branches of the tree that are most likely to contain the
|bi ⊕ bj | nearest neighbors of the query point.
dshd (bi , bj ) = (13) Approximate Nearest Neighbors Oh Yeah [79]. It is
|bi ∧ bj |
a technique which can perform fast and accurate similarity
where |bi ⊕ bj | represents the number of different bits (where search and retrieval of high-dimensional vectors. It works by
the XOR operation results in 1) between two binary codes, building a forest of binary trees, where each tree splits the
|bi ∧ bj | represents the number of common bits (where the vector space into two regions based on a random hyperplane.
AND operation results in 1) between the two binary codes. Each vector is then assigned to a leaf node in each tree based
Compared to hyperplane-based hashing functions, spher- on which side of the hyperplane it falls on. To query a vector,
ical hashing can map more spatially coherent data points Annoy traverses each tree from the root to the leaf node that
into binary codes. Moreover, in high-dimensional spaces, contains the vector, and collects all the vectors in the same
hyperspheres are more powerful than hyperplanes in defining leaf nodes as candidates. Then, it computes the exact distance
closed regions, allowing more potential nearest neighbors to or similarity between the query vector and each candidate, and
be captured within the binary code region of a query point. returns the top k nearest neighbors.
Deep Hashing [75], [76]. It is a technique for finding the The formula for finding the median hyperplane between two
approximate nearest neighbors of a given vector in a large points p and q is:
collection of vectors. It works by using a deep neural network
to learn hash functions that transform high-dimensional vec- w·x+b=0 (15)
tors into compact binary codes, and then using a hash table
to store and retrieve the codes based on their similarity or where w = p − q is the normal vector of the hyperplane, x is
distance [77]. The hash functions are designed to preserve the any point on the hyperplane, and b = − 21 (w · p + w · q) is the
semantic information of the vectors, which means that similar bias term. The formula for assigning a point x to a leaf node
vectors are more likely to have the same or similar codes than in a tree is:
dissimilar vectors [78]. sign (wi · x + bi ) (16)
The deep hashing algorithm works by optimizing an ob-
jective function that balances two terms: (1) a reconstruction where wi and bi are the normal vector and bias term of the
loss that measures the fidelity of the binary codes to the i-th split in the tree, and sign is a function that returns 1 if the
original data points and (2) a quantization loss that measures argument is positive, −1 if negative, and 0 if zero. The point
the discrepancy between the binary codes and their continu- x follows the left or right branch of the tree depending on the
ous relaxations. The objective function can be formulated as sign of this expression, until it reaches a leaf node.
follows: The formula for searching for the nearest neighbor of a
query point q in the forest is:
N
X 2 2
min ∥xi − W bi ∥2 + λ ∥bi − sgn (bi )∥2 (14) min d(q, x) (17)
W,B x∈C(q)
i=1

where xi is the i-th data point, bi is its continuous relaxation, where C(q) is the set of candidate points obtained by travers-
sgn (bi ) is its binary code, W is a weight matrix that maps the ing each tree in the forest and retrieving all the points in the
binary codes to the data space, and λ is a trade-off parameter. leaf node that q belongs to, and d is a distance function, such
The advantage of deep hashing is that it can leverage the as Euclidean distance or cosine distance. The algorithm uses
representation learning ability of neural networks to generate a priority queue to store the nodes to be visited, sorted by
more discriminative and robust codes for complex data, such their distance to q. The algorithm also prunes branches that
as images, texts, or audios. The performance of deep hashing are unlikely to contain the nearest neighbor by using a bound
depends on several factors, such as the architecture of the on the distance between q and any point in a node.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 10

The advantage of Annoy is that it can uses multiple random

projection trees to index the data points, which can increase Nearest Starting
Vector Node
the recall and robustness of the search, also reduce the memory
usage and improve the speed of NNS, by creating large read-
only file-based data structures that are mapped into memory so
that many processes can share the same data. The performance
of Annoy depends on several factors, such as the dimensional-
Query
ity of the data, the number of trees built, the number of nearest Vector
candidates to search, and the distance approximation method
used. These factors affect the trade-off between accuracy and
efficiency, as well as the complexity and scalability of the Fig. 4. The process of performing nearest neighbor search on a small-world
network.
algorithm. There are also some challenges and extensions of
Annoy, such as dealing with noisy and outlier data, choosing a
good splitting plane for each node, or using multiple distance The formula for searching for the nearest neighbor of a
metrics to increase recall. query point q in the k-means tree is:
Best Bin First [80], [81]. It is a technique for finding
the approximate nearest neighbors of a given vector in a min ∥q − x∥22 (20)
x∈C(q)
large collection of vectors. It works by building a kd-tree that
partitions the data points into bins, and then searching for the where C(q) is the set of candidate points obtained by travers-
closest bin to the query point. The algorithm then searches ing each branch of the tree and retrieving all the points in
within the closest bin to find the closest point to the query the leaf nodes that q belongs to. The algorithm uses a priority
point. The best bin first algorithm still follows (1) (2). The queue to store the nodes to be visited, sorted by their distance
advantage of best bin first is that it can reduce the search to q. The algorithm also prunes branches that are unlikely to
time and improve the accuracy of NNS, by focusing on the contain the nearest neighbor by using a bound on the distance
most promising bins and avoiding unnecessary comparisons between q and any point in a node.
with distant points. The performance of best bin first depends The advantage of K-means tree is that it can perform fast
on several factors, such as the dimensionality of the data, the and accurate similarity search and retrieval of data points based
number of bins per node, the number of nearest candidates to on their cluster membership, by following the branches of the
search, and the distance approximation method used. These tree that are most likely to contain the nearest neighbors of
factors affect the trade-off between accuracy and efficiency, the query point. K-means tree can also support dynamic oper-
as well as the complexity and scalability of the algorithm. ations, such as inserting and deleting points, by updating the
There are also some challenges and extensions of best bin tree structure accordingly. The performance of K-means tree
first, such as dealing with noisy and outlier data, choosing a depends on several factors, such as the dimensionality of the
good splitting dimension and value for each node, or using data, the number of clusters per node, and the distance metric
multiple trees to increase recall. used. These factors affect the trade-off between accuracy and
K-means Tree [82]. It is a technique for clustering high- efficiency, as well as the complexity and scalability of the
dimensional data points into a hierarchical structure, where algorithm. There are also some challenges and extensions of
each node represents a cluster of points. It works by applying K-means tree, such as dealing with noisy and outlier points,
a k-means clustering algorithm to the data points at each level choosing a good initialization for the k-means algorithm, or
of the tree, and then creating child nodes for each cluster. The using multiple trees to increase recall.
process is repeated recursively until a desired depth or size of 3) Graph-Based Approach: The core concept of the graph-
the tree is reached. based approach is the small-world network. A small-world
The formula for assigning a point x to a cluster using the network is a complex network where most nodes are not
k-means algorithm is: directly connected, but almost any node can be reached from
another in just a few steps. This means the average path
2 length between any two nodes is much shorter than the total
arg min ∥x − ci ∥2 (18)
i=1,...,k number of nodes. The ”six degrees of separation” theory in
sociology [83] is a concrete manifestation of a small-world
where argmin is a function that returns the argument that network.
minimizes the expression, and ∥ · ∥2 denotes the Euclidean
Given a query vector q and the task finding the k closest
norm. The formula for assigning a point x to a leaf node in a
vectors from a set O, the graph-based approach uses a graph
k-means tree is:
G(V, E) to represent these objects, where each object oi
corresponds to a node vi . The small-world network graph is
arg min ∥x − [Link]∥22 (19)
N ∈L(x) constructed by sequentially adding all nodes. As shown in
Figure 4, when a new node is added, a list of neighboring
where L(x) is the set of leaf nodes that x belongs to, and N nodes is generated using a greedy algorithm, and bidirectional
.center is the cluster center of node N . The point x belongs to connections are established between the new node and all
a leaf node if it belongs to all its ancestor nodes in the tree. nodes in the list. Once the graph is constructed, searching for
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 11

q is similar to the process of adding a new node. The search the trade-off between accuracy and efficiency, as well as
starts from a randomly selected node (with different small- the complexity and scalability of the algorithm. There are
world variants possibly using different selection strategies). also some extensions and variations of the NSW algorithm,
From the list of neighbors of the current node, the node most such as hierarchical navigable small world (HNSW), which
similar to q is identified. If such a node is found, it becomes adds multiple layers of graphs, each with different scales and
the next node, and the search process is repeated. If a node densities, or navigable small world with pruning (NSWP),
has a higher similarity to q than all of its neighbors, the search which removes redundant links to reduce memory usage and
stops, and that node is considered the one most similar to q. improve search speed.
Two types of graph-based methods are introduced: navigable Hierachical Navigable Small World [87]. It is a state-of-
small world (NSW), and hierachical navigable small world the-art technique for finding the approximate nearest neighbors
(HNSW). of a given vector in a large collection of vectors. It works by
Navigable Small World It is a technique that uses a graph building a graph structure that connects the vectors based on
structure to store and retrieve high-dimensional vectors based their similarity or distance, and then using a greedy search
on their similarity or distance [84]. The NSW algorithm builds strategy to traverse the graph and find the most similar vectors.
a graph by connecting each vector to its nearest neighbors, The HNSW algorithm still follows (21) and (22). The HNSW
as well as some random long-range links that span different algorithm also builds a hierarchical structure of the graph
regions of the vector space. The idea is that these long-range by assigning each point to different layers with different
links create shortcuts that allow for faster and more efficient probabilities. The higher layers contain fewer points and edges,
traversal of the graph, similar to how social networks have while the lower layers contain more points and edges. When a
small world properties [85]. search query comes in, the HNSW algorithm finds the closest
The NSW algorithm works by using a greedy heuristic to matching data points in the highest layer. It then proceeds
add edges to the graph [86]. The algorithm starts with an layer by layer, moving downwards and finding the nearest data
empty graph and adds one point at a time. For each point, points in each subsequent layer based on those from the layer
the algorithm finds its nearest neighbor in the graph using above. These points are considered the nearest neighbors. The
a random walk, and connects it with an edge. Then, the algorithm continues this process in the lower layers, updating
algorithm adds more edges by connecting the point to other the list of nearest neighbors at each step. Once it reaches the
points that are closer than its current neighbors. The algorithm bottom layer, the HNSW algorithm returns the data points that
repeats this process until all points are added to the graph. are closest to the search query. The algorithm uses a parameter
The formula for finding the nearest neighbor of a point p M to control the maximum number of neighbors for each point
in the graph using a random walk is: in each layer.
The formula for assigning a point p to a layer l using a
arg min d(p, q) (21) random probability is:
q∈N (p) 
1 if l = 0
where N(p) is the set of neighbors of p in the graph, and Pr[p ∈ l] = 1 (23)
M if l > 0
d is a distance function, such as Euclidean distance or cosine
distance. The algorithm starts from a random point in the graph where M is the parameter that controls the maximum number
and moves to its nearest neighbor until it cannot find a closer of neighbors for each point in each layer. The algorithm
point. The formula for adding more edges to the graph using assigns p to layer l with probability Pr[p ∈ l], and stops when
a greedy heuristic is: it fails to assign p to any higher layer.
The formula for searching for the nearest neighbor of a
∀q ∈ N (p), ∀r ∈ N (q), if d(p, r) < d(p, q), query point q in the hierarchical graph is:
(22)
then add edge (p, r)
min d(q, p) (24)
p∈C(q)
where N (p) and N (q) are the sets of neighbors of p and q
in the graph, respectively, and d is a distance function. The where C(q) is the set of candidate points obtained by travers-
algorithm connects p to any point that is closer than its current ing each layer of the graph from top to bottom and retrieving
neighbors. all the points that are closer than the current best distance.
The advantage of the NSW algorithm is that it can handle The algorithm uses a priority queue to store the nodes to be
arbitrary distance metrics, it can adapt to dynamic data sets, visited, sorted by their distance to q. The algorithm also prunes
and it can achieve high accuracy and recall with low memory branches that are unlikely to contain the nearest neighbor by
consumption. The NSW algorithm also uses a greedy routing using a bound on the distance between q and any point in a
strategy, which means that it always moves to the node that is node.
closest to the query vector, until it reaches a local minimum The advantage of HNSW is that it can achieve better
or a predefined number of hops. performance than other methods of ANNS, such as tree-
The performance of the NSW algorithm depends on several based or hash-based techniques. For example, it can handle
factors, such as the dimensionality of the vectors, the number arbitrary distance metrics, it can adapt to dynamic data sets,
of neighbors per node, the number of long-range links per and it can achieve high accuracy and recall with low memory
node, and the number of hops per query. These factors affect consumption. HNSW also uses a hierarchical structure that
 JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 12
Vectors

allows for fast

𝑠𝑠12 and accurate search, by starting from the highest
layer and moving down to the lowest layer, using the closest 𝑠𝑠5
𝑠𝑠9 𝑠𝑠6
node as the next hop 𝑠𝑠10 at each layer. So, HNSW can effectively 𝑠𝑠11
“jump over” large portions of data that 𝑠𝑠8 don’t require searching.
Suppose a data store has only a single𝑠𝑠 layer. In that case, 𝑠𝑠7 𝑠𝑠4 Codeword
𝑠𝑠10
7 𝑠𝑠12
the search 𝑠𝑠algorithm
Codewords 11 is unable to bypass unrelated objects,
meaning it has to examine 𝑠𝑠3 many more data points, even if 𝑠𝑠9
Vector
they are unlikely to be relevant matches. 𝑠𝑠6 𝑠𝑠8 𝑠𝑠13
The performance of HNSW depends 𝑠𝑠4 on several factors, such 𝑠𝑠1
𝑠𝑠1 𝑠𝑠2 the vectors, the 𝑠𝑠3
as the dimensionality of 𝑠𝑠5 number of layers, the
number of neighbors per node, and the number Voronoiof hops per
Region
query. These factors affect the trade-off between accuracy and 𝑠𝑠2 Voronoi
efficiency, as well as the complexity and scalability of the Region
algorithm. There are also some challenges and extensions of
HNSW, such as finding the optimal parameters for the graph Fig. 5. Codewords and Voronoi Regions in a Two-Dimensional Space
construction, dealing with noise and outliers, and scaling to
r
very large data sets. Some of the extensions include optimized Encoder Hash Code N

product quantization (OPQ), which combines HNSW with Input Vector Output Vector

product quantization to reduce quantization distortions, or Codebook Indices

product quantization network (PQN), which uses a neural

network to learn an end-to-end product quantizer from data.
4) Quantization-Based Approach: The core idea of quan- Search
Engine

tization is to map points in a high-dimensional space to a

low-precision representation in a finite set. This reduces the
number of bits required for storage, lowering storage demands.
Fig. 6. Vector Quantization Process with Encoder and Decoder Operations
By using these quantized representations during queries, the
distance between the original points can be quickly estimated.
Specifically, a vector quantizer maps k-dimensional vectors the appropriate number of codewords. Designing an optimal
from the vector space Rk to a finite set of vectors S = {si : codebook is an NP-hard problem, implying that finding the
i = 1, . . . , n}. Each vector si is called a code vector or code- absolute best set of codewords through exhaustive search
word or centroids. The collection of all codewords is referred becomes impractically complex as the number of codewords
to as a codebook. Associated with each codeword, si , is a increases. As a result, heuristic methods, such as the Linde-
nearest neighbor
 region called Voronoi region, and it is defined Buzo-Gray (LBG) algorithm, which is conceptually similar to
by: Vi = x ∈ Rk : ∥x − yi ∥ ≤ ∥x − yj ∥ , forall j ̸= i . The the K-means clustering algorithm, are commonly employed.
set of Voronoi region partitions the entire space Rk such that: To create a codebook using the LBG algorithm, one first
N
[ specifies the number of codewords, N , which defines the
Vi = Rk size of the codebook. Initially, N codewords are selected at
i=1 random, often from the set of input vectors themselves. Each
N
input vector is then associated with the nearest codeword based
\
Vi = ϕ for all i ̸= j on the Euclidean distance. After all vectors have been assigned
i=1
to their respective clusters, a new set of codewords is generated
by computing the average of the vectors within each cluster.
Figure 5 shows the codewords in a two-dimensional space, This process involves summing the components of the vectors
where input vectors are marked with blue stars, codewords in each cluster and dividing by the total number of vectors
are marked with orange circles, and the Voronoi regions are in that cluster. This iterative procedure refines the codebook
separated with boundary lines. until a satisfactory level of representation is achieved. The
A vector quantizer consists of two primary components: formula for calculating the average of the components within
an encoder and a decoder, as shown in figure6. The encoder each cluster is: m
takes an input vector and outputs the index of the codeword 1 X
that minimizes the distortion. This minimal distortion is found yi = xij
m j=1
by calculating the distance between the input vector and
each codeword in the codebook, typically using metrics like where i is the component of each vector , m is the number of
Euclidean or Hamming distance. Once the codeword with vectors in the cluster. There are also many other methods to de-
the smallest distance is identified, its index is transmitted signing the codebook, methods such as Generative Pre-trained
to the decoder. At the receiver, the decoder then maps this Transformer Vector quantization (GPTVQ) [88], Vector Post-
index back to the corresponding codeword. Generating an Training Quantization (VPTQ) [89], deep network architecture
effective codebook involves selecting codewords that best for vector quantization (DeepVQ) [90], etc. Based on the
represent a given set of input vectors, along with determining core idea described above, six quantization-based methods will
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 13

be presented here, namely inverted file index (IVF), product where argmin is a function that returns the argument that
quantization (PQ) [91], [92], optimized product quantization minimizes the expression, and ∥ · ∥2 denotes the Euclidean
(OPQ) [93], [94], online product quantization [95], scalable norm.
nearest neighbor (ScaNN) [96], and inverted file product The formula for encoding a vector x using PQ is:
quantization (IVF PQ) [40], [97]. Product quantization can
reduce the memory footprint and search time of ANN search, c(x) = (q1 (x1 ) , q2 (x2 ) , . . . , qm (xm )) (28)
by comparing codes instead of the original vectors [98]. where xi is the i-th subvector of x, and qi is the quantization
Inverted File Index. Inverted File Index is a technique function for the i-th subvector, which returns the index of the
designed to enhance search efficiency by narrowing the search nearest centroid in the codebook.
area through the use of neighbor partitions or clusters [99]. It The advantage of product quantization is that it is simple
uses clustering (e.g., K-means) to partition high-dimensional and easy to implement, as it only requires a standard clustering
vectors into multiple regions (Voronoi Cells) and records the algorithm and a simple distance approximation method.
vectors within each region through an inverted index. During The performance of product quantization depends on several
a query, the search is restricted to a few regions closest to factors, such as the dimensionality of the data, the number
the query vector, significantly reducing the search space and of sub-vectors, the number of centroids per sub-vector, and
improving retrieval efficiency. IVF is often combined with the distance approximation method used. These factors affect
other techniques, such as Product Quantization (PQ), to further the trade-off between accuracy and efficiency, as well as the
optimize storage and computation, making it widely used in complexity and scalability of the algorithm. There are also
image retrieval, recommendation systems, and VDBs. Its main some challenges and extensions of product quantization, such
advantages are fast search speed and high efficiency, though as dealing with noisy and outlier data, optimizing the space
its performance in high-dimensional spaces may be limited by decomposition and the codebooks, or adapting to dynamic data
clustering quality and the complexity of dynamic updates. sets.
Product Quantization . It is a technique for compress- Optimized Product Quantization [93]. It is a variation of
ing high-dimensional vectors into smaller and more efficient product quantization (PQ), which is a technique for compress-
representations [91], [92]. It works by dividing a vector into ing high-dimensional vectors into smaller and more efficient
several sub-vectors, and then applying a clustering algorithm representations. OPQ works by optimizing the space decompo-
(such as k-means) to each sub-vector to assign it to one of a sition and the codebooks to minimize quantization distortions.
finite number of possible values (called centroids). The result OPQ can improve the performance of PQ by reducing the loss
is a compact code that consists of the indices of the centroids of information and increasing the discriminability of the codes
for each sub-vector. [94].
The PQ algorithm works by using a vector quantization The advantage of OPQ is that it can achieve higher accuracy
technique to map each subvector to its nearest centroid in a and recall than PQ, as it can better preserve the similarity or
predefined codebook. The algorithm first splits each vector into distance between the original vectors.
m equal-sized subvectors, where m is a parameter that controls The formula for applying a random rotation to the data is:
the length of the code. Then, for each subvector, the algorithm
learns k centroids using the k-means algorithm, where k is a x′ = Rx (29)
parameter that controls the size of the codebook. Finally, the where x is the original vector, x′ is the rotated vector, and
algorithm assigns each subvector to its nearest centroid and R is a random orthogonal matrix. The formula for finding the
concatenates the centroid indices to form the code. rotation matrix for a subvector using an optimization technique
The formula for splitting a vector x into m subvectors is: is: X 2
min ∥x − Ri ci (Ri x)∥2 (30)
Ri
x = (x1 , x2 , . . . , xm ) (25) x∈Pi

where Pi is the set of subvectors assigned to the i-th cluster,

where xi is the i-th subvector of x, and has dimension d/m,
Ri is the rotation matrix for the i-th cluster, and ci is the
where d is the dimension of x.
quantization function for the i-th cluster, which returns the
The formula for finding the centroids of a set of subvectors
nearest centroid in the codebook.
P using the k-means algorithm is:
The formula for encoding a vector x using OPQ is:
1 X c(x) = (q1 (R1 x1 ) , q2 (R2 x2 ) , . . . , qm (Rm xm )) (31)
ci = x (26)
|Si |
x∈Si
where xi is the i-th subvector of x, Ri is the rotation matrix for
where ci is the i-th centroid, Si is the set of subvectors the i -th subvector, and qi is the quantization function for the
assigned to the i -th cluster, and | · | denotes the cardinality of i-th subvector, which returns the index of the nearest centroid
a set. in the codebook.
The formula for assigning a subvector x to a centroid using The performance of OPQ depends on several factors, such
the k-means algorithm is: as the dimensionality of the data, the number of sub-vectors,
the number of centroids per sub-vector, and the distance
2
argmini=1,...,k ∥x − ci ∥2 (27) approximation method used. These factors affect the trade-off
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 14

between accuracy and efficiency, as well as the complexity and O-PQ search performance depends on roughly the same
scalability of the algorithm. There are also some challenges factors as OPQ, and also faces similar challenges as OPQ.
and extensions of OPQ, such as dealing with noisy and outlier Scalable Nearest Neighbor. It is a technique for efficient
data, choosing a good optimization algorithm, or combining vector similarity search at scale [96], [101]. ScaNN optimizes
OPQ with other techniques such as hierarchical navigable Maximum Inner Product Search (MIPS) through search space
small world (HNSW) or product quantization network (PQN). pruning and quantization. Traditional MIPS schemes aim to
Online Product Quantization [100]. It is a variation of minimize the average distance between each vector x and its
product quantization (PQ), which is a technique for compress- centroids x̃, that is, to minimize quantization distortions.
ing high-dimensional vectors into smaller and more efficient The formula for typically measure the quantization distor-
representations. Online product quantization (O-PQ) works by tion is:
N
adapting to dynamic data sets, by updating the quantization 1 X 2
D= ∥xi − x̃i ∥2 (38)
codebook and the codes online. O-PQ can handle data streams N i=1
and incremental data sets, without requiring offline retraining
or reindexing. where N is the total number of vectors, xi is original vector,
The formula for splitting a vector x into m subvectors is: x̃ is quantized centroid, and ∥ · ∥2 denotes Euclidean norm.
While the ScaNN algorithm argues that optimizing the
x = (x1 , x2 , . . . , xm ) (32) average distance is not equivalent to optimizing the accuracy
of nearest-neighbor searches. The hypothesis it puts forward
where xi is the i-th subvector of x, and has dimension d/m, is that the objective of maximizing the inner product between
where d is the dimension of x. two points is not entirely consistent with the objective of
The formula for initializing the centroids of a set of sub- minimizing the average distance between two points.
vectors P using the k-means++ algorithm is: ScaNN taking into account the distribution characteristics of
ci = randomly choose a point from P (33) the data in different directions, ellipsoidal or other shaped re-
gions are used instead of spherical regions around the centroids
where ci is the i-th centroid, with probability proportional to to better fit the local structure of the data. Building on this
D(x)2 , D(x) is the distance between point x and its closest perspective, the anisotropic loss function can further enhance
centroid among {c1 , . . . , ci−1 }. the adaptability of vector quantization to data anisotropy.
The formula for assigning a subvector x to a centroid using By explicitly separating quantization errors into parallel and
PQ is: orthogonal components, the anisotropic loss function assigns
2
argmini=1,...,k ∥x − ci ∥2 (34) ∥
distinct scaling parameters hi and h⊥ i to these components,
where arg min is a function that returns the argument that respectively. This allows for more fine-grained control over the
minimizes the expression, and ∥ · ∥2 denotes the Euclidean quantization process, ensuring that the errors are distributed in
norm. alignment with the data’s geometric characteristics.
The formula for encoding a vector x using PQ is: The anisotropic vector quantization algorithm shares sim-
ilarities with the Lloyd algorithm, iteratively refining the
c(x) = (q1 (x1 ) , q2 (x2 ) , . . . , qm (xm )) (35) codebook and data partitions. The key distinction lies in the
where xi is the i-th subvector of x, and qi is the quantization update rule for the codebook centroids:
function for the i-th subvector, which returns the index of the ∥ ∥
hi · xi + h⊥ ⊥
P
nearest centroid in the codebook. i∈Xj i · xi
cj =   (39)
The O-PQ algorithm also updates the codebooks and codes
P ∥ ⊥
i∈Xj hi + hi
for each subvector using an online learning technique. The
algorithm uses two parameters: α, which controls the learning where Xj is the set of data points assigned to the codeword cj .
rate, and β, which controls the forgetting rate. The algorithm This update formula takes into account the directional scaling,
updates the codebooks and codes as follows: ensuring that the resulting codewords are optimally positioned
For each new point x, assign it to its nearest centroid in in accordance with the anisotropic properties of the data.
each subvector using PQ. By integrating this anisotropic loss framework, the quanti-
For each subvector xi , update its centroid cqi (xi ) as: zation process moves beyond spherical symmetry and better
accommodates ellipsoidal or irregularly shaped distributions
cqi (xi ) = (1 − α)cqi (xi ) + αxi (36) in the data. This alignment with ScaNN’s approach to using
For each subvector xi , update its code qi (xi ) as: ellipsoidal regions around centroids enhances both the repre-
2 sentation accuracy and the retrieval efficiency, especially in
qi (xi ) = arg min ∥(1 − β)xi + βxi − (1 − β)cj + βcj ∥2 cases where the data exhibits significant directional variance.
j=1,...,k
(37) Moreover, extending this concept to product quantization
where xi and cj are the mean vectors of all points and allows the construction of multiple subspace-specific dictio-
centroids in subvector i, respectively. naries, each tuned to the anisotropic characteristics of the
The advantage of O-PQ is that it can deal with changing corresponding subspace. This not only retains the efficiency
data distributions and new data points, as it can update the of ScaNN’s design but also adds a layer of flexibility for
codebooks and the codes in real time. handling complex, high-dimensional data distributions. The
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 15

performance of ScaNN depends on several factors, such as the ular options, including PgVector2 , QdrantCloud3 , Weaviate-
anisotropy of the data distribution, the choice of quantization Cloud4 , ZillizCloud5 , Milvus6 , ElasticCloud7 , and Pinecone8 .
methods like vector or product quantization, the size and The comparison of VDBs includes both the attributes and
quality of the codebooks, and the efficiency of the partitioning characteristics of different VDBs, as well as a comparison of
and scoring processes. These factors impact the trade-off their loading capacity and search performance.
between retrieval accuracy and computational speed, as well as 1) The Comparison of Features and Characteristics of
the scalability of the algorithm for massive datasets. Additional Vector Databases: The characteristics of VDBs directly affect
challenges and potential extensions include handling highly ir- their performance in practical applications. Therefore, gaining
regular data distributions, selecting optimal scaling parameters a deep understanding of these databases’ features is essential
for the score-aware loss function, and integrating ScaNN with for selecting the most suitable one. As shown in Table I, we
complementary techniques like hierarchical search structures compare several popular VDBs, focusing on their differences
or advanced compression methods. in indexing methods, query types, distance functions, scala-
Inverted File Product quantization. It is a widely used bility, maximum dimension, and support for data management
technique for approximate nearest neighbor (ANN) search features such as replication, sharding, and partitioning.
in high-dimensional vector spaces [40], [97]. This algorithm It can be observed from the table I that all VDBs sup-
is a combination of the Inverted File Indexing (IVF) and port NNS and ANNS. However, the implementation strate-
Product Quantization (PQ) algorithms. IVF PQ first uses the gies and optimizations for these searches vary significantly
IVF algorithm to divide or partition the data into clusters and across databases, depending on their underlying indexing
uses the parameter nprobe to control the number of clusters. methods and architectural designs. For example, the indexing
The higher the nprobe, the better the search results, but it methods and distance functions are not exactly the same
also increases the time required. It then identifies the top-N across databases, but there are commonalities. For instance,
clusters closest to the query vector and performs the search all databases except Pinecone support graph-based methods,
within these N clusters using the Product Quantization (PQ) which indicates that graph-based methods are widely adopted
algorithm. for their ability to handle complex relationships and data
The IVF PQ algorithm naturally results in two different structures. Additionally, the majority of databases also support
approaches when using the PQ algorithm: the first involves three distance functions: inner product, cosine similarity, and
performing K-means clustering with the IVF algorithm, fol- Euclidean distance. For details on the indexing methods and
lowed by applying a local PQ algorithm for dimensionality distance functions supported by different databases, see the
reduction within each cluster; the second also starts with the table II and table III below.
IVF algorithm to divide all data points into several clusters Scalability is a critical factor in evaluating the performance
but applies a globally unified PQ algorithm for dimensionality and flexibility of VDBs, especially for large-scale and high-
reduction within each [Link] addition, there is another demand applications. Scalability is typically categorized into
implementation scheme for the IVFPQ algorithm in FAISS horizontal scaling and vertical scaling. Horizontal scaling
(Facebook AI Similarity Search)1 . First, all data points are refers to a database’s ability to distribute data and computation
clustered using the IVF algorithm. Then, for all data points across multiple nodes, allowing it to handle large datasets
within each cluster, the difference between each point and its and high query throughput. This approach is particularly
cluster center (referred to as the ”””residual”) is calculated. beneficial for cloud-native environments and distributed archi-
Mathematically, the residual represents the offset of a data tectures, where data is sharded and replicated across multiple
point relative to its cluster center. This operation is equivalent machines. In contrast, vertical scaling involves upgrading a
to shifting all cluster centers to the origin, causing all points single machine with more resources, such as additional CPU
to focus around the origin. Afterward, the PQ algorithm power or memory, to manage increased workloads. Both
is applied to the residuals. Compared to the previous two scaling methods offer distinct advantages depending on the
approaches, the key difference is that PQ is applied to the application’s requirements and the environment in which the
residuals rather than the original vectors. The advantage of database operates. Specifically, PgVector, QdrantCloud, and
this scheme is that, as the data points become more tightly Pinecone support both horizontal and vertical scaling modes,
clustered, the average size of each cluster region is smaller, while WeaviateCloud, Milvus, and ElasticCloud only support
leading to reduced approximation errors during distance com- horizontal scaling. ZillizCloud is the only one that supports
putations. only vertical scaling. Although the level of support for scala-
bility varies across databases, most exhibit strong capabilities
IV. V ECTOR DATABASE C OMPARISON in data storage and backup. Specifically, all databases, except
for ElasticCloud, for which no relevant information was found,
In the realm of VDBs, a variety of storage and search
2 [Link]
technologies has given rise to a diverse range of commercial
3 [Link]
and open-source solutions. In this section, to help users 4 [Link]
better understand the performance of different VDBs, we 5 [Link]
have conducted a comprehensive comparison of several pop- 6 [Link]
7 [Link]
1 [Link] 8 [Link]
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 16

TABLE I
FEATURES OF VECTOR DATABASES

Maximum
Database Query Types Indexing Methods NSD Scalability Replication Sharding Partitioning
Dimension
Brute Tree Hash Graph Quantization Horizontal Vertical
ANNS NNS
Force Based Based Based Based Scaling Scaling

PgVector ✓ ✓ ✓ ✓ ✓ ✓ ✓ 7 ✓ ✓ ✓ ✓ ✓ 16,000

QdrantCloud ✓ ✓ ✓ × × ✓ ✓ 4 ✓ ✓ ✓ ✓ ✓ 65,535

WeaviateCloud ✓ ✓ ✓ × × ✓ × 6 ✓ × ✓ ✓ ✓ 65,535

ZillizCloud ✓ ✓ ✓ × ✓ ✓ ✓ 4 × ✓ ✓ ✓ ✓ 32,768

Milvus ✓ ✓ ✓ × × ✓ ✓ 6 ✓ × ✓ ✓ ✓ 32,768

ElasticCloud ✓ ✓ ✓ × × ✓ × 4 ✓ × ✓ ✓ ✓ N/A

Pinecone ✓ ✓ N/A N/A N/A N/A N/A 3 ✓ ✓ ✓ ✓ ✓ N/A

Abbreviations: NSD Number of Supported Distance Functions, N/A Unknown, ✓ Support, × Not Support
The database information listed above is based on data up to December 1, 2024.

TABLE II
OVERVIEW OF S UPPORTED D ISTANCE F UNCTIONS IN V ECTOR DATABASES

PgVector QdrantCloud WeaviateCloud ZillizCloud Milvus ElasticCloud Pinecone

Inner Product ✓ ✓ ✓ ✓ ✓ ✓ ✓
Cosine Similarity ✓ ✓ ✓ ✓ ✓ ✓ ✓
Manhattan Distance ✓ ✓ ✓ × × × ×
Distance Function

Hamming Distance ✓ × ✓ ✓ ✓ × ×
Jaccard Distance ✓ × × ✓ ✓ × ×
Taxicab Distance ✓ × × × × × ×
Euclidean Distance ✓ ✓ ✓ × ✓ ✓ ✓
Structural Similarity × × × × ✓ × ×
Max Inner Product × × × × × ✓ ×
Abbreviations: ✓ Support, × Not Support
The database information listed above is based on data up to December 1, 2024.

support Replication, Sharding, and Partitioning. These features testing methodology, which provides reliable, reproducible
ensure fault tolerance, efficient data distribution, and flexible results across various VDBs. By utilizing pre-existing data,
query handling. we ensure consistency and comparability, as these results
The last column of the table I provides statistics on the have been generated under controlled conditions, following
maximum vector dimensions supported by each database. It established benchmarks.
can be observed that, with the exception of ElasticCloud and
Pinecone, for which no relevant information was available, VectorDBBench provides a comprehensive performance
most of the listed VDBs support a total vector dimension in analysis by evaluating VDBs based on metrics such as Queries
the range of tens of thousands, with the maximum supported Per Second (QPS), recall rate, latency(the time required for
dimensions ranging from 16,000 to 65,535. It should be noted each query from submission to system response), load du-
that QdrantCloud has a default support for up to 65,535 ration, and maximum load count(The maximum number of
dimensions, though this can be configured to support higher vectors a database can successfully insert or store in a single
dimensions. loading operation.). Its testing methodology employs a relative
2) The Comparison of Loading Capacity and Search Per- scoring mechanism to ensure fair comparisons. For QPS, the
formance of Vector Database: In this subsection, we have highest observed value among all tested databases serves as
opted to use the performance results obtained from the exist- the reference baseline; for latency, the lowest observed value
ing benchmarking tool, VectorDBBench(A Benchmark Tool among all tested databases is used as the baseline, with an
for VectorDB)9 , rather than conducting our own tests. This additional 10ms adjustment to avoid distortions when latency
decision is based on the tool’s comprehensive and standardized is very low. For systems that fail or encounter timeouts in a
specific test case, their scores are penalized by assigning a
9 [Link] value proportionally worse than the lowest-performing result,
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 17

TABLE III
OVERVIEW OF S UPPORTED I NDEXING M ETHODS IN V ECTOR DATABASES

PgVector QdrantCloud WeaviateCloud ZillizCloud Milvus ElasticCloud Pinecone

HNSW ✓ ✓ ✓ ✓ ✓ ✓ N/A
Flat × × ✓ × ✓ × N/A
BINFlat × × × × ✓ × N/A
IVF Flat × × × × ✓ × N/A
BIN IVF Flat × × × × ✓ × N/A
IVF SQ8 × × × × ✓ × N/A
IVF PQ × × × × ✓ × N/A
B-tree ✓ × × × × × N/A
LSH × × × ✓ × × N/A
Indexing Method

BRIN ✓ × × × × × N/A
Inverted File Index ✓ × × × ✓ ✓ N/A
SP ARSE Inverted Index × × × × × × N/A
SP ARSE W AN D × × × × ✓ × N/A
GIST ✓ × × × × × N/A
GIN ✓ × × × × × N/A
DiskANN × ✓ × ✓ × × N/A
SCANN × × × ✓ × × N/A
Sparse Vector Index × ✓ × × × × N/A
Parameterized index × ✓ × × × × N/A
Abbreviations: N/A Unknown, ✓ Support, × Not Support
The database information listed above is based on data up to December 1, 2024.

TABLE IV
VECTOR DATABASE EVALUATION TEST CASES

Case No. Case Type Dataset Dataset Size Vector Dimensions Filtering Rate Test Metrics
1 Capacity SIFT1 500K 128 N/A NIV
2 Capacity GIST2 100K 960 N/A NIV
3 Search Performance Google C43 500K 1536 N/A IBT, R, L, MQPS

1 [Link]
2 [Link]
3 The processed version of Google C4 dataset([Link]
Abbreviations: N/A. Not Applicable, NIV. Number of inserted vector, IBT. Index building time, R. Recall, L.
Latency, MQPS. Maxiumum QPS

using a factor of two. For example, in the case of QPS, the SIFT and GIST datasets. Search performance cases (Cases 3)
score is reduced to half of the minimum observed value, while evaluate index building time, recall, latency, and maximum
for latency, it is increased to twice the maximum observed QPS using Google C4 dataset dataset.
value. The formulas for calculating QPS and latency metrics
for VDB x are as follows: The VDB versions involved in the performance tests are as
follows: Milvus-2c8g-hnsw-v2.2.12 (hereafter referred to as
origin QP Sx Milvus), Pinecone-p1.x1 (hereafter referred to as Pinecone),
QP Sx = × 100 (40)
base QP S WeaviateCloud-standard (hereafter referred to as Weaviate
Cloud), ZillizCloud-2cu-cap-v2023.6 (hereafter referred to
as ZillizCloud), QdrantCloud-2c8g-1node (hereafter referred
base Latency + 10ms
Latencyx = × 100 (41) to as QdrantCloud), PgVector-2c8g (hereafter referred to as
origin Latencyx + 10ms PgVector), and ElasticCloud-upTo2.5c8g (hereafter referred to
where origin QP Sx and origin Latencyx represent the as ElasticCloud). To ensure minimal differences in hardware
original QPS value and original latency value, respectively, performance across the tested databases, a configuration of
measured for database x during the test. base QP S and 2 CPUs and 8GB of memory was specifically selected. For
base Latency is the reference baseline. VDBs that do not meet this hardware requirement, similar
Specifically, as shown in table IV, the VDB evaluation con- configurations were chosen as closely as possible. The specific
sists of a series of test cases designed to assess capacity, search test results are shown in the figure7. The overall ranking
performance, and filtering search performance. Capacity cases in the figure 7 is calculated by averaging the rankings of
(Cases 1 and 2) measure the database’s ability to handle large each sub-test item, with the final overall ranking determined
datasets, focusing on the number of inserted vectors using in ascending order of the average values. According to the
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 18

and requirements, such as dimensionality, sparsity, distribu-

tion, similarity metrics, and so on. Therefore, VDBs need
to provide a flexible and adaptive indexing system to handle
various vector data types and optimize their performance and
availability.

C. Distributed Parallel Processing Support

VDBs need to be scalable to handle large-scale vector data
and queries that may exceed the capacity of a single machine.
Therefore, VDBs need to support distributed parallel process-
ing of vector data and queries across multiple computers or
clusters. This involves challenges such as data partitioning,
load balancing, fault tolerance, and consistency.

D. Integration with Mainstream Machine Learning Frame-

works
VDBs need to be integrated with popular machine learn-
Fig. 7. Performance Test Results for Vector Databases
ing frameworks such as TensorFlow, PyTorch, Scikit-learn,
etc., which are used to generate and use vector embeddings.
overall ranking, Milvus ranks first with its comprehensive As a result, VDBs need to provide easy-to-use application
performance, achieving a QPS of 380, latency of 12.4 mil- programming interfaces (API) and encapsulated connectors
liseconds, and outstanding performance in load capacity. In to seamlessly interact with these frameworks and support a
contrast, ElasticCloud ranks last, with a QPS of 11.29 and variety of data formats and models.
latency as high as 361 milliseconds. In terms of recall rate,
E. Integration with Emerging Application Scenarios
all databases perform close to 1.0, indicating little difference
in query accuracy. ZillizCloud demonstrates the best latency Currently, many emerging application scenarios remain un-
performance, at only 6 milliseconds, but its load capacity is derexplored. For instance, the incremental k-NN search [102]
relatively low. It is worth noting that ZillizCloud, ElasticCloud, adopted by recommendation and e-commerce platforms faces
and PgVector were assigned penalty values (P) due to timeouts significant challenges due to the vast imbalance between the
in the load capacity tests, which may have been caused by volume of vector data processed and the data displayed to
network issues and should not be taken as a definitive measure users. This method cannot be effectively supported by most
of their actual performance. Overall, no single database ranked VDBs [20]. Furthermore, with the latest advancements in
in the top three across all tests, indicating that different sparse vector technology, integrating these technologies into
databases may have their own strengths. Additionally, the VDBs to enable hybrid retrieval (combining keyword and
overall rank is simply a straightforward average of the rankings vector retrieval methods) is increasingly regarded as a best
in each test item, without applying weighted averages based practice. Such hybrid systems must manage large datasets
on specific tasks, so it should be regarded as a preliminary while enhancing computational efficiency and maintaining
reference. retrieval quality.

F. Data Security and Privacy Protection

V. C HALLENGES
As cyber threats intensify and regulatory requirements be-
A. Index Construction and Searching of High-Dimensional come more stringent, data security and privacy protection for
Vectors databases have become top priorities [103]. Compared to the
VDBs require efficient indexing and searching of billions comprehensive data security and privacy protection features
of vectors in hundred or thousand dimensions, which poses a of traditional relational databases, VDBs are still in the early
huge computational and storage challenge. Traditional index- stages. Unlike traditional relational databases, VDBs typically
ing methods, such as B-trees or hash tables, are not suitable handle large amounts of high-dimensional embedding vectors,
for high-dimensional vectors because they suffer from dimen- which pose higher risks of privacy breaches during storage,
sionality catastrophe. Therefore, VDBs need to use specialized querying, and transmission. This is especially true in cloud
techniques such as ANN search, hashing, quantization, or platforms, where data is often stored in an unencrypted form
graph-based search to reduce complexity and improve the or transmitted between different nodes, increasing the potential
accuracy of vector similarity search. attack surface [104], [105]. In the future, VDBs will need
to not only leverage traditional data security and privacy
protection methods to build a robust security framework, but
B. Support for Heterogeneous Vector Data Types also integrate emerging technologies, such as blockchain tables
VDBs need to support different types of vector data, such [106] (to ensure data immutability) and AI-based anomaly de-
as dense vectors, sparse vectors, binary vectors, and so on. tection (for proactive threat management), to adapt to specific
Each type of vector data may have different characteristics application scenarios.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 19

VI. S YNERGY OF LLM S AND VDB S direction for enhancing the performance and adaptability of
By virtue of its excellent capability for rapid processing of LLMs in a variety of tasks by integrating retrieval with
unstructured data, a VDB can naturally meet the requirements generation.
of vector-intensive applications, especially for LLMs, where its The RAG framework has become a paradigm and has
role is becoming increasingly crucial. When processing natural brought a huge shift to NLP [110]. RAG models consist of
language, LLMs need to convert text into high-dimensional several major processes in the era of LLMs, including retrieval,
vectors for computation and analysis, which demands robust generation, and augmentation. A common workflow of RAG
storage and retrieval capabilities for high-dimensional vectors. when meeting LLMs is illustrated in figure8. The complete
Meanwhile, alleviating issues such as hallucinations and for- operational workflow of the system essentially consists of
getfulness in LLMs also requires supporting facilities like vast three core components: data storage, information retrieval, and
external knowledge bases, all of which necessitate the support content generation.
of VDBs. Therefore, the integration of LLMs and VDBs is The RAG workflow begins with the data storage phase.
set to be an inevitable trend in the future. Consequently, this During this phase, externally collected unstructured data (text,
section will delve into the integration and mutual influence images, audio, video) undergoes preprocessing. The processed
between VDBs and LLMs, and provide an outlook on rele- data is then divided into smaller chunks, converted into vectors
vant potential applications, with the aim of offering valuable via an embedding model to capture semantic representations,
references and insights for subsequent scientific research and and stored in a VDB for subsequent vector retrieval.
industrial applications. In the following sections, We will delve Next is the information retrieval phase. This stage starts
into the synergistic interaction between VDBs and LLMs, when a user poses a question to the model in the form of
exploring their concrete application prospects in depth. a prompt. The embedding model (used earlier for processing
Given these challenges, researchers and developers have external unstructured data) generates an embedding vector for
been exploring innovative solutions to enhance the perfor- the query, which is then used to retrieve the most semantically
mance and reliability of LLMs. One promising approach is similar data chunks from the VDB. These retrieved results are
the integration of VDBs into LLM systems. converted back from vector format to their original format and
returned to the user.
Finally, in the content generation phase, the large language
A. VDBs for LLMs model (LLM) generates the final answer. The user’s original
LLMs are characterized by large model capacity and vast question and the retrieved information are integrated into a
data corpus [107]. With hundreds of billions (or more) of task-specific prompt template (the selection of the prompt
parameters and extensive textual training, they are highly adept template depends on the task type). The LLM then processes
at comprehending human knowledge and instructions [108]. this prompt and produces the answer.
However, LLMs do have certain shortcomings, though [3]. VDBs as a Cost-effective Semantic Cache. The running of
One major shortcoming is hallucinations where the model LLMs consume huge resources. Its training requires massive
generates a response that is factually inaccurate. This short- computing power,and frequent API calls to third-party models
coming is mainly caused by the following issues, including racks up significant costs. With the help of VDBs, the inter-
knowledge limitations confined by the training corpa, the action cost and computing workload of LLMs can be reduced
internal knowledge in LLMs cannot be updated resulting in significantly, thereby promoting cost-effective and end-to-end
outdated knowledge, LLMs may also introduce systematic applications of LLMs.
errors due to the large dataset used for training. Another By integrating VDBs with LLMs, VDBs serve as GPT
shortcoming is oblivion problem. LLMs have been found semantic cache, which leverages semantic caching of query
having the inclination to forget the previous input information, embeddings in in-memory storage. This method can efficiently
and also exhibit catastrophic forgetting behavior. In response identify semantically similar questions by storing embeddings
to these issues, VDBs can offer robust support for LLMs in of user queries, allowing for the retrieval of pre-generated
the following aspects: responses without redundant API calls to the LLMs. This
1) VDBs as an External Knowledge Base: Retrieval- technique is an efficient way to reduce operational costs
Augmented Generation (RAG). The Retrieval-Augmented ,improve response times and address inefficiency [111]. This
Generation (RAG) technique is an artificial intelligence tech- architecture mainly consists of three components, including an
nology that combines information retrieval technology with embedding generation that converts user queries into semantic
language generation models [109]. This technique enhances embeddings, an in-memory caching that manages storage and
the capability of LLMs in handling knowledge-intensive tasks, retrieval of embeddings and responses and a similarity search
such as question answering, text summarization, and content that identifies semantically similar queries. The combination
generation, by retrieving relevant information from an external of VDBs with LLMs offers several advantages. This technique
knowledge base and inputting it as a prompt to the LLMs. reduces API dependency while maintaining high response
To address the above limitations, recent research introduced accuracy. In addition, it demonstrates substantial scalability
the RAG technique. Retrieval models play an important role and adaptability. By using vector searching algorithms and in-
in various knowledge-intensive tasks by providing timely and memory caching, it allows for the handling of large volumes
accurate external knowledge through effective data mainte- of queries without a proportional increase in computational de-
nance in external databases. RAG models provide a promising mands, supporting stable performance even under fluctuating
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 20

Information Retrieval
User Question
Vector Search

2025 China EV sales leaders?

Vectorized
Relevant Docs Prompt
Retrieve Please answer the question
Embedding Model Vector Database • 2025 China Current
using the given documents
market leaders

• 2025 Report of the Documents: “[Relevant Docs]”

China Association of
Chunking
Automobile Question: ”[User Question]”
Manufacturers
Unstructured Data

Result
Based on RAG data,
the top EV brands in
China by 2025 are
likely to be:

Rank Brand Share

1 BYD 35%
Image & Text Audio & Video
Large Language Model 2 Tesla 15%

Ddata Storage Content Generation

Fig. 8. A common workflow of RAG

workloads. It also supports for multiple embedding models which facilitates the subsequent retrieval and updating of
and configurations, making the system adaptable to various relevant memory information. Another shortcoming of LLMs
deployment needs [112]. Using VDBs as GPT semantic cache is that they cannot update knowledge dynamically, lacking of
will be a viable solution to facilitate the large-scale application the few-shot learning ability. VDBs provide a robust memory
of LLMs. layer for LLMs to update new information continuously in the
VDBs as A Reliable Memory of LLMs. Memory systems way of storage, thus ensuring that LLMs can make response
can power the intelligence LLMs, enabling them to demon- according to the most current and relevant data.
strate the capability of autonomous and thus show impressive
performance in a wide range of tasks. The integration of mem- B. LLMs for VDBs
ory systems and LLMs is conductive to the coherence, con- In addition, LLMs in turn can empower [Link]
textual, and efficiency of interactions and that the system can technology has been proved to perform well in many data
learn and adapt over time. Currently, a significant drawback of management tasks, such as data processing, database opti-
LLMs is lacking strong long-term memory capabilities [113]. mization, and data analysis. However, traditional machine
This limitation will hinder LLMs’ ability to maintain context learning algorithms are unable to solve generalization and
over long periods of time and retrieve relevant information inference problems. For example, traditional machine learning
from past interactions. Therefore, in order to improve the algorithms have difficulty in adapting to different databases,
decision quality and reasoning efficiency of LLMs in complex different query workloads, and different hardware environ-
tasks, it is necessary to research and develop effective long- ments, making them unable to solve the generalizability and
term memory mechanisms. Through the external knowledge inference problems in data management tasks. In addition,
storage and historical interactions, long-term memory is avail- traditional machine learning algorithms cannot satisfy the
able for LLMs to store and retrieve and use in subsequent need for contextual understanding and multi-step reasoning in
interactions, which enhances LLMs’ intelligence ability in optimization scenarios such as database diagnosis, root cause
maintaining contextual coherence, improving decision-making analysis, etc. However, LLMs bring promising solutions to the
quality, reducing cost of reasoning and demonstrating higher above problems [114].
intelligence in long-term interactions. LLMs assist database management tasks. LLMs revo-
The VDBs can be used as the underlying basic tool of lutionize data management. LLMs show great potential in
LLMs to support the storage of historical information, so that optimizing data management problems due to its excellent
LLMs can effectively store different types of historical inter- language comprehension and generalization capabilities in
action information, such as knowledge information, dialogue tasks such as data processing, database optimization, and data
information, and related task information. Then different types analysis. For example, LLMs can analyze anomalous database
of information during intelligent interaction are stored in the metrics and report root causes and potential solutions to data
VDBs as long term memory after slicing and vectorizing, base administrators. LLMs can also be used as a natural
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 21

User Intent
language (NL) interface for data analysis tasks, converting Applications of quantum
computing in drug discovery
NL requests into executable queries against their databases.
LLMs bring several advantages to database management tasks.
Prompt:
Analysis of Quantum Computing
The first point is higher transfer capability. Existing instance- [You are an expert in quantum computing and
Algorithms in Molecular
biomedicine. Please accomplish the following
Dynamics Simulations:
optimal works can optimize an instance but cannot be extended User Level
objectives:.]
[Objective 1: Analyze the efficiency improvements [Objective 1:Variational
Quantum Eigensolver (VQE)]
to other instances, whereas, the combination of LLMs with of quantum computing algorithms (e.g., VQE,
QAOA) in molecular dynamics simulations. [Objective 2: Comparison with
Objective 2: Compare with classical methods] Classical Methods:]
databases demonstrates exceptional transfer capability. With
a few fine-tuned examples, comparable performance can be
achieved on novel database tasks, making them more adaptable Key Term Model-extracted Keywords:
Extraction [VQE, QAOA, Molecular Dynamics
to database schema, workload, or even data and hardware Model Level Simulation, Comparison]

changes. The second point is the ability to provide a user- Vector Domain-specific model
0.4 0.5 0.7 0.9 0.1
0.4 0.5 0.7 0.9 0.1
friendly interface. LLMs allow users to provide some prompts Embedding 0.2 0.7 0.7 0.8 0.3

as hints to guide the model’s inference, thus offering an

intuitive interface. The second is the ability to provide a Embeddings
AI Database Level and
user-friendly interface. LLMs allow users to provide some Unstructured
data
prompts as hints to guide the model’s inference, thus offering Vector Database Similarity Search

an intuitive user experience without the need for large amounts

of training data (supervised modelling) or multiple iterations Multi-type
Unstructured
(reinforcement learning) to capture and merge user feedback. Data Level Data

The third point is to learn from prior knowledge. LLMs can Multidisciplinary
Journal Article Patent Databases Code Repository Online Course Fields
extract insights from existing database components, including
documents and even code. By integrating the strengths of these
Fig. 9. A common workflow of Retrieval-Augmented Generation (RAG).
components, databases’ performance can be enhanced while
mitigating the individual weaknesses of the components [115].
LLMs smarten vector data handling. The deep integration open source LLMs, the corre- sponding vector embeddings
of LLMs with VDBs has pioneered innovative application can be obtained directly. The VDB stores unstructured data
scenarios for data-driven workflows, encompassing content and their joint embeddings. The next step is to go to the
generation, knowledge enhancement, and system optimiza- VDB to find similar nearest neighbors. The ones obtained from
tion. By combining semantic understanding with vectorized the sequences in the big language model are compared with
retrieval, LLMs can generate customized texts (e.g., thematic the vector encodings in the VDB, by means of the NNS or
articles, stylized summaries) based on vector inputs, enrich ANNS algorithms. And different results are derived through a
ambiguous texts with additional details (e.g., supplementing predefined serialization chain, which plays the role of a search
statistical data or case studies), and facilitate cross-language, engine. If it is not a generalized question, the results derived
cross-domain text transformations (e.g., multilingual simplifi- need to be further put into the domain model, for example,
cation of legal documents). Furthermore, LLMs significantly imagine we are seeking an intelligent scientific assistant, which
optimize the management tasks of VDBs: they recommend can be put into the model of AI4S to get professional results.
configuration parameters by analyzing historical performance Eventually it can be placed again into the LLM to get coherent
data to improve system stability, automatically diagnose per- generated results. For the data layer located at the bottom, one
formance bottlenecks while generating interpretable reports, can choose from a variety of file formats such as PDF, CSV,
and efficiently process heterogeneous data through semantic MD, DOC, PNG, SQL, etc., and its sources can be journals,
analysis (e.g., schema matching and error correction). These conferences, textbooks, and so on. Corresponding disciplines
applications not only reduce the cost of manual intervention can be art, science, engineering, business, medicine, law, and
but also extend the generalization capabilities of traditional etc.
methods through adaptive solutions, highlighting the core
value of LLMs in enhancing the intelligence and scalability
of VDBs [116]–[122].
VII. C ONCLUSION
In this paper, we provide a comprehensive and up-to-date
C. A General LLMs and VDBs Synergized Framework literature review on VDBs, including the key algorithms,
For a framework that incorporates a large language model storage, and retrieval methods. We also compare representative
and a VDB, as shown in figure8 it can be understood by VDB systems, analyze their design trade-offs, and discuss
splitting it into four levels: the user level, the model level, the their strengths, limitations, and typical use cases. Furthermore,
AI database level, and the data level, respectively. For a user we identify key challenges and outline potential research
who has never been exposed to large language modeling, it is directions, including improved indexing and closer integration
possible to enter natural language to describe their problem. with LLMs. We believe this survey offers a solid reference
For a user who is proficient in large language modeling, a for researchers and practitioners, and contributes to a clearer
well-designed prompt can be entered. The LLM next processes understanding of the current state and future direction of vector
the problem to extract the key- words in it, or in the case of databases.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 22

R EFERENCES [23] Y. Su, Y. Sun, M. Zhang, and J. Wang, “Vexless: A serverless vector
data management system using cloud functions,” Proceedings of the
[1] J. Cao, J. Fang, Z. Meng, and S. Liang, “Knowledge graph embed- ACM on Management of Data, vol. 2, no. 3, pp. 1–26, 2024.
ding: A survey from the perspective of representation spaces,” ACM [24] T. Taipalus, “Vector database management systems: Fundamental con-
Computing Surveys, vol. 56, no. 6, pp. 1–42, 2024. cepts, use-cases, and current challenges,” Cognitive Systems Research,
[2] S. Pouyanfar, Y. Yang, S.-C. Chen, M.-L. Shyu, and S. S. Iyengar, vol. 85, p. 101216, 2024.
“Multimedia big data analytics: A survey,” ACM Comput. Surv., vol. 51, [25] S. Joshi, “Introduction to vector databases for generative ai: Ap-
no. 1, Jan. 2018. [Online]. Available: [Link] plications, performance, future projections, and cost considerations,”
[3] W. X. Zhao, K. Zhou, J. Li, T. Tang, X. Wang, Y. Hou, Y. Min, International Advanced Research Journal in Science, Engineering and
B. Zhang, J. Zhang, Z. Dong et al., “A survey of large language Technology ISSN (O), pp. 2393–8021.
models,” arXiv preprint arXiv:2303.18223, 2023.
[26] V. Beecher. (2021) Oracle database using oracle sharding. [Online].
[4] A. M. N. Allam and M. H. Haggag, “The question answering systems:
Available: [Link]
A survey,” International Journal of Research and Reviews in Informa-
18/shard/[Link]
tion Sciences (IJRRIS), vol. 2, no. 3, 2012.
[27] C. H. Costa, P. Maia, F. Carlos et al., “Sharding by hash partitioning,”
[5] G. M. Biancofiore, Y. Deldjoo, T. D. Noia, E. Di Sciascio, and F. Nar-
in Proceedings of the 17th International Conference on Enterprise
ducci, “Interactive question answering systems: Literature review,”
Information Systems, vol. 1, 2015, pp. 313–320.
ACM Computing Surveys, vol. 56, no. 9, pp. 1–38, 2024.
[6] Y. Zhang, J. Wu, and J. Cai, “Compact representation of high- [28] P. Done, Practical MongoDB Aggregations. GitHub,
dimensional feature vectors for large-scale image recognition and 2023, accessed: 2024-12-01. [Online]. Available: www.
retrieval,” IEEE Transactions on Image Processing, vol. 25, no. 5, pp. [Link]
2407–2419, 2016. [29] V. Mirrokni, M. Thorup, and M. Zadimoghaddam, “Consistent hashing
[7] Z. Zhao, W. Fan, J. Li, Y. Liu, X. Mei, Y. Wang, Z. Wen, F. Wang, with bounded loads,” in Proceedings of the Twenty-Ninth Annual ACM-
X. Zhao, J. Tang et al., “Recommender systems in the era of large SIAM Symposium on Discrete Algorithms. SIAM, 2018, pp. 587–604.
language models (llms),” IEEE Transactions on Knowledge and Data [30] D. Karger, A. Sherman, A. Berkheimer, B. Bogstad, R. Dhanidina,
Engineering, 2024. K. Iwamoto, B. Kim, L. Matkins, and Y. Yerushalmi, “Web caching
[8] Q. Liu, J. Hu, Y. Xiao, X. Zhao, J. Gao, W. Wang, Q. Li, and J. Tang, with consistent hashing,” Computer Networks, vol. 31, no. 11-16, pp.
“Multimodal recommender systems: A survey,” ACM Computing Sur- 1203–1213, 1999.
veys, vol. 57, no. 2, pp. 1–17, 2024. [31] D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and
[9] G. Touya and I. Lokhat, “Deep learning for enrichment of vector D. Lewin, “Consistent hashing and random trees: Distributed caching
spatial databases: Application to highway interchange,” ACM Trans. protocols for relieving hot spots on the world wide web,” in Pro-
Spatial Algorithms Syst., vol. 6, no. 3, Apr. 2020. [Online]. Available: ceedings of the twenty-ninth annual ACM symposium on Theory of
[Link] computing, 1997, pp. 654–663.
[10] M. Wang, L. Lv, X. Xu, Y. Wang, Q. Yue, and J. Ni, “An efficient [32] R. Taft, I. Sharif, A. Matei, N. VanBenschoten, J. Lewis, T. Grieger,
and robust framework for approximate nearest neighbor search with K. Niemi, A. Woods, A. Birzin, R. Poss et al., “Cockroachdb: The
attribute constraint,” Advances in Neural Information Processing Sys- resilient geo-distributed sql database,” in Proceedings of the 2020 ACM
tems, vol. 36, 2024. SIGMOD international conference on management of data, 2020, pp.
[11] T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis, “The case 1493–1509.
for learned index structures,” in Proceedings of the 2018 international [33] Y. Zhang, R. Power, S. Zhou, Y. Sovran, M. K. Aguilera, and J. Li,
conference on management of data, 2018, pp. 489–504. “Transaction chains: achieving serializability with low latency in geo-
[12] X. Xie, H. Liu, W. Hou, and H. Huang, “A brief survey of vector distributed storage systems,” in Proceedings of the Twenty-Fourth ACM
databases,” in 2023 9th International Conference on Big Data and Symposium on Operating Systems Principles, 2013, pp. 276–291.
Information Analytics (BigDIA). IEEE, 2023, pp. 364–371. [34] D. DeWitt and J. Gray, “Parallel database systems: The future of high
[13] X. Zhao, Y. Tian, K. Huang, B. Zheng, and X. Zhou, “Towards efficient performance database systems,” Communications of the ACM, vol. 35,
index construction and approximate nearest neighbor search in high- no. 6, pp. 85–98, 1992.
dimensional spaces,” Proceedings of the VLDB Endowment, vol. 16, [35] D. J. DeWitt and S. Ghandeharizadeh, “Hybrid-range partitioning strat-
no. 8, pp. 1979–1991, 2023. egy: A new declustering strategy for multiprocessor database machine,”
[14] Z. Wang, P. Wang, T. Palpanas, and W. Wang, “Graph-and tree- in Proc. 16th international Conference on VLDB, 1990, pp. 481–492.
based indexes for high-dimensional vector similarity search: Analyses, [36] L. Hobbs, S. Hillson, S. Lawande, and P. Smith, Oracle 10g data
comparisons, and future directions.” IEEE Data Eng. Bull., vol. 46, warehousing. Elsevier, 2011.
no. 3, pp. 3–21, 2023. [37] D. Hotka, Oracle9i Development by Example. Que Publishing, 2002.
[15] W. Li, Y. Zhang, Y. Sun, W. Wang, M. Li, W. Zhang, and [38] [Link]
X. Lin, “Approximate nearest neighbor search on high dimensional
[39] [Link]
data—experiments, analyses, and improvement,” IEEE Transactions on
[40] R. Guo, X. Luan, L. Xiang, X. Yan, X. Yi, J. Luo, Q. Cheng, W. Xu,
Knowledge and Data Engineering, vol. 32, no. 8, pp. 1475–1488, 2019.
J. Luo, F. Liu et al., “Manu: a cloud native vector database management
[16] V. Karthik, S. Khan, S. Singh, H. V. Simhadri, and J. Vedurada, “Bang:
system,” arXiv preprint arXiv:2206.13843, 2022.
Billion-scale approximate nearest neighbor search using a single gpu,”
arXiv preprint arxiv:2401.11324, 2024. [41] D. Grund and J. Reineke, “Abstract interpretation of fifo replacement,”
[17] H. Jégou, M. Douze, J. Johnson, L. Hosseini, and C. Deng, “Faiss: in International Static Analysis Symposium. Springer, 2009, pp. 120–
Similarity search and clustering of dense vectors library,” Astrophysics 136.
Source Code Library, pp. ascl–2210, 2022. [42] ——, “Precise and efficient fifo-replacement analysis based on static
[18] J. Mohoney, A. Pacaci, S. R. Chowdhury, A. Mousavi, I. F. Ilyas, phase detection,” in 2010 22nd Euromicro Conference on Real-Time
U. F. Minhas, J. Pound, and T. Rekatsinas, “High-throughput vector Systems. IEEE, 2010, pp. 155–164.
similarity search in knowledge graphs,” Proceedings of the ACM on [43] R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger, “Evaluation
Management of Data, vol. 1, no. 2, pp. 1–25, 2023. techniques for storage hierarchies,” IBM Systems journal, vol. 9, no. 2,
[19] J. J. Pan, J. Wang, and G. Li, “Vector database management techniques pp. 78–117, 1970.
and systems,” in Companion of the 2024 International Conference on [44] X. Gu and C. Ding, “On the theory and potential of lru-mru collab-
Management of Data, 2024, pp. 597–604. orative cache management,” ACM SIGPLAN Notices, vol. 46, no. 11,
[20] ——, “Survey of vector database management systems,” The VLDB pp. 43–54, 2011.
Journal, vol. 33, no. 5, pp. 1591–1615, 2024. [45] D. Lee, J. Choi, J.-H. Kim, S. H. Noh, S. L. Min, Y. Cho, and C. S.
[21] T. R. Rao, P. Mitra, R. Bhatt, and A. Goswami, “The big data Kim, “On the existence of a spectrum of policies that subsumes the
system, components, tools, and technologies: a survey,” Knowledge least recently used (lru) and least frequently used (lfu) policies,” in
and Information Systems, vol. 60, pp. 1165–1245, 2019. Proceedings of the 1999 ACM SIGMETRICS international conference
[22] M. Wang, W. Xu, X. Yi, S. Wu, Z. Peng, X. Ke, Y. Gao, X. Xu, on Measurement and modeling of computer systems, 1999, pp. 134–
R. Guo, and C. Xie, “Starling: An i/o-efficient disk-resident graph 143.
index framework for high-dimensional vector similarity search on data [46] S. Podlipnig and L. Böszörmenyi, “A survey of web cache replacement
segment,” Proceedings of the ACM on Management of Data, vol. 2, strategies,” ACM Computing Surveys (CSUR), vol. 35, no. 4, pp. 374–
no. 1, pp. 1–27, 2024. 398, 2003.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 23

[47] S. Mittal, “A survey of techniques for cache partitioning in multicore [71] A. Andoni, P. Indyk, H. L. Nguyen, and I. Razenshteyn,
processors,” ACM Computing Surveys (CSUR), vol. 50, no. 2, pp. 1–39, “Beyond Locality-Sensitive Hashing,” Oct. 2013, arXiv:1306.1547
2017. [cs]. [Online]. Available: [Link]
[48] D. Ongaro and J. Ousterhout, “In search of an understandable consen- [72] A. Andoni and I. Razenshteyn, “Optimal Data-Dependent Hashing
sus algorithm,” in 2014 USENIX annual technical conference (USENIX for Approximate Near Neighbors,” Jul. 2015, arXiv:1501.01062 [cs].
ATC 14), 2014, pp. 305–319. [Online]. Available: [Link]
[49] H. Garcia-Molina and D. Barbara, “How to assign votes in a distributed [73] Y. Weiss, A. Torralba, and R. Fergus, “Spectral hashing,” Advances in
system,” Journal of the ACM (JACM), vol. 32, no. 4, pp. 841–860, neural information processing systems, vol. 21, 2008.
1985. [74] J.-P. Heo, Y. Lee, J. He, S.-F. Chang, and S.-E. Yoon, “Spherical
[50] J. Garmany and R. G. Freeman, Oracle Replication: Snapshot, Multi- hashing,” in 2012 IEEE conference on computer vision and pattern
master and Materialized Views Scripts. Rampant TechPress, 2003. recognition. IEEE, 2012, pp. 2957–2964.
[51] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, [75] H. Liu, R. Wang, S. Shan, and X. Chen, “Deep supervised hashing
A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, “Dynamo: for fast image retrieval,” in Proceedings of the IEEE conference on
Amazon’s highly available key-value store,” ACM SIGOPS operating computer vision and pattern recognition, 2016, p. 2064–2072.
systems review, vol. 41, no. 6, pp. 205–220, 2007. [76] X. Luo, H. Wang, D. Wu, C. Chen, M. Deng, J. Huang, and X.-S. Hua,
[52] P. Bailis, S. Venkataraman, M. J. Franklin, J. M. Hellerstein, and I. Sto- “A survey on deep hashing methods,” 2022.
ica, “Quantifying eventual consistency with pbs,” Communications of
[77] ——, “A survey on deep hashing methods,” ACM Transactions on
the ACM, vol. 57, no. 8, pp. 93–102, 2014.
Knowledge Discovery from Data, vol. 17, no. 1, pp. 1–50, 2023.
[53] J. Gao and C. Long, “High-dimensional approximate nearest neighbor
search: with reliable and efficient distance comparison operations,” [78] “Remote Sensing | Free Full-Text | Deep Hashing Using Proxy
Proceedings of the ACM on Management of Data, vol. 1, no. 2, pp. Loss on Remote Sensing Image Retrieval.” [Online]. Available:
1–27, 2023. [Link]
[54] M. D. Manohar, Z. Shen, G. Blelloch, L. Dhulipala, Y. Gu, H. V. [79] B. E and S. AB., “Annoy (approximate nearest neighbors oh yeah),”
Simhadri, and Y. Sun, “Parlayann: Scalable and deterministic parallel [DB/OL]. (2015) [2023-07-28]. 3, 2015.
graph-based approximate nearest neighbor search algorithms,” in Pro- [80] B. J. S and L. D. G., “Shape indexing using approximate nearest-
ceedings of the 29th ACM SIGPLAN Annual Symposium on Principles neighbour search in high-dimensional spaces,” in Proceedings of IEEE
and Practice of Parallel Programming, 2024, pp. 270–285. computer society conference on computer vision and pattern recogni-
[55] C. Fu, C. Wang, and D. Cai, “High dimensional similarity search tion, 1997, pp. 1000–1006.
with satellite system graph: Efficiency, scalability, and unindexed query [81] H. Liu, M. Deng, and C. Xiao, “An improved best bin first algorithm
compatibility,” IEEE Transactions on Pattern Analysis and Machine for fast image registration,” in Proceedings of 2011 International
Intelligence, vol. 44, no. 8, pp. 4139–4150, 2021. Conference on Electronic & Mechanical Engineering and Information
[56] Z. Wang, Q. Wang, P. Wang, T. Palpanas, and W. Wang, “Dumpy: Technology, vol. 1. IEEE, 2011, pp. 355–358.
A compact and adaptive index for large data series collections,” [82] T. P, T. P, and S. M., “K-means tree: an optimal clustering tree for
Proceedings of the ACM on Management of Data, vol. 1, no. 1, pp. unsupervised learning,” The Journal of Supercomputing, vol. 77, pp.
1–27, 2023. 5239–5266, 2021.
[57] J. L. Bentley, “Multidimensional binary search trees used for asso- [83] J. Guare, “Six degrees of separation,” in The Contemporary Mono-
ciative searching,” Communications of the ACM, vol. 18, no. 9, p. logue: Men. Routledge, 2016, pp. 89–93.
509–517, 1975. [84] A. Ponomarenko, Y. Malkov, A. Logvinov, and V. Krylov, “Approxi-
[58] B. Ghojogh, S. Sharifian, and H. Mohammadzade, “Tree-based opti- mate nearest neighbor search small world approach,” in International
mization: A meta-algorithm for metaheuristic optimization,” 2018. Conference on Information and Communication Technologies & Ap-
[59] S. M. Omohundro, Five balltree construction algorithms. Berkeley: plications, vol. 17, 2011.
International Computer Science Institute, 1989. [85] M. Y, P. A, L. A, and K. A., “Approximate nearest neighbor algorithm
[60] T. Liu, A. W. Moore, A. Gray, and K. Yang, “New algorithms for based on navigable small world graphs,” Information Systems, vol. 45,
efficient high-dimensional nonparametric classification,” Journal of pp. 61–68, 2014.
machine learning research, vol. 7, no. 6, 2006. [86] ——, “Scalable distributed algorithm for approximate nearest neighbor
[61] M. Dolatshah, A. Hadian, and B. Minaei-Bidgoli, “Ball*-tree: Efficient search problem in high dimensional general metric spaces,” in Simi-
spatial indexing for constrained nearest-neighbor search in metric larity Search and Applications: 5th International Conference, SISAP
spaces,” Nov. 2015, arXiv:1511.00628 [cs]. [Online]. Available: 2012, Toronto, ON, Canada, August 9-10, 2012. Proceedings 5, 2012,
[Link] pp. 132–147.
[62] A. Guttman, “R-trees: a dynamic index structure for spatial searching,” [87] Y. A. Malkov and D. A. Yashunin, “Efficient and robust approxi-
in Proceedings of the 1984 ACM SIGMOD international conference on mate nearest neighbor search using hierarchical navigable small world
Management of data, 1984, p. 47–57. graphs,” IEEE transactions on pattern analysis and machine intelli-
[63] P. Ciaccia, M. Patella, and P. Zezula, “M-tree: An efficient access gence, vol. 42, no. 4, p. 824–836, 2018.
method for similarity search in metric spaces,” in Vldb, vol. 97, 1997,
[88] M. van Baalen, A. Kuzmin, M. Nagel, P. Couperus, C. Bas-
p. 426–435.
toul, E. Mahurin, T. Blankevoort, and P. Whatmough, “Gptvq: The
[64] D. Cai, “A revisit of hashing algorithms for approximate nearest neigh-
blessing of dimensionality for llm quantization,” arXiv preprint
bor search,” IEEE Transactions on Knowledge and Data Engineering,
arXiv:2402.15319, 2024.
vol. 33, no. 6, pp. 2337–2348, 2019.
[65] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni, “Locality- [89] Y. Liu, J. Wen, Y. Wang, S. Ye, L. L. Zhang, T. Cao, C. Li, and
sensitive hashing scheme based on p-stable distributions,” in Proceed- M. Yang, “Vptq: Extreme low-bit vector post-training quantization for
ings of the twentieth annual symposium on Computational geometry, large language models,” arXiv preprint arXiv:2409.17066, 2024.
2004, p. 253–262. [90] D.-K. Le Tan, H. Le, T. Hoang, T.-T. Do, and N.-M. Cheung, “Deepvq:
[66] O. Jafari, P. Maurya, P. Nagarkar, K. M. Islam, and C. Crushev, “A A deep network architecture for vector quantization,” in Proceedings
survey on locality sensitive hashing algorithms and their applications,” of the IEEE Conference on Computer Vision and Pattern Recognition
2021. Workshops, 2018, pp. 2579–2582.
[67] A. Andoni, P. Indyk et al., “Locality sensitive hashing (lsh) home page,” [91] H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest
ˆ1ˆ, 2023, accessed: 2023-10-18. neighbor search,” IEEE transactions on pattern analysis and machine
[68] N. Dikkala, G. Kaplun, and R. Panigrahy, “For manifold learning, deep intelligence, vol. 33, no. 1, p. 117–128, 2010.
neural networks can be locality sensitive hash functions,” 2021. [92] Y. Matsui, Y. Uchida, H. Jégou, and S. Satoh, “A survey of product
[69] K. Bob, D. Teschner, T. Kemmer, D. Gomez-Zepeda, S. Tenzer, quantization,” ITE Transactions on Media Technology and Applica-
B. Schmidt, and A. Hildebrandt, “Locality-sensitive hashing enables tions, vol. 6, no. 1, pp. 2–10, 2018.
efficient and scalable signal classification in high-throughput mass [93] T. Ge, K. He, Q. Ke, and J. Sun, “Optimized product quantiza-
spectrometry raw data,” BMC Bioinformatics, vol. 23, no. 1, p. 287, tion,” IEEE transactions on pattern analysis and machine intelligence,
2022. [Online]. Available: ˆ1ˆ vol. 36, no. 4, pp. 744–755, 2013.
[70] A. Andoni and P. Indyk, “Near-optimal hashing algorithms for ap- [94] L. Li and Q. Hu, “Optimized high order product quantization for
proximate nearest neighbor in high dimensions,” Communications of approximate nearest neighbors search,” Frontiers of Computer Science,
the ACM, vol. 51, no. 1, pp. 117–122, 2008. vol. 14, no. 2, pp. 259–272, 2020. [Online]. Available: ˆ1ˆ
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 24

[95] “Online Product Quantization | IEEE Transactions on Knowledge [118] M. Fan, X. Han, J. Fan, C. Chai, N. Tang, G. Li, and X. Du, “Cost-
and Data Engineering.” [Online]. Available: [Link] effective in-context learning for entity resolution: A design space
1109/TKDE.2018.2817526 exploration,” in 2024 IEEE 40th International Conference on Data
[96] R. Guo, P. Sun, E. Lindgren, Q. Geng, D. Simcha, F. Chern, and Engineering (ICDE). IEEE, 2024, pp. 3696–3709.
S. Kumar, “Accelerating large-scale inference with anisotropic vec- [119] X. Zhou, G. Li, Z. Sun, Z. Liu, W. Chen, J. Wu, J. Liu, R. Feng,
tor quantization,” in International Conference on Machine Learning. and G. Zeng, “D-bot: Database diagnosis system using large language
PMLR, 2020, pp. 3887–3896. models,” arXiv preprint arXiv:2312.01454, 2023.
[97] J. Wang, X. Yi, R. Guo, H. Jin, P. Xu, S. Li, X. Wang, X. Guo, [120] X. Huang, H. Li, J. Zhang, X. Zhao, Z. Yao, Y. Li, Z. Yu, T. Zhang,
C. Li, X. Xu et al., “Milvus: A purpose-built vector data management H. Chen, and C. Li, “Llmtune: Accelerate database knob tuning with
system,” in Proceedings of the 2021 International Conference on large language models,” arXiv preprint arXiv:2404.11581, 2024.
Management of Data, 2021, pp. 2614–2627. [121] S. Chang and E. Fosler-Lussier, “How to prompt llms for text-to-sql:
[98] Y. Wang, Z. Pan, and R. Li, “A new cell-level search based non- A study in zero-shot, single-domain, and cross-domain settings,” 2023.
exhaustive approximate nearest neighbor (ann) search algorithm in the [122] C. Whitehouse, M. Choudhury, and A. F. Aji, “Llm-powered data
framework of product quantization,” IEEE Access, vol. 7, pp. 37 059– augmentation for enhanced crosslingual performance,” 2023.
37 070, 2019.
[99] Y. Liu, Z. Pan, L. Wang, and Y. Wang, “A new fast inverted file-based
algorithm for approximate nearest neighbor search without accuracy
reduction,” Information Sciences, vol. 608, pp. 613–629, 2022.
[100] D. Xu, I. W. Tsang, Y. Zhang, and J. Yang, “Online product quantiza-
tion,” IEEE Transactions on Knowledge and Data Engineering, vol. 30,
no. 11, p. 2185–2198, 2018.
[101] P. Sun, D. Simcha, D. Dopson, R. Guo, and S. Kumar, “Soar: improved
indexing for approximate nearest neighbor search,” Advances in Neural
Information Processing Systems, vol. 36, pp. 3189–3204, 2023.
[102] G. Zhao, K. Xuan, D. Taniar, and B. Srinivasan, “Incremental k-
nearest-neighbor search on road networks,” Journal of Interconnection
Networks, vol. 9, no. 04, pp. 455–470, 2008.
[103] O. A. Farayola, O. L. Olorunfemi, and P. O. Shoetan, “Data privacy
and security in it: a review of techniques and challenges,” Computer
Science & IT Research Journal, vol. 5, no. 3, pp. 606–615, 2024.
[104] R. R. Asaad and S. R. Zeebaree, “Enhancing security and privacy
in distributed cloud environments: A review of protocols and mech-
anisms,” Academic Journal of Nawroz University, vol. 13, no. 1, pp.
476–488, 2024.
[105] A. Amaithi Rajan and V. V, “Systematic survey: secure and privacy-
preserving big data analytics in cloud,” Journal of Computer Informa-
tion Systems, vol. 64, no. 1, pp. 136–156, 2024.
[106] D. C. G. Valadares, A. Perkusich, A. F. Martins, M. B. M. Kamel,
and C. Seline, “Privacy-preserving blockchain technologies,” Sensors,
vol. 23, no. 16, 2023. [Online]. Available: [Link]
1424-8220/23/16/7172
[107] J. A. OpenAI, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L.
Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat et al.,
“Gpt-4 technical report, 2024,” URL [Link] org/abs/2303.08774,
vol. 2, p. 6, 2024.
[108] M. Shanahan, “Talking about large language models,” 2023.
[109] P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal,
H. Küttler, M. Lewis, W.-t. Yih, T. Rocktäschel et al., “Retrieval-
augmented generation for knowledge-intensive nlp tasks,” Advances in
neural information processing systems, vol. 33, pp. 9459–9474, 2020.
[110] P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal,
H. Küttler, M. Lewis, W. tau Yih, T. Rocktäschel, S. Riedel, and
D. Kiela, “Retrieval-augmented generation for knowledge-intensive
nlp tasks,” 2021. [Online]. Available: [Link]
[111] S. Regmi and C. P. Pun, “Gpt semantic cache: Reducing llm
costs and latency via semantic embedding caching,” arXiv preprint
arXiv:2411.05276, 2024.
[112] F. Bang, “Gptcache: An open-source semantic cache for llm applica-
tions enabling faster answers and cost savings,” in Proceedings of the
3rd Workshop for Natural Language Processing Open Source Software
(NLP-OSS 2023), 2023, pp. 212–218.
[113] K. Hatalis, D. Christou, J. Myers, S. Jones, K. Lambert, A. Amos-
Binks, Z. Dannenhauer, and D. Dannenhauer, “Memory matters: The
need to improve long-term memory in llm-agents,” in Proceedings of
the AAAI Symposium Series, vol. 2, no. 1, 2023, pp. 277–280.
[114] X. Zhou, Z. Sun, and G. Li, “Db-gpt: Large language model meets
database,” Data Science and Engineering, vol. 9, no. 1, pp. 102–111,
2024.
[115] G. Li, X. Zhou, and X. Zhao, “Llm for data management,” Proceedings
of the VLDB Endowment, vol. 17, no. 12, pp. 4213–4216, 2024.
[116] R. Tang, X. Han, X. Jiang, and X. Hu, “Does synthetic data generation
of llms help clinical text mining?” 2023.
[117] A. Albalak, Y. Elazar, S. M. Xie, S. Longpre, N. Lambert, X. Wang,
N. Muennighoff, B. Hou, L. Pan, H. Jeong et al., “A survey on
data selection for language models,” arXiv preprint arXiv:2402.16827,
2024.