A curated list of awesome works related to high dimensional structure/vector search & database

• Google Vector Search (Vertex AI)
• Pinecone
• Weaviate [Beginner Guide]
• Vespa
• txtai
• marqo
• vectara
• Epsilla
• algolia
• nucliadb
• OpenSearch
• MyScale
• QdrantCloud
• zilliz
• OpenSearch's AlibabaCloud
• Typesense's Cloud
• MongoDB Atlas Vector Search
• SuperDuperDB

• From Vespa
• Vector DB Comparison by VectorHub

• ⭐ 🥇 Vector DB Feature Matrix
• ⭐ Faiss Paper
• Typesense
• Qdrant
  • Video tutorial, Notebook
• annoy
• NGT
• pgvector
• Chroma
• LlamaIndex
• vectordb
• jvector
• RAFT
• Vald
• Voyager
• tinyvector
• USearch
• vearch
• MRPT
• milvus
• infinity
• havenask

• PISA
• Tantivy
• sonic

• SimSIMD: Efficient Alternative to scipy.spatial.distance and numpy.inner

• ANN Benchmarks [Paper].
• Billion-scale ANNS Benchmarks
  • 2021 Result
• BEIR
• VectorDBBench - A Vector Database Benchmark Tool
• Qdrant's Vector Database Benchmarks
• MyScale's Vector Database Benchmark
• Li, Wen, et al. "Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement." IEEE Transactions on Knowledge and Data Engineering 32.8 (2019): 1475-1488.

• Foundations of Multidimensional and Metric Data Structures
• Introduction to Information Retrieval
• Deep Learning for Search
• Foundations of Vector Retrieval

• ⭐ VLDB
  • Tutorial:
    • New Trends in High-D Vector Similarity Search [slides, video, paper]
• ⭐ Image Retrieval in the Wild (CVPR20) [Video]
• Haystack
• Neural Search In Action
• ACM MM 2020: Effective and Efficient: Toward Open-world Instance Re-identification
  • Billion-scale Approximate Nearest Neighbor Search: [Slides, Video]
  • Is instance search a solved problem? [Slides, Video]
• Retrieval Augmented Generation and Vespa [Slides]

• Long Term Memory in AI - Vector Search and Databases (COS 495 - Princeton) [Class Notes]
• Freiburg Information Retrieval WS 2022-2023 [Website, Video Lectures]

• ⭐ Pan, James Jie, Jianguo Wang, and Guoliang Li. "Survey of Vector Database Management Systems." arXiv preprint arXiv:2310.14021 (2023). [Paper]
• Nearest neighbor search: the old, the new, and the impossible. Andoni, Alexandr. [Paper]

Source: A survey of product quantization.

• ⭐ PQ: Product quantization for nearest neighbor search. Jegou, Herve, Matthijs Douze, and Cordelia Schmid. [Paper, Code, Julia Code, nanopq]
• ⭐ k-selection on GPU: Billion-scale similarity search with gpus. Johnson, Jeff, Matthijs Douze, and Hervé Jégou [Paper, Code]
• ⭐ A survey of product quantization. Matsui, Yusuke, Yusuke Uchida, Hervé Jégou, and Shin'ichi Satoh [Paper]
• OPQ: Optimized Product Quantization. Ge, Tiezheng, Kaiming He, Qifa Ke, and Jian Sun [Homepage, Paper, Code, nanopq]
• Quicker adc: Unlocking the hidden potential of product quantization with simd. André, Fabien, Anne-Marie Kermarrec, and Nicolas Le Scouarnec [Paper, Code]
  • Accelerated nearest neighbor search with quick adc. André, Fabien, Anne-Marie Kermarrec, and Nicolas Le Scouarnec [Paper].
  • Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. Fabien André, Anne-Marie Kermarrec, Nicolas Le Scouarnec [Paper]
• ScaNN: Accelerating Large-Scale Inference with Anisotropic Vector Quantization. Guo, Ruiqi, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar [Paper, Python/C++ Inference, Julia Training/Inference]
• The inverted multi-index. Babenko, Artem, and Victor Lempitsky [Paper, Code]
• Are We There Yet? Product Quantization and its Hardware Acceleration. Fernandez-Marques, Javier, Ahmed F. AbouElhamayed, Nicholas D. Lane, and Mohamed S. Abdelfattah. [Paper]
• LibVQ: A Toolkit for Optimizing Vector Quantization and Efficient Neural Retrieval. Li, Chaofan, Zheng Liu, Shitao Xiao, Yingxia Shao, Defu Lian, and Zhao Cao. [Paper, Code]
• Matsui, Yusuke, Ryota Hinami, and Shin'ichi Satoh. "Reconfigurable Inverted Index." Proceedings of the 26th ACM international conference on Multimedia. 2018. [Paper, Project, Code]
• Aguerrebere, Cecilia, et al. "Similarity search in the blink of an eye with compressed indices." arXiv preprint arXiv:2304.04759 (2023).
• Huijben, Iris, et al. "Residual Quantization with Implicit Neural Codebooks." arXiv preprint arXiv:2401.14732 (2024). [Code]
• Rege, Aniket, et al. "Adanns: A framework for adaptive semantic search." Advances in Neural Information Processing Systems 36 (2024).
• Amara, Kenza, et al. "Nearest neighbor search with compact codes: A decoder perspective." Proceedings of the 2022 International Conference on Multimedia Retrieval. 2022.
• Krishnan, Aditya, and Edo Liberty. "Projective Clustering Product Quantization." arXiv preprint arXiv:2112.02179 (2021).
• Noh, Haechan, Taeho Kim, and Jae-Pil Heo. "Product quantizer aware inverted index for scalable nearest neighbor search." Proceedings of the IEEE/CVF International Conference on Computer Vision. 2021.
• Zhan, Jingtao, et al. "Jointly optimizing query encoder and product quantization to improve retrieval performance." Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021.
• Wang, Runhui, and Dong Deng. "DeltaPQ: lossless product quantization code compression for high dimensional similarity search." Proceedings of the VLDB Endowment 13.13 (2020): 3603-3616.
• Jang, Young Kyun, and Nam Ik Cho. "Generalized product quantization network for semi-supervised image retrieval." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020.
• Chen, Ting, Lala Li, and Yizhou Sun. "Differentiable product quantization for end-to-end embedding compression." International Conference on Machine Learning. PMLR, 2020.
• Huang, Rong, et al. "Learning Discrete Document Representations in Web Search." Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.

• ⭐ Wang, Zeyu, et al. "Graph-and Tree-based Indexes for High-dimensional Vector Similarity Search: Analyses, Comparisons, and Future Directions." Data Engineering (2023): 3-21.
• ⭐ A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Wang, Mengzhao, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. [Paper, Code]
• Lin, Peng-Cheng, and Wan-Lei Zhao. "Graph based nearest neighbor search: Promises and failures." arXiv preprint arXiv:1904.02077 (2019).
• ⭐ HNSW: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. Malkov, Yu A., and Dmitry A. Yashunin. [Paper, Code], Rust Version
• Scaling Graph-Based ANNS Algorithms to Billion-Size Datasets: A Comparative Analysis. Dobson, Magdalen, Zheqi Shen, Guy E. Blelloch, Laxman Dhulipala, Yan Gu, Harsha Vardhan Simhadri, and Yihan Sun. [Paper]
• FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search. Chen, Patrick, Wei-Cheng Chang, Jyun-Yu Jiang, Hsiang-Fu Yu, Inderjit Dhillon, and Cho-Jui Hsieh [Paper, Video]
• NSG : Navigating Spread-out Graph For Approximate Nearest Neighbor Search. Fu, Cong, Chao Xiang, Changxu Wang, and Deng Cai. [Paper, Code]
• EFANNA : Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph. Cong Fu, Deng Cai. [Paper, Code]
• Khan, Saim, et al. "BANG: Billion-Scale Approximate Nearest Neighbor Search using a Single GPU." arXiv preprint arXiv:2401.11324 (2024).
• Ootomo, Hiroyuki, et al. "Cagra: Highly parallel graph construction and approximate nearest neighbor search for gpus." arXiv preprint arXiv:2308.15136 (2023).
• Oguri, Yutaro, and Yusuke Matsui. "Theoretical and Empirical Analysis of Adaptive Entry Point Selection for Graph-based Approximate Nearest Neighbor Search." arXiv preprint arXiv:2402.04713 (2024).
• Oguri, Yutaro, and Yusuke Matsui. "General and practical tuning method for off-the-shelf graph-based index: Sisap indexing challenge report by team utokyo." International Conference on Similarity Search and Applications. Cham: Springer Nature Switzerland, 2023.
• Wang, Mengzhao, et al. "Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment." arXiv preprint arXiv:2401.02116 (2024).
• Manohar, Magdalen Dobson, et al. "ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms." Proceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 2024. [Code]
• Wang, Mengzhao, et al. "An Efficient and Robust Framework for Approximate Nearest Neighbor Search with Attribute Constraint." Advances in Neural Information Processing Systems 36 (2024).
• Yu, Shangdi, et al. "Pecann: Parallel efficient clustering with graph-based approximate nearest neighbor search." arXiv preprint arXiv:2312.03940 (2023).
• Azizi, Ilias, Karima Echihabi, and Themis Palpanas. "ELPIS: Graph-Based Similarity Search for Scalable Data Science." Proceedings of the VLDB Endowment 16.6 (2023): 1548-1559.
• Indyk, Piotr, and Haike Xu. "Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations." Advances in Neural Information Processing Systems 36 (2024).
• Liu, Jun, et al. "Optimizing Graph-based Approximate Nearest Neighbor Search: Stronger and Smarter." 2022 23rd IEEE International Conference on Mobile Data Management (MDM). IEEE, 2022.
• Wang, Hui, Yong Wang, and Wan-Lei Zhao. "Graph-based Approximate NN Search: A Revisit." arXiv preprint arXiv:2204.00824 (2022).
• Peng, Zhen, et al. "Speed-ANN: Low-Latency and High-Accuracy Nearest Neighbor Search via Intra-Query Parallelism." arXiv preprint arXiv:2201.13007 (2022).
• Lu, Kejing, et al. "HVS: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search." Proceedings of the VLDB Endowment 15.2 (2021): 246-258. [Code]
• Yingfan, Liu, Cheng Hong, and Cui Jiangtao. "Revisiting $ k $-Nearest Neighbor Graph Construction on High-Dimensional Data: Experiments and Analyses." arXiv preprint arXiv:2112.02234 (2021).
• Zhu, Dantong, and Minjia Zhang. "Understanding and Generalizing Monotonic Proximity Graphs for Approximate Nearest Neighbor Search." arXiv preprint arXiv:2107.13052 (2021).
• Gottesbüren, Lars, et al. "Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search." arXiv preprint arXiv:2403.01797 (2024).
• Singh, Aditi, et al. "Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search." arXiv preprint arXiv:2105.09613 (2021).
• Wang, Hui, Wan-Lei Zhao, and Xiangxiang Zeng. "Large-Scale Approximate k-NN Graph Construction on GPU." arXiv preprint arXiv:2103.15386 (2021).
• Patel, Liana, et al. "ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data." arXiv preprint arXiv:2403.04871 (2024).

• Diskann: Fast accurate billion-point nearest neighbor search on a single node. Jayaram Subramanya, Suhas, et al. [Paper, Code]
• Li, Haitao, et al. "Constructing Tree-based Index for Efficient and Effective Dense Retrieval." arXiv preprint arXiv:2304.11943 (2023).
• Engels, Joshua, et al. "Approximate Nearest Neighbor Search with Window Filters." arXiv preprint arXiv:2402.00943 (2024).
• Song, Yang, et al. "ProMIPS: Efficient high-dimensional C-approximate maximum inner product search with a lightweight index." 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 2021.

• ⭐ Awesome Papers on Learning to Hash
• ⭐ A survey on learning to hash. Wang, Jingdong, Ting Zhang, Nicu Sebe, and Heng Tao Shen [Paper]
• ⭐ A survey on deep hashing methods. Luo, Xiao, Haixin Wang, Daqing Wu, Chong Chen, Minghua Deng, Jianqiang Huang, and Xian-Sheng Hua. [Paper]
• ⭐ Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. Gong, Yunchao, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin [Paper, Python code, Matlab code]
• Gan, Yukang, et al. "Binary Embedding-based Retrieval at Tencent." arXiv preprint arXiv:2302.08714 (2023).
• Yan, Bencheng, et al. "Binary code based hash embedding for web-scale applications." Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2021.
• Weng, Zhenyu, and Yuesheng Zhu. "Unsupervised Online Hashing with Multi-Bit Quantization." Proceedings of the Asian Conference on Computer Vision. 2022.
• Huang, Qiang, Yifan Lei, and Anthony KH Tung. "Point-to-hyperplane nearest neighbor search beyond the unit hypersphere." Proceedings of the 2021 International Conference on Management of Data. 2021.
• Weng, Zhenyu, Yuesheng Zhu, and Ruixin Liu. "Fast Search on Binary Codes by Weighted Hamming Distance." arXiv preprint arXiv:2009.08591 (2020).
• Jian, Xiaozheng, et al. "Fast top-K cosine similarity search through XOR-friendly binary quantization on GPUs." arXiv preprint arXiv:2008.02002 (2020).
• Zheng, Bolong, et al. "PM-LSH: A fast and accurate LSH framework for high-dimensional approximate NN search." Proceedings of the VLDB Endowment 13.5 (2020): 643-655.
• Eghbali, Sepehr. "Scalable Nearest Neighbor Search with Compact Codes." (2019).
• Lei, Yifan, et al. "Locality-sensitive hashing scheme based on longest circular co-substring." Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2020.

• Chen, Qi, et al. "Spann: Highly-efficient billion-scale approximate nearest neighbor search." arXiv preprint arXiv:2111.08566 (2021). [Code]
• Li, Yuliang, et al. "Index-based, high-dimensional, cosine threshold querying with optimality guarantees." Theory of Computing Systems 65 (2021): 42-83.
• Chen, Yewang, et al. "Semi-convex hull tree: Fast nearest neighbor queries for large scale data on GPUs." 2018 IEEE International Conference on Data Mining (ICDM). IEEE, 2018.
• Engels, Joshua, Benjamin Coleman, and Anshumali Shrivastava. "Practical near neighbor search via group testing." Advances in Neural Information Processing Systems 34 (2021): 9950-9962. [Supplement]
• Gong, Long, et al. "iDEC: indexable distance estimating codes for approximate nearest neighbor search." Proceedings of the VLDB Endowment 13.9 (2020).
• Lu, Kejing, et al. "VHP: approximate nearest neighbor search via virtual hypersphere partitioning." Proceedings of the VLDB Endowment 13.9 (2020): 1443-1455.

• Qin, An, et al. "Maze: A Cost-Efficient Video Deduplication System at Web-scale." Proceedings of the 30th ACM International Conference on Multimedia. 2022.
• Doshi, Ishita, et al. "LANNS: a web-scale approximate nearest neighbor lookup system." arXiv preprint arXiv:2010.09426 (2020).

• Search Optimization with Query Likelihood Boosting and Two-Level Approximate Search for Edge Devices
• Gao, Jianyang, and Cheng Long. "High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations." Proceedings of the ACM on Management of Data 1.2 (2023): 1-27.
• Approximate Nearest Neighbor Search in Recommender Systems. Yury Malkov.
• Accelerating vector search on the GPU with RAPIDS RAFT. Corey Nolet
• Gupta, Gaurav, et al. "CAPS: A Practical Partition Index for Filtered Similarity Search." arXiv preprint arXiv:2308.15014 (2023).
• Zhu, Yuhao. "RTNN: accelerating neighbor search using hardware ray tracing." Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2022. [Code]
• Levi, Asaf, et al. "Physical vs. Logical Indexing with {IDEA}: Inverted {Deduplication-Aware} Index." 22nd USENIX Conference on File and Storage Technologies (FAST 24). 2024. [Code]
• Carra, Damiano, and Giovanni Neglia. "Taking two Birds with one k-NN Cache." 2021 IEEE Global Communications Conference (GLOBECOM). IEEE, 2021.
• Salem, Tareq Si, Giovanni Neglia, and Damiano Carra. "Ascent Similarity Caching With Approximate Indexes." IEEE/ACM Transactions on Networking (2022).
• Li, Conglong, et al. "Improving approximate nearest neighbor search through learned adaptive early termination." Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2020.
• Karppa, Matti, Martin Aumüller, and Rasmus Pagh. "Deann: Speeding up kernel-density estimation using approximate nearest neighbor search." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

• Which BM25 do you mean? A large-scale reproducibility study of scoring variants. Kamphuis, Chris, Arjen P. de Vries, Leonid Boytsov, and Jimmy Lin [Paper]

• What is a Vector Database?
• Vector databases (Part 1): What makes each one different?
• eBay’s Blazingly Fast Billion-Scale Vector Similarity Engine
• Computer Vision Meetup: Computer Vision Applications at Scale with Vector Databases
• How to choose your vector database in 2023?
• Do we really need a specialized vector database?
• Vector database is not a separate database category
• Vector Databases: A First-Principles Approach
• Vector Search RAG Tutorial – Combine Your Data with LLMs with Advanced Search
• Efficient Vector Similarity Search in Recommender Workflows Using Milvus with NVIDIA Merlin
• Vector Databases: A Beginner’s Guide!
• Vector Database and Spring IA