@inproceedings{033b7e8a5b6d4f418ae52658c6ba5c9f,
title = "Distributed exact subgraph matching in small diameter dynamic graphs",
abstract = "Subgraph isomorphism is a fundamental graph problem with many applications. Due to its NP-Hard nature, subgraph isomorphism in large dynamic graphs is considered as a challenging problem. In this paper, we present a distributed graph pruning algorithm (D-IDS) for dynamic graphs to enable efficient subgraph isomorphism. D-IDS continuously maintains the maximum dual simulation match in a dynamic graph. We develop D-ISI, a distributed incremental algorithm for subgraph isomorphism that utilizes D-IDS. We evaluated our algorithms on a commodity cluster in Amazon EC2 using real world graph datasets. Our evaluation results show that the graph pruning technique is highly effective on graphs with small diameter where it achieves over 60\% reduction in graph size.",
keywords = "distributed, dynamic graphs, small diameter graphs, subgraph isomorphism",
author = "Charith Wickramaarachchi and Rajgopal Kannan and Charalampos Chelmis and Prasanna, \{Viktor K.\}",
note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 4th IEEE International Conference on Big Data, Big Data 2016 ; Conference date: 05-12-2016 Through 08-12-2016",
year = "2016",
doi = "10.1109/BigData.2016.7840996",
language = "English",
series = "Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "3360--3369",
editor = "Ronay Ak and George Karypis and Yinglong Xia and Hu, \{Xiaohua Tony\} and Yu, \{Philip S.\} and James Joshi and Lyle Ungar and Ling Liu and Aki-Hiro Sato and Toyotaro Suzumura and Sudarsan Rachuri and Rama Govindaraju and Weijia Xu",
booktitle = "Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016",
}