Distributed k-Hop Query Powered by an Asynchronous Framework

Distributed k-Hop Query Powered by an Asynchronous Framework

연구 분야: Databases

학회: International Conference on Web Information Systems Engineering

The k-hop query represents a fundamental challenge in various graph applications, often supported by numerous distributed systems. The conventional approach to this query paradigm typically involves iterative layer-by-layer expansion, which inevitably increases redundant vertices as the hop count grows. Moreover, issues such as master node idle waiting and workload imbalances across computing nodes contribute to the wastage of computational resources and time. To tackle these challenges, this paper introduces an asynchronous framework for k-hop queries, namely ADFQ, designed for seamless integration into any distributed system. Diverging from the traditional vertex-centric techniques, this framework employs distributed machines to store graph blocks and process queries without waiting during deduplication between hops. By ensuring comprehensive deduplication at each hop’s conclusion and efficiently expanding frontiers, the framework significantly improves query performance. Experimental results demonstrate superior performance compared to the classic Bulk Synchronous Parallel paradigm, particularly as graph imbalances intensify.