Literature by the same author
plus at Google Scholar

Bibliografische Daten exportieren
 

Q-graph : preserving query locality in multi-query graph processing

Title data

Mayer, Christian ; Mayer, Ruben ; Grunert, Jonas ; Rothermel, Kurt ; Tariq, Muhammad Adnan:
Q-graph : preserving query locality in multi-query graph processing.
In: Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) 2018. - New York : Association for Computing Machinery , 2018 . - 6
ISBN 978-1-4503-5695-4
DOI: https://doi.org/10.1145/3210259.3210265

Abstract in another language

Arising user-centric graph applications such as route planning and personalized social network analysis have initiated a shift of paradigms in modern graph processing systems towards multi-query analysis, i.e., processing multiple graph queries in parallel on a shared graph. These applications generate a dynamic number of localized queries around query hotspots such as popular urban areas. However, existing graph processing systems are not yet tailored towards these properties: The employed methods for graph partitioning and synchronization management disregard query locality and dynamism which leads to high query latency. To this end, we propose the system Q-Graph for multi-query graph analysis that considers query locality on three levels. (i) The query-aware graph partitioning algorithm Q-cut maximizes query locality to reduce communication overhead. (ii) The method for synchronization management, called hybrid barrier synchronization, allows for full exploitation of local queries spanning only a subset of partitions. (iii) Both methods adapt at runtime to changing query workloads in order to maintain and exploit locality. Our experiments show that Q-cut reduces average query latency by up to 57 percent compared to static query-agnostic partitioning algorithms.

Further data

Item Type: Article in a book
Refereed: Yes
Institutions of the University: Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science > Chair Data Systems
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science > Chair Data Systems > Chair Data Systems - Univ.-Prof. Dr. Ruben Mayer
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science
Result of work at the UBT: No
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
Date Deposited: 27 Apr 2023 08:41
Last Modified: 05 Feb 2024 07:38
URI: https://eref.uni-bayreuth.de/id/eprint/76031