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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems (GRADES) and Network Data Analytics (NDA), GRADES-NDA 2018
EditorsArnab Bhattacharya, George Fletcher, Shourya Roy, Akhil Arora, Josep Lluis Larriba Pey, Robert West
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450356954
DOIs
StatePublished - 10 Jun 2018
Externally publishedYes
Event1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, GRADES-NDA 2018 - Houston, United States
Duration: 10 Jun 2018 → …

Publication series

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

Conference

Conference1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences and Systems and Network Data Analytics, GRADES-NDA 2018
Country/TerritoryUnited States
CityHouston
Period10/06/18 → …

Keywords

  • Distributed Graph Processing
  • Graph Partitioning
  • Graph Query
  • Hybrid Barrier Synchronisation
  • Query-cut

Fingerprint

Dive into the research topics of 'Q-graph: Preserving query locality in multi-query graph processing'. Together they form a unique fingerprint.

Cite this