PaperlayerView exact revision on arXiv

Source-linked AI summary

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, Ziyue Qiao, Wei Ju, Chong Chen, Dongjie Wang, Kunpeng Liu, Pengyang Wang, Pengfei Wang, Yanjie Fu, Chunjiang Liu, Yuanchun Zhou, Chang-Tien Lu

arXiv:2310.11703v4cs.DBcs.AI

TL;DR

Traditional databases designed for structured data are often inadequate for managing and retrieving high-dimensional vector data, for which vector databases provide a specialized solution. The survey reviews VDB storage and retrieval technologies, compares representative systems, and discusses design trade-offs, challenges, research directions, and LLM integration. The survey synthesizes VDB algorithms, storage and retrieval methods, system trade-offs, challenges, and potential research directions, including improved indexing and closer LLM integration.

  • Problem

    Traditional databases designed for structured data are often inadequate for managing and retrieving high-dimensional vector data, for which vector databases provide a specialized solution.

    Source: §1 · p. 1

  • Method

    The survey reviews VDB storage and retrieval technologies, compares representative systems, and discusses design trade-offs, challenges, research directions, and LLM integration.

    Source: §1 · p. 3, §7 · p. 22

  • Results

    The survey synthesizes VDB algorithms, storage and retrieval methods, system trade-offs, challenges, and potential research directions, including improved indexing and closer LLM integration.

    Source: §1 · p. 3, §7 · p. 22

  • Takeaways & Limitations

    The survey is intended as a reference for researchers and practitioners seeking to understand the current state and future direction of VDBs.

    Source: §7 · p. 22

    Spectral hashing performs well when data lie on a low-dimensional manifold, while noise, outliers, graph-Laplacian choice, and recall can pose challenges.

    Source: §3.2.1 · p. 8

Abstract

from arXiv · show

As high-dimensional vector data increasingly surpasses the processing capabilities of traditional database management systems, Vector Databases (VDBs) have emerged and become tightly integrated with large language models, being widely applied in modern artificial intelligence systems. However, existing research has primarily focused on underlying technologies such as approximate nearest neighbor search, with relatively few studies providing a systematic architectural-level review of VDBs or analyzing how these core technologies collectively support the overall capacity of VDBs. This survey aims to offer a comprehensive overview of the core designs and algorithms of VDBs, establishing a holistic understanding of this rapidly evolving field. First, we systematically review the key technologies and design principles of VDBs from the two core dimensions of storage and retrieval, tracing their technological evolution. Next, we conduct an in-depth comparison of several mainstream VDB architectures, summarizing their strengths, limitations, and typical application scenarios. Finally, we explore emerging directions for integrating VDBs with large language models, including open research challenges and trends such as novel indexing strategies. This survey serves as a systematic reference guide for researchers and practitioners, helping readers quickly grasp the technological landscape and development trends in the field of vector databases, and promoting further innovation in both theoretical and applied aspects.

1. Introduction

Vector databases are designed to store and retrieve high-dimensional vector representations where traditional databases are often inadequate. This survey reviews their storage and retrieval technologies, compares systems, and discusses challenges and LLM integration.

1. Introduction

  • High-dimensional vectors represent data features and encode semantic and contextual information for entities such as text, images, audio, and video.The passage says vectors are generally generated using machine-learning models and used for similarity comparison.Source: §1 · p. 1
  • VDBs store and manage high-dimensional vectors and use specialized retrieval indexes, while storage mechanisms include quantization, compression, and distributed storage.The surveyed indexes include tree-, hashing-, graph-, and quantization-based methods.Source: §1 · pp. 1–2
  • VDBs support similarity-based retrieval and management of unstructured data, while traditional databases are often inadequate for high-dimensional vector data.The paper also describes scalability and real-time processing as VDB benefits.Source: §1 · pp. 1–2
  • The survey identifies limited architectural-level coverage of storage and search technologies, VDB capability comparisons, and integration with rapidly advancing AI technologies in prior work.It presents a comprehensive survey to integrate existing knowledge and identify research issues.Source: §1 · pp. 2–3
  • The survey systematically reviews VDB storage and retrieval technologies, tests open-source VDB performance, and examines challenges and LLM integration.It also presents a classification system for storage and search technologies.Source: §1 · p. 3

2. Storage

The storage section surveys ways to distribute, organize, cache, and replicate vector data. The techniques make different trade-offs in scalability, query efficiency, availability, and workload fit.

2. Storage

  • VDB storage covers sharding and partitioning for data distribution, caching to reduce query latency, and replication for availability and fault tolerance.Partitioning organizes data within one physical system, while sharding distributes it across machines; using both combines local organization with horizontal scaling.Source: §2 · p. 3, §2.2 · p. 4

2.1. Sharding

  • Sharding distributes records across machines using range, hash, or geographic rules, with each scheme suited to different workloads and design goals.Range sharding supports predictable range queries but can skew when keys are uneven; geographic sharding places data near users, while consistent hashing limits movement during cluster changes.Source: §2.1 · pp. 3–4

2.2. Partitioning

  • Partitioning groups data within a database by ranges, lists, clusters, or hashes so queries can target relevant subsets rather than scan unrelated data.K-means partitioning can be costly at large scale, particularly when frequent updates require reclustering; hash partitioning can overload partitions under uneven distributions.Source: §2.2 · p. 4

2.3. Caching

  • FIFO, LRU, and MRU evict vectors using age or recency, and their fit depends on whether workloads repeat recent items or quickly make older items irrelevant.FIFO can evict frequently used vectors; LRU may struggle with periodic or long-tailed access, while MRU may underperform when temporal locality is strong.Source: §2.3 · p. 5
  • LFU retains frequently accessed vectors, while partitioned caches assign separate sizes or eviction policies to groups such as geographic regions or access frequencies.LFU can retain stale popular items and is less effective as access distributions change; partitioned caches can improve hit rates when configured well.Source: §2.3 · p. 5

2.4. Replication

  • Replication strategies include leader-follower, multi-leader, and leaderless designs, trading write handling and consistency properties against availability and coordination needs.Leader-follower centralizes writes; leaderless replication avoids a single point of failure but may require conflict-resolution mechanisms.Source: §2.4 · p. 5

3. Search

Vector search finds similar items in high-dimensional data using exact or approximate nearest-neighbor methods. Approximate methods trade accuracy for speed and space, and newer algorithms may offer future opportunities for VDBs.

3. Search

  • Nearest-neighbor search finds the point closest to a query, while approximate nearest-neighbor search permits error in exchange for speed and space efficiency.The passages give image, document, product, and user similarity as example uses.Source: §3 · p. 5
  • Exact search methods use deterministic space partitioning and distance bounds, whereas approximate methods use probabilistic or heuristic hashing, region ordering, or graph traversal.The examples include k-d trees and ball trees for exact search, and locality-sensitive hashing and hierarchical navigable small world graphs for approximate search.Source: §3 · p. 6
  • Recent high-dimensional nearest-neighbor algorithms have not yet been widely adopted by VDBs, but the survey describes them as having significant potential for future applications.The passage notes that data structures or algorithms for exact search can also be applied to approximate search.Source: §3 · p. 6

3.1. Nearest Neighbor Search

Nearest-neighbor search ranges from exact scans and spatial tree partitions to approximate methods; the best choice depends on dataset size, dimensionality, spatial-query needs, and accuracy requirements.

3.1.1. Brute Force Approach

  • Brute-force NNS scans every point, computes its distance to the query, and tracks the closest point, with O(n) time and O(1) extra space.It guarantees the true nearest neighbor, but its linear cost limits it to small datasets.Source: §3.1.1 · p. 6, §3.1.3 · p. 7

3.1.2. Tree-Based Approach

  • Tree searches use a priority queue ordered by distance to the query, visiting the nearest-bound node first and updating the best neighbor at leaves.Ball-Tree computes node distances using bounds based on each ball’s center and radius.Source: §3.1.2 · p. 6

3.1.3. Summary and Trade-offs of NNS Methods

  • Exact methods suit small datasets, low dimensions, or strict accuracy needs, while large-scale high-dimensional settings often use approximate methods.Brute-force search guarantees the true nearest neighbor but has linear time complexity.Source: §3.1.3 · p. 7

3.1.2. Tree-Based Approach

  • KD-Tree partitions space with axis-aligned splits; Ball-Tree and M-Tree group points in balls, while R-Tree groups them in rectangles.KD-Tree works well in low dimensions but suffers from the curse of dimensionality; Ball-Tree handles high dimensions better at higher construction cost, R-Tree supports rectangle queries but may require multiple search paths, and M-Tree supports dynamic updates with higher maintenance overhead.Source: §3.1.2 · pp. 6–7, §3.1.3 · p. 7

3.2. Approximate Nearest Neighbor Search

This section surveys approximate nearest-neighbor search approaches based on hashing, trees, graphs, and quantization, describing representative methods and how they structure search. It considers trade-offs involving compression, search accuracy and efficiency, dynamic data support, and conditions shaping method use.

3.2.1. Hash-Based Approach

  • Hash-based search maps vectors to compact binary codes to reduce memory and search time, with LSH, spectral, spherical, and deep hashing offering different encoding strategies.LSH supports dynamic insertion and deletion; spectral hashing can perform well on low-dimensional manifolds, spherical hashing defines compact regions, and deep hashing learns discriminative codes for complex data.Source: §3.2.1 · pp. 7–9

3.2.2. Tree-Based Approach

  • Tree-based methods reduce the search space using Annoy’s random-projection forest, Best Bin First’s kd-tree bins, or recursively clustered k-means trees.Annoy gathers candidates from shared leaf nodes and ranks them by exact distance; k-means trees can support insertions and deletions by updating the tree.Source: §3.2.2 · pp. 9–10

3.2.3. Graph-Based Approach

  • Graph-based search greedily navigates neighbor links, while HNSW accelerates traversal with sparse upper layers leading into denser lower layers.Triangle-inequality pruning can eliminate candidates unlikely to beat the current best; a cluster-index example reports over 99.4% pruning, and the technique is described as index-agnostic.Source: §3.2.3 · pp. 10–11

3.2.4. Quantization-Based Approach

  • Quantization maps vectors to codebook entries and uses their low-precision representations to reduce storage and quickly estimate distances.An encoder selects the nearest codeword and a decoder maps its index back; because optimal codebook design is NP-hard, the survey describes heuristic LBG construction similar to k-means.Source: §3.2.4 · pp. 11–12
  • PQ compresses vectors into codes of subvector-centroid indices; IVF narrows search to nearby clusters, and IVF_PQ combines both, with higher nprobe improving results but increasing search time.IVF partitions vectors into regions and searches a few nearest regions; IVF_PQ can use local or globally unified PQ for dimensionality reduction.Source: §3.2.4 · pp. 12, 14
  • OPQ optimizes space decomposition and codebooks to reduce quantization distortion, while online PQ [114] updates codebooks and codes for dynamic data without offline retraining or reindexing.Online PQ can handle data streams and incremental datasets; OPQ performance depends on data dimensionality, subvector count, centroid count, and distance-approximation method.Source: §3.2.4 · p. 13
  • ScaNN [99] optimizes MIPS through search-space pruning and anisotropic quantization, since minimizing average distance does not necessarily optimize nearest-neighbor accuracy.Its anisotropic loss separates parallel and orthogonal quantization errors to better fit directional data structure and ellipsoidal or irregular distributions.Source: §3.2.4 · pp. 13–14
  • RaBitQ [37] compresses D-dimensional vectors into D-bit strings with a sharp theoretical distance-error bound and empirically outperforms PQ variants in accuracy-efficiency trade-off using bitwise or SIMD acceleration.Its empirical behavior closely aligns with theoretical analysis, making it valuable where reliability and high performance are both required.Source: §3.2.4 · p. 14

3.2.5. Summary and Trade-offs of ANNS Methods

  • Hashing suits static high-dimensional sparse data but may have limited recall; trees work in low dimensions but degrade in high dimensions, while graphs balance accuracy and speed at high memory cost.Quantization reduces storage for memory-constrained settings but may sacrifice accuracy; method choice depends on dimensionality, query patterns, hardware resources, and update frequency.Source: §3.2.5 · p. 14

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

The database information is current through December 1, 2024, and the table defines its support and distance-function abbreviations.

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

4. Vector Database Comparison

The comparison surveys mainstream VDB features and evaluates their loading and search performance. Results show varied strengths across systems, with HARMONY offering a promising distributed-ANNS direction.

4.1. The Comparison of Features and Characteristics of Vector Databases

  • All compared VDBs support NNS and ANNS, but indexing strategies vary; every listed database except Pinecone supports graph-based methods.The feature comparison also considers query types, distance functions, scalability, maximum dimensions, and data-management features.Source: §4.1 · p. 16
  • PgVector, QdrantCloud, and Pinecone support horizontal and vertical scaling; WeaviateCloud, Milvus, and ElasticCloud support horizontal scaling only, while ZillizCloud supports vertical scaling only.All listed databases except ElasticCloud support replication, sharding, and partitioning.Source: §4.1 · p. 17
  • Most listed VDBs support maximum dimensions from 16,000 to 65,535; QdrantCloud defaults to 65,535 but can be configured higher.Dimension information was unavailable for ElasticCloud and Pinecone.Source: §4.1 · p. 17

4.2. The Comparison of Loading Capacity and Search Performance of VDB

  • The evaluation uses VectorDBBench results for seven VDBs under 2-CPU, 8-GB configurations, covering capacity, search, and filtering with QPS, recall, latency, and load metrics.Capacity cases use SIFT and GIST; search cases use Google C4 and measure index-building time, recall, latency, and maximum QPS.Source: §4.2 · p. 17
  • Milvus ranked first overall (QPS 380; latency 12.4 milliseconds), ElasticCloud last (QPS 11.29; latency 361 milliseconds), while ZillizCloud had the best latency at 6 milliseconds.No database ranked in the top three across all tests; the overall rank is an unweighted average and preliminary, and timeout penalties should not be treated as definitive performance.Source: Figure 7 · p. 18, §4.2 · p. 18
  • HARMONY combines multi-granularity partitioning with early-stop pruning; experiments report 4.63× higher throughput than leading distributed VDBs and 58% improvement for skewed workloads.The system targets load imbalance and high communication overhead associated with traditional partition strategies.Source: §4.2 · p. 18

5. Challenges

The paper identifies challenges in indexing high-dimensional vectors, accommodating heterogeneous data, and scaling distributed processing. It also highlights underexplored application scenarios and data-security concerns.

5.1. High-Dimensional Vector Index and Search

  • Billions of vectors with hundreds or thousands of dimensions challenge storage and computation; traditional B-trees and hash tables suffer dimensionality catastrophe, motivating specialized ANN, hashing, quantization, or graph-based methods.Source: §5.1 · p. 18

5.2. Support for Heterogeneous Vector Data Types

  • Dense, sparse, and binary vectors differ in dimensionality, sparsity, distribution, and similarity metrics, requiring flexible indexing that adapts to their varied characteristics.Source: §5.2 · p. 18

5.3. Distributed Parallel Processing Support

  • Scaling beyond one machine requires distributed parallel processing, with data partitioning, load balancing, fault tolerance, and consistency as challenges.Source: §5.3 · p. 18

5.4. Integration with Emerging Application Scenarios

  • Incremental k-NN search faces an imbalance between processed and displayed data, and most VDBs do not effectively support it; hybrid keyword-vector retrieval also must balance scale, efficiency, and retrieval quality.Source: §5.4 · pp. 18–19

5.5. Data Security and Privacy Protection

  • VDBs remain at an early stage in security and privacy protection; exposed embeddings and cloud storage or transmission can increase privacy risks.The paper discusses traditional safeguards alongside blockchain tables and AI-based anomaly detection as future directions.Source: §5.5 · p. 19

6. Synergy of LLMs and VDBs

The section describes complementary roles for VDBs and LLMs: VDBs support vector storage and retrieval for LLMs, while LLMs can assist database tasks. It outlines their applications and a layered framework for combining them.

6.1. VDBs for LLMs

  • VDBs support LLMs facing hallucinations and forgetting through external knowledge, semantic caching, and storage of historical information that can be updated.The section also notes that LLMs need high-dimensional vector storage and retrieval when processing natural language.Source: §6.1 · pp. 19–20, §6 · p. 19
  • Retrieval-Augmented Generation (RAG) retrieves relevant information from an external knowledge base and supplies it as a prompt for LLM generation.Its workflow stores embedded data chunks in a VDB, retrieves semantically similar chunks for a user query, then combines retrieved information with the question to generate an answer.Source: §6.1 · p. 19
  • As a semantic cache, a VDB matches query embeddings to reduce redundant third-party model API calls, costs, and response time.The section also describes scalability under fluctuating workloads and support for multiple embedding models and configurations.Source: §6.1 · p. 19

6.2. LLMs for VDBs

  • LLMs can assist database management by diagnosing abnormal metrics, suggesting causes and solutions, translating natural-language requests into queries, and adapting to new tasks with minimal fine-tuning.The section attributes these examples to LLM integration with databases.Source: §6.2 · p. 20
  • LLMs can generate or enrich text from vector inputs and support VDB configuration, bottleneck diagnosis, and heterogeneous data processing.The section presents these as applications of combining LLM semantic understanding with vectorized retrieval.Source: §6.2 · p. 20

6.3. A General LLMs and VDBs Synergized Framework

  • The proposed synergized framework has user, model, AI database, and data levels, linking prompts and embeddings with VDB nearest-neighbor search and generated responses.For non-general questions, retrieved results may also be passed through a domain model before returning to the LLM.Source: §6.3 · p. 20

7. Conclusion

The conclusion presents a survey of VDB algorithms, storage, and retrieval, compares representative systems, and identifies challenges and research directions.

7. Conclusion

  • The survey reviews key VDB algorithms and storage and retrieval methods.It is presented as a comprehensive and up-to-date literature review.Source: §7 · p. 22
  • It compares representative VDB systems, analyzing their design trade-offs, strengths, limitations, and typical use cases.Source: §7 · p. 22
  • It identifies key challenges and potential research directions, including improved indexing and closer integration with LLMs.The authors describe the survey as a reference for researchers and practitioners and as contributing to understanding the field’s current state and future direction.Source: §7 · p. 22
Loading 2310.11703v4…