Open Access System for Information Sharing

Login Library

 

Conference
Cited 0 time in webofscience Cited 0 time in scopus
Metadata Downloads

Fast and Robust Distributed Subgraph Enumeration

Title
Fast and Robust Distributed Subgraph Enumeration
Authors
HAN, WOOK SHINXuguang RenJunhu WangJeffrey Xu Yu
Date Issued
27-Aug-2019
Publisher
VLDB Endowment
Abstract
We study the subgraph enumeration problem under distributed settings. Existing solutions either suffer from severe memory crisis or rely on large indexes, which makes them impractical for very large graphs. Most of them follow a synchronous model where the performance is often bottlenecked by the machine with the worst performance. Motivated by this, in this paper, we propose RADS, a Robust Asynchronous Distributed Subgraph enumeration system. RADS first identifies results that can be found using singlemachine algorithms. This strategy not only improves the overall performance but also reduces network communication and memory cost. Moreover, RADS employs a novel region-grouped multi-round expand verify & filter framework which does not need to shuffle and exchange the intermediate results, nor does it need to replicate a large part of the data graph in each machine. This feature not only reduces network communication cost and memory usage, but also allows us to adopt simple strategies for memory control and load balancing, making it more robust. Several optimization strategies are also used in RADS to further improve the performance. Our experiments verified the superiority of RADS to state-of-the-art subgraph enumeration approaches.
URI
http://oasis.postech.ac.kr/handle/2014.oak/99676
Article Type
Conference
Citation
45th Int'l Conf. on Very Large Data Bases (VLDB), page. 1344 - 1356, 2019-08-27
Files in This Item:
There are no files associated with this item.

qr_code

  • mendeley

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Related Researcher

Researcher

 HAN, WOOK SHIN
Dept of Computer Science & Enginrg
Read more

Views & Downloads

Browse