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

Christian Mayer, Ruben Mayer, Jonas Grunert, Kurt Rothermel, Muhammad Adnan Tariq

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

5 Zitate (Scopus)

Abstract

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 multiquery 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.

OriginalspracheEnglisch
TitelProceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), GRADES-NDA 2018
Redakteure/-innenArnab Bhattacharya, George Fletcher, Shourya Roy, Akhil Arora, Josep Lluis Larriba Pey, Robert West
Herausgeber (Verlag)Association for Computing Machinery, Inc
ISBN (elektronisch)9781450356954
DOIs
PublikationsstatusVeröffentlicht - 10 Juni 2018
Extern publiziertJa
Veranstaltung1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, GRADES-NDA 2018 - Houston, USA/Vereinigte Staaten
Dauer: 10 Juni 2018 → …

Publikationsreihe

NameProceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), GRADES-NDA 2018

Konferenz

Konferenz1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, GRADES-NDA 2018
Land/GebietUSA/Vereinigte Staaten
OrtHouston
Zeitraum10/06/18 → …

Fingerprint

Untersuchen Sie die Forschungsthemen von „Q-graph: Preserving query locality in multi-query graph processing“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren