2023

Survey of Vector Database Management Systems

Pan, James Jie, Wang, Jianguo, Li, Guoliang

Understand

There are now over 20 commercial vector database management systems (VDBMSs), all produced within the past five years.

But embedding-based retrieval has been studied for over ten years, and similarity search a staggering half century and more.
Driving this shift from algorithms to systems are new data intensive applications, notably large language models, that demand vast stores of unstructured data coupled with reliable, secure, fast, and scalable query processing capability.
A variety of new data management techniques now exist for addressing these needs, however there is no comprehensive survey to thoroughly review these techniques and systems.

Built on

Proc. USSR Acad. Sci. 146
Adelson-Velsky, G., Landis, E.: An algorithm for the organization of information · 1962
Earlier work this paper cites.
Commun. ACM 18
Bentley, J.L.: Multidimensional binary search trees used for associative searching · 1975
Earlier work this paper cites.
Acta Inform. 9
Lee, D., Wong, C.: Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees · 1977
Earlier work this paper cites.
SIAM J. Comput. 9
Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem · 1980
Earlier work this paper cites.
Pattern Recognit. 12
Toussaint, G.T.: The relative neighbourhood graph of a finite planar set · 1980
Earlier work this paper cites.
IEEE Trans. Inform. Theory 28
Lloyd, S.: Least squares quantization in PCM · 1982
Earlier work this paper cites.
IEEE ASSP Mag. 1
Gray, R.M.: Vector quantization · 1984
Earlier work this paper cites.
In: ACSSC, pp. 548–553 (1988)
Dearholt, D., Gonzales, N., Kurup, G.: Monotonic search networks for computer vision databases · 1988
Earlier work this paper cites.
Discrete Comput. Geom. 4
Vaidya, P.M.: An O ⁡ ( n log ⁡ n ) O(n\log n) algorithm for the all-nearest-neighbors problem · 1989
Earlier work this paper cites.
Springer (1991)
Gersho, A., Gray, R.M.: Vector Quantization and Signal Compression · 1991
Earlier work this paper cites.
Computing 46
Su, T.H., Chang, R.C.: On constructing the relative neighborhood graphs in Euclidean k k -dimensional spaces · 1991
Earlier work this paper cites.
Proc. IEEE 80
Jaromczyk, J., Toussaint, G.: Relative neighborhood graphs and their relatives · 1992
Earlier work this paper cites.
Inform. Comput. 106
Meiser, S.: Point location in arrangements of hyperplanes · 1993
Earlier work this paper cites.
In: SODA, pp. 311–321 (1993)
Yianilos, P.N.: Data structures and algorithms for nearest neighbor search in general metric spaces · 1993
Earlier work this paper cites.
Algorithmica 15
Edelsbrunner, H., Shah, N.R.: Incremental topological flipping works for regular triangulations · 1996
Earlier work this paper cites.
Acta Inform. 33
O’Neil, P., Cheng, E., Gawlick, D., O’Neil, E.: The log-structured merge-tree (LSM-tree) · 1996
Earlier work this paper cites.
Proc. VLDB Endow. pp. 426–435 (1997)
Ciaccia, P., Patella, M., Zezula, P.: M-Tree: An efficient access method for similarity search in metric spaces · 1997
Earlier work this paper cites.
Discrete Comput. Geom. 17
Eppstein, D., Paterson, M.S., Yao, F.F.: On nearest-neighbor graphs · 1997
Earlier work this paper cites.
Proc. VLDB Endow. pp. 13–14 (1997)
Sellis, T., Roussopoulos, N., Faloutsos, C.: Multidimensional access methods: Trees have grown everywhere · 1997
Earlier work this paper cites.
In: STOC, pp. 604–613 (1998)
Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality · 1998
Earlier work this paper cites.
Nature 393
Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks · 1998
Earlier work this paper cites.
Proc. VLDB Endow. pp. 194–205 (1998)
Weber, R., Schek, H.J., Blott, S.: A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces · 1998
Earlier work this paper cites.
In: ICDT (1999)
Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U.: When is “nearest neighbor” meaningful? · 1999
Earlier work this paper cites.
Nature 406
Kleinberg, J.M.: Navigation in a small world · 2000
Earlier work this paper cites.
In: ICDT (2001)
Aggarwal, C.C., Hinneburg, A., Keim, D.A.: On the surprising behavior of distance metrics in high dimensional space · 2001
Earlier work this paper cites.
VLDB J. (2002)
Navarro, G.: Searching in metric spaces by spatial approximation · 2002
Earlier work this paper cites.
In: ICCV, pp. 1470–1477 (2003)
Sivic, Zisserman: Video Google: A text retrieval approach to object matching in videos · 2003
Earlier work this paper cites.
In: SCG, pp. 253–262 (2004)
Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing scheme based on p-stable distributions · 2004
Earlier work this paper cites.
In: NeurIPS, pp. 825–832 (2004)
Liu, T., Moore, A.W., Gray, A., Yang, K.: An investigation of practical approximate nearest neighbor algorithms · 2004
Earlier work this paper cites.
In: SPIRE, pp. 127–138 (2005)
Paredes, R., Chávez, E.: Using the k k -nearest neighbor graph for proximity searching in metric spaces · 2005
Earlier work this paper cites.
In: FOCS, pp. 459–468 (2006)
Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions · 2006
Earlier work this paper cites.
In: WEA (2006)
Paredes, R., Chávez, E., Figueroa, K., Navarro, G.: Practical construction of k k -nearest neighbor graphs in metric spaces · 2006
Earlier work this paper cites.
Proc. VLDB Endow. pp. 950–961 (2007)
Lv, Q., Josephson, W., Wang, Z., Charikar, M., Li, K.: Multi- probe LSH: Efficient indexing for high-dimensional similarity search · 2007
Earlier work this paper cites.
In: AISTATS (2007)
Salakhutdinov, R.R., Hinton, G.E.: Learning a nonlinear embedding by preserving class neighbourhood structure · 2007
Earlier work this paper cites.
Commun. ACM 51
Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions · 2008
Earlier work this paper cites.
Springer-Verlag (2008)
Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3 edn · 2008
Earlier work this paper cites.
In: STOC, pp. 537–546 (2008)
Dasgupta, S., Freund, Y.: Random projection trees and low dimensional manifolds · 2008
Earlier work this paper cites.
IEEE Micro. 28
Lindholm, E., Nickolls, J., Oberman, S., Montrym, J.: NVIDIA Tesla: A unified graphics and computing architecture · 2008
Earlier work this paper cites.
In: CVPR (2008)
Silpa-Anan, C., Hartley, R.: Optimised KD · 2008
Earlier work this paper cites.
In: NeurIPS, pp. 1753–1760 (2008)
Weiss, Y., Torralba, A., Fergus, R.: Spectral hashing · 2008
Earlier work this paper cites.

Similar

Prentice-Hall (2009)
Jurafsky, D., Martin, J.H.: Speech and Language Processing, 2nd edn · 2009
Cited alongside, same era.
In: VISAPP (2009)
Muja, M., Lowe., D.G.: FLANN: Fast library for approximate nearest neighbors · 2009
Cited alongside, same era.
SIGOPS Oper. Syst. Rev. 44
Lakshman, A., Malik, P.: Cassandra: A decentralized structured storage system · 2010
Cited alongside, same era.
Now Publishers (2011)
Cormode, G., Garofalakis, M., Haas, P.J., Jermaine, C.: Synopses for Massive Data: Samples, Histograms, Wavelets, Sketches · 2011
Cited alongside, same era.
In: WWW (2011)
Dong, W., Charikar, M., Li, K.: Efficient k k -nearest neighbor graph construction for generic similarity measures · 2011
Cited alongside, same era.
IEEE Trans. Pattern Anal. and Mach. Intell. 33
Jégou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search · 2011
Cited alongside, same era.
In: SIGCHI, pp. 1673–1682 (2012)
Fisher, D., Popov, I., Drucker, S., Schraefel, M.C.: Trust me, I’m partially right: Incremental visualization lets analysts explore large datasets faster · 2012
Cited alongside, same era.
In: LIPIcs (2012)
Vempala, S.S.: Randomly-oriented k k - d d trees adapt to intrinsic dimension · 2012
Cited alongside, same era.
In: MM, pp. 179–188 (2012)
Wang, J., Li, S.: Query-driven iterated neighborhood graph search for large scale indexing · 2012
Cited alongside, same era.
In: CVPR, pp. 1106–1113 (2012)
Wang, J., Wang, J., Zeng, G., Tu, Z., Gan, R., Li, S.: Scalable k k -NN graph construction for visual descriptors · 2012
Cited alongside, same era.
In: COLT, pp. 317–337 (2013)
Dasgupta, S., Sinha, K.: Randomized partition trees for exact nearest neighbor search · 2013
Cited alongside, same era.
In: CVPR, pp. 2946–2953 (2013)
Ge, T., He, K., Ke, Q., Sun, J.: Optimized product quantization for approximate nearest neighbor search · 2013
Cited alongside, same era.

Then

VLDB J. 29
Luo, C., Carey, M.J.: LSM-Based storage techniques: A survey · 2019
Later among the works it cites.
In: KDD, pp. 1378–1388 (2019)
Ram, P., Sinha, K.: Revisiting k d kd -tree for nearest neighbor search · 2019
Later among the works it cites.
In: NeurIPS (2019)
Subramanya, S.J., Devvrit, Kadekodi, R., Krishnaswamy, R., Simhadri, H.: DiskANN: Fast accurate billion-point nearest neighbor search on a single node · 2019
Later among the works it cites.
Proc. VLDB Endow. 12
Zhan, C., Su, M., Wei, C., Peng, X., Lin, L., Wang, S., Chen, Z., Li, F., Pan, Y., Zheng, F., Chai, C.: AnalyticDB: Real-time OLAP database system at Alibaba Cloud · 2019
Later among the works it cites.
Inform. Syst. 87
Aumüller, M., Bernhardsson, E., Faithfull, A.: ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms · 2020
Later among the works it cites.
In: ICLR (2020)
Chang, W.C., Yu, F.X., Chang, Y.W., Yang, Y., Kumar, S.: Pre-training tasks for embedding-based large-scale retrieval · 2020
Later among the works it cites.
In: ICML (2020)
Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F., Kumar, S.: Accelerating large-scale inference with anisotropic vector quantization · 2020
Later among the works it cites.
IEEE Trans. Knowl. Data Eng. 32
Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., Lin, X.: Approximate nearest neighbor search on high dimensional data — Experiments, analyses, and improvement · 2020
Later among the works it cites.
IEEE Trans. Pattern Anal. and Mach. Intell. 42
Malkov, Y., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs · 2020
Later among the works it cites.
Entropy 22
Mirkes, E.M., Allohibi, J., Gorban, A.: Fractional norms and quasinorms do not help to overcome the curse of dimensionality · 2020
Later among the works it cites.
In: ICML (2020)
Prokhorenkova, L., Shekhovtsov, A.: Graph-based nearest neighbor search: From practice to theory · 2020
Later among the works it cites.
Proc. VLDB Endow. 13
Qin, J., Wang, W., Xiao, C., Zhang, Y.: Similarity query processing for high-dimensional data · 2020
Later among the works it cites.
Proc. VLDB Endow. 13
Wang, R., Deng, D.: DeltaPQ: Lossless product quantization code compression for high dimensional similarity search · 2020
Later among the works it cites.
Proc. VLDB Endow. 13
Wei, C., Wu, B., Wang, S., Lou, R., Zhan, C., Li, F., Cai, Y.: AnalyticDB-V: A hybrid analytical engine towards query fusion for structured and unstructured data · 2020
Later among the works it cites.
In: SIGMOD, pp. 2241–2253 (2020)
Yang, W., Li, T., Fang, G., Wei, H.: PASE: PostgreSQL ultra-high-dimensional approximate nearest neighbor search extension · 2020
Later among the works it cites.
In: SIGMOD, pp. 2601–2616 (2020)
Zhang, H., Cao, L., Yan, Y., Madden, S., Rundensteiner, E.A.: Continuously adaptive similarity search · 2020
Later among the works it cites.
IEEE Trans. Pattern Anal. and Mach. Intell. 43
André, F., Kermarrec, A.M., Le Scouarnec, N.: Quicker ADC: Unlocking the hidden potential of product quantization with SIMD · 2021
Later among the works it cites.
In: NeurIPS (2021)
Chen, Q., Zhao, B., Wang, H., Li, M., Liu, C., Li, Z., Yang, M., Wang, J., Yang, M., Wang, J.: SPANN: Highly-efficient billion-scale approximate nearest neighbor search · 2021
Later among the works it cites.
Proc. VLDB Endow. 14
Echihabi, K., Zoumpatianos, K., Palpanas, T.: New trends in high-D vector similarity search: AI-driven, progressive, and distributed · 2021
Later among the works it cites.
IEEE Trans. Big Data 7
Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with GPUs · 2021
Later among the works it cites.
In: KDD, pp. 4062–4063 (2021)
Qin, J., Wang, W., Xiao, C., Zhang, Y., Wang, Y.: High-dimensional similarity query processing for data science · 2021
Later among the works it cites.
In: SIGMOD, pp. 2614–2627 (2021)
Wang, J., Yi, X., Guo, R., Jin, H., Xu, P., Li, S., Wang, X., Guo, X., Li, C., Xu, X., Yu, K., Yuan, Y., Zou, Y., Long, J., Cai, Y., Li, Z., Zhang, Z., Mo, Y., Gu, J., Jiang, R., Wei, Y., Xie, C.: Milvus: A purpose-built vector data management system · 2021
Later among the works it cites.
Proc. VLDB Endow. 14
Wang, M., Xu, X., Yue, Q., Wang, Y.: A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search · 2021
Later among the works it cites.
ACM Comput. Surv. 55
Chen, L., Gao, Y., Song, X., Li, Z., Zhu, Y., Miao, X., Jensen, C.S.: Indexing metric spaces for exact similarity search · 2022
Later among the works it cites.
Proc. VLDB Endow. 15
Guo, R., Luan, X., Xiang, L., Yan, X., Yi, X., Luo, J., Cheng, Q., Xu, W., Luo, J., Liu, F., Cao, Z., Qiao, Y., Wang, T., Tang, B., Xie, C.: Manu: A cloud native vector database management system · 2022
Later among the works it cites.
In: SIGIR, pp. 3373–3374 (2022)
Kim, Y.: Applications and future of dense retrieval in industry · 2022
Later among the works it cites.
In: SIGMOD, pp. 2483–2488 (2022)
Li, G., Zhang, C.: HTAP databases: What is new and what is next · 2022
Later among the works it cites.
Proc. VLDB Endow. 15
Meng, J., Wang, H., Xu, J., Ogihara, M.: ONe Index for All Kernels (ONIAK): A zero re-indexing LSH solution to ANNS-ALT (After Linear Transformation) · 2022
Later among the works it cites.
In: SIGMOD, pp. 2340–2352 (2022)
Prout, A., Wang, S.P., Victor, J., Sun, Z., Li, Y., Chen, J., Bergeron, E., Hanson, E., Walzer, R., Gomes, R., Shamgunov, N.: Cloud-native transactions and analytics in SingleStore · 2022
Later among the works it cites.
In: CIKM (2022)
Wu, W., He, J., Qiao, Y., Fu, G., Liu, L., Yu, J.: HQANN: Efficient and robust similarity search for hybrid queries with structured and unstructured constraints · 2022
Later among the works it cites.
VLDB J. 31
Zhu, Y., Chen, L., Gao, Y., Jensen, C.S.: Pivot selection algorithms in metric spaces: A survey and experimental study · 2022
Later among the works it cites.
IEEE Trans. Inform. Theory (2023)
Agrell, E., Allen, B.: On the best lattice quantizers · 2023
Closest in time.
In: ACL (2023)
Asai, A., Min, S., Zhong, Z., Chen, D.: Retrieval-based language models and applications · 2023
Closest in time.
Proc. VLDB Endow. 16
Azizi, I., Echihabi, K., Palpanas, T.: ELPIS: Graph-based similarity search for scalable data science · 2023
Closest in time.
In: WWW (2023)
Gollapudi, S., Karia, N., Sivashankar, V., Krishnaswamy, R., Begwani, N., Raz, S., Lin, Y., Zhang, Y., Mahapatro, N., Srinivasan, P., Singh, A., Simhadri, H.V.: Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters · 2023
Closest in time.
In: CIDR (2023)
Hambardzumyan, S., Tuli, A., Ghukasyan, L., Rahman, F., Topchyan, H., Isayan, D., McQuade, M., Harutyunyan, M., Hakobyan, T., Stranic, I., Buniatyan, D.: Deep Lake: A lakehouse for deep learning · 2023
Closest in time.
In: SIGIR (2023)
Li, H., Ai, Q., Zhan, J., Mao, J., Liu, Y., Liu, Z., Cao, Z.: Constructing tree-based index for efficient and effective dense retrieval · 2023
Closest in time.
In: SIGIR (2023)
Tagliabue, J., Greco, C.: (Vector) Space is not the final frontier: Product search as program synthesis · 2023
Closest in time.
In: SIGMOD, pp. 37–44 (2023)
Wang, J., Zhang, Q.: Disaggregated database systems · 2023
Closest in time.
In: SIGIR (2023)
Wang, W., Guo, Y., Shen, C., Ding, S., Liao, G., Fu, H., Prabhakar, P.K.: Integrity and junkiness failure handling for embedding-based retrieval: A case study in social network search · 2023
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…