# High-Throughput Vector Similarity Search in Knowledge Graphs

arXiv: https://arxiv.org/abs/2304.01926 · HTML: https://mlsanity.com/paper/2304.01926/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 51 references that are in the map.
- First posted on arXiv 4 Apr 2023.

## Builds on (most cited first, 23 of 23)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [A Comprehensive Survey of Deep Learning for Image Captioning](https://mlsanity.com/paper/1810.04020/) (2018)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [Deep Image Retrieval: Learning global representations for image search](https://mlsanity.com/paper/1604.01325/) (2016)
- [Deep Learning Based Text Classification: A Comprehensive Review](https://mlsanity.com/paper/2004.03705/) (2020)
- [Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba](https://mlsanity.com/paper/1803.02349/) (2018)
- [PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest](https://mlsanity.com/paper/2007.03634/) (2020)
- [Monolith: Real Time Recommendation System With Collisionless Embedding Table](https://mlsanity.com/paper/2209.07663/) (2022)
- [Marius: Learning Massive Graph Embeddings on a Single Machine](https://mlsanity.com/paper/2101.08358/) (2021)
- [Related Pins at Pinterest: The Evolution of a Real-World Recommender System](https://mlsanity.com/paper/1702.07969/) (2017)
- [Applying Deep Learning To Airbnb Search](https://mlsanity.com/paper/1810.09591/) (2018)
- [MariusGNN: Resource-Efficient Out-of-Core Training of Graph Neural Networks](https://mlsanity.com/paper/2202.02365/) (2022)
- [Saga: A Platform for Continuous Construction and Serving of Knowledge At Scale](https://mlsanity.com/paper/2204.07309/) (2022)
- [Qd-tree: Learning Data Layouts for Big Data Analytics](https://mlsanity.com/paper/2004.10898/) (2020)
- [Manu: A Cloud Native Vector Database Management System](https://mlsanity.com/paper/2206.13843/) (2022)
- [The Design and Implementation of a Real Time Visual Search System on JD E-commerce Platform](https://mlsanity.com/paper/1908.07389/) (2019)

## Built on by (most cited first, 19 of 19)

- [A Comprehensive Survey on Vector Database: Storage and Retrieval Technique, Challenge](https://mlsanity.com/paper/2310.11703/) (2023)
- [Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models](https://mlsanity.com/paper/2310.09949/) (2023)
- [RAGO: Systematic Performance Optimization for Retrieval-Augmented Generation Serving](https://mlsanity.com/paper/2503.14649/) (2025)
- [RetroInfer: A Vector Storage Engine for Scalable Long-Context LLM Inference](https://mlsanity.com/paper/2505.02922/) (2025)
- [Quake: Adaptive Indexing for Vector Search](https://mlsanity.com/paper/2506.03437/) (2025)
- [Incremental IVF Index Maintenance for Streaming Vector Search](https://mlsanity.com/paper/2411.00970/) (2024)
- [WeKnow-RAG: An Adaptive Approach for Retrieval-Augmented Generation Integrating Web Search and Knowledge Graphs](https://mlsanity.com/paper/2408.07611/) (2024)
- [MicroNN: An On-device Disk-resident Updatable Vector Database](https://mlsanity.com/paper/2504.05573/) (2025)
- [LEANN: A Low-Storage Vector Index](https://mlsanity.com/paper/2506.08276/) (2025)
- [Cracking Vector Search Indexes](https://mlsanity.com/paper/2503.01823/) (2025)
- [HONEYBEE: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning[Technical Report]](https://mlsanity.com/paper/2505.01538/) (2025)
- [Cloud-Native Vector Search: A Comprehensive Performance Analysis](https://mlsanity.com/paper/2511.14748/) (2025)
- [Computing in the Era of Large Generative Models: From Cloud-Native to AI-Native](https://mlsanity.com/paper/2401.12230/) (2024)
- [Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors](https://mlsanity.com/paper/2507.21989/) (2025)
- [Opal: Private Memory for Personal AI](https://mlsanity.com/paper/2604.02522/) (2026)
- [Mandol: An Agglomerative Agent Memory System for Long-Term Conversations](https://mlsanity.com/paper/2606.29778/) (2026)
- [Text2VectorSQL: Towards a Unified Interface for Vector Search and SQL Queries](https://mlsanity.com/paper/2506.23071/) (2025)
- [Exqutor: Extended Query Optimizer for Vector-augmented Analytical Queries](https://mlsanity.com/paper/2512.09695/) (2025)
- [CubeGraph: Efficient Retrieval-Augmented Generation for Spatial and Temporal Data](https://mlsanity.com/paper/2604.06616/) (2026)

## Abstract (arXiv)

There is an increasing adoption of machine learning for encoding data into vectors to serve online recommendation and search use cases. As a result, recent data management systems propose augmenting query processing with online vector similarity search. In this work, we explore vector similarity search in the context of Knowledge Graphs (KGs). Motivated by the tasks of finding related KG queries and entities for past KG query workloads, we focus on hybrid vector similarity search (hybrid queries for short) where part of the query corresponds to vector similarity search and part of the query corresponds to predicates over relational attributes associated with the underlying data vectors. For example, given past KG queries for a song entity, we want to construct new queries for new song entities whose vector representations are close to the vector representation of the entity in the past KG query. But entities in a KG also have non-vector attributes such as a song associated with an artist, a genre, and a release date. Therefore, suggested entities must also satisfy query predicates over non-vector attributes beyond a vector-based similarity predicate. While these tasks are central to KGs, our contributions are generally applicable to hybrid queries. In contrast to prior works that optimize online queries, we focus on enabling efficient batch processing of past hybrid query workloads. We present our system, HQI, for high-throughput batch processing of hybrid queries. We introduce a workload-aware vector data partitioning scheme to tailor the vector index layout to the given workload and describe a multi-query optimization technique to reduce the overhead of vector similarity computations. We evaluate our methods on industrial workloads and demonstrate that HQI yields a 31x improvement in throughput for finding related KG queries compared to existing hybrid query processing approaches.