A survey on concurrent processing of graph analytical queries: Systems and algorithms

• Main Authors: LI, Yuchen, SUN, Shixuan, XIAO, Hanhua, YE, Chang, LU, Shengliang, HE, Bingsheng
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Concurrent computing; network theory; data systems; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/9913
• Institution: Singapore Management University

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.