at Google ScholarTitle 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 |