Glign: Taming Misaligned Graph Traversals in Concurrent Graph Processing
Xizhe Yin, Zhijia Zhao, Rajiv Gupta
Abstract
In concurrent graph processing, different queries are evaluated on the same graph simultaneously, sharing the graph accesses via the memory hierarchy. However, different queries may traverse the graph differently, especially for those starting from different source vertices. When these graph traversals are ”misaligned”, the benefits of graph access sharing can be seriously compromised. As more concurrent queries are added to the evaluation batch, the issue tends to become even worse.
Topics & Concepts
Computer scienceTraverseGraphButterfly graphTheoretical computer scienceNull graphVoltage graphParallel computingLine graphGeographyGeodesyGraph Theory and AlgorithmsAdvanced Database Systems and QueriesData Management and Algorithms