Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching
Open Access
- 30 September 2024
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (4) , 1-29
Abstract
Knowledge graph reasoning (KGR) answers logical queries over a knowledge graph (KG), and embedding-based KGR (EKGR) becomes popular recently, which embeds both queries and KG entities such that the vector embeddings of a query and its answer entities are similar. Compared with traditional KGR methods based on subgraph matching, EKGR produces fewer intermediate results and is more robust to missing and noisy information in the KG. However, existing systems are inefficient for serving online EKGR queries because they can only batch queries of the same type for execution (i.e., query-level batching ) and hence have limited batching opportunities due to the heterogeneity of queries. To serve EKGR queries efficiently, we propose the Atom system with operator-level batching, which decomposes queries into operators and batches operators of the same type from different queries for execution. The insight is that the types of operators are far fewer than the types of queries, and thus different queries typically share common operators, yielding more batching opportunities. To schedule the operators, Atom adopts a hybrid policy, which improves system throughput and avoids starving rare operators. For efficiency, Atom incorporates system optimizations including two-level pipeline, opportunistic submission, pre-allocated memory buffer, and tailored GPU kernels. Experiment results show that compared with existing systems, Atom can improve query throughput by over 20x and reduce query latency by over 5x. Micro experiments suggest that the designs and optimizations are effective in improving system performance.Keywords
This publication has 65 references indexed in Scilit:
- Unifying Structure Reasoning and Language Pre-Training for Complex Reasoning TasksIEEE/ACM Transactions on Audio, Speech, and Language Processing, 2023
- MTLFormer: Multi-Task Learning Guided Transformer Network for Business Process PredictionIEEE Access, 2023
- A Holistic Approach for Answering Logical Queries on Knowledge Graphs2023
- VSGM: View-Based GPU-Accelerated Subgraph Matching on Large Graphs2022
- Missing-edge aware knowledge graph inductive inference through dual graph learning and traversingExpert Systems with Applications, 2022
- Ebird: Elastic Batch for Improving Responsiveness and Throughput of Deep Learning Services2019
- Learning to Hash for Efficient Search Over Incomplete Knowledge Graphs2019
- GraphFlow: Workflow-based big graph processing2016
- Effective Utilization of CUDA Hyper-Q for Improved Power and Performance Efficiency2016
- MAGE: Matching approximate patterns in richly-attributed graphs2014