A survey on concurrent processing of graph analytical queries: Systems and algorithms
Publication Type
Journal Article
Publication Date
11-2024
Abstract
Graph analytical queries (GAQs) are becoming increasingly important in various domains, including social networks, recommendation systems, and bioinformatics, among others. GAQs typically require iterative processing of the graph data to compute various metrics and identify patterns or anomalies. Parallel to the burgeoning demand for graph analytics, the need for Concurrent Graph Analytical Queries (CGAQs), allowing simultaneous execution of multiple graph queries, is increasing. Within social networks, CGAQ s bolster real-time analytics, concurrently investigate various network properties, such as community detection, path analysis, and influence propagation. In transportation, CGAQs concurrently optimize multiple routes and manage real-time traffic data, contributing significantly to efficient supply chain strategies and traffic management. The key property of CGAQ s lies in their capacity for shared processing, exploiting the synergies between concurrent queries, which in return opens opportunities for improved system scalability and throughput. In this survey, we present a comprehensive review of system-level and algorithm-level efforts to support CGAQ processing. We introduce a novel survey framework based on three aspects: 1) What are the sharing opportunities exploited? 2) What are the scheduling techniques proposed to maximize sharing? 3) What are the optimizations employed? We also identify important gaps and promising research directions for CGAQ processing.
Keywords
Concurrent computing, network theory, data systems
Discipline
Databases and Information Systems | Numerical Analysis and Scientific Computing
Research Areas
Data Science and Engineering
Publication
IEEE Transactions on Knowledge and Data Engineering
Volume
36
Issue
11
First Page
5508
Last Page
5528
ISSN
1041-4347
Identifier
10.1109/TKDE.2024.3393936
Publisher
Institute of Electrical and Electronics Engineers
Citation
LI, Yuchen; SUN, Shixuan; XIAO, Hanhua; YE, Chang; LU, Shengliang; and HE, Bingsheng.
A survey on concurrent processing of graph analytical queries: Systems and algorithms. (2024). IEEE Transactions on Knowledge and Data Engineering. 36, (11), 5508-5528.
Available at: https://ink.library.smu.edu.sg/sis_research/9913
Additional URL
https://doi.org/10.1109/TKDE.2024.3393936
