Finding and counting tree-like subgraphs using MapReduce. Zhao, Z., Chen, L., Avram, M., Li, M., Wang, G., Butt, A., Khan, M., Marathe, M., Qiu, J., & Vullikanti, A. IEEE Transactions on Multi-Scale Computing Systems, 4(3):217-230, 7, 2018. ![Finding and counting tree-like subgraphs using MapReduce [link]](https://bibbase.org/img/filetypes/link.svg "link")
Website doi abstract bibtex IEEE Several variants of the subgraph isomorphism problem, e.g., finding, counting and estimating frequencies of subgraphs in networks arise in a number of real world applications, such as web analysis, disease diffusion prediction and social network analysis. These problems are computationally challenging in having to scale to very large networks with millions of vertices. In this paper, we present SAHAD, a MapReduce algorithm for detecting and counting trees of bounded size using the elegant color coding technique developed by N. Alon et al. SAHAD is a randomized algorithm, and we show rigorous bounds on the approximation quality and the performance of it. SAHAD scales to very large networks comprising of < formula > < tex > $10^7$ < /tex > < /formula > - < formula > < tex > $10^8$ < /tex > < /formula > edges and tree-like (acyclic) templates with up to 12 vertices. Further, we extend our results by implementing SAHAD in the Harp framework, which is more of a high performance computing environment. The new implementation gives 100x improvement in performance over the standard Hadoop implementation and achieves better performance than state-of-the-art MPI solutions on larger graphs.
@article{
title = {Finding and counting tree-like subgraphs using MapReduce},
type = {article},
year = {2018},
pages = {217-230},
volume = {4},
websites = {https://ieeexplore.ieee.org/document/8090537/},
month = {7},
day = {1},
id = {1abad963-1212-3047-a2d7-667a53ae393e},
created = {2019-10-01T17:20:57.186Z},
accessed = {2019-08-21},
file_attached = {false},
profile_id = {42d295c0-0737-38d6-8b43-508cab6ea85d},
last_modified = {2020-05-11T14:43:32.716Z},
read = {false},
starred = {false},
authored = {true},
confirmed = {true},
hidden = {false},
citation_key = {Zhao2018},
folder_uuids = {36d8ccf4-7085-47fa-8ab9-897283d082c5,3b35931e-fb6d-48f9-8e01-87ee16ef0331},
private_publication = {false},
abstract = {IEEE Several variants of the subgraph isomorphism problem, e.g., finding, counting and estimating frequencies of subgraphs in networks arise in a number of real world applications, such as web analysis, disease diffusion prediction and social network analysis. These problems are computationally challenging in having to scale to very large networks with millions of vertices. In this paper, we present SAHAD, a MapReduce algorithm for detecting and counting trees of bounded size using the elegant color coding technique developed by N. Alon et al. SAHAD is a randomized algorithm, and we show rigorous bounds on the approximation quality and the performance of it. SAHAD scales to very large networks comprising of < formula > < tex > $10^7$ < /tex > < /formula > - < formula > < tex > $10^8$ < /tex > < /formula > edges and tree-like (acyclic) templates with up to 12 vertices. Further, we extend our results by implementing SAHAD in the Harp framework, which is more of a high performance computing environment. The new implementation gives 100x improvement in performance over the standard Hadoop implementation and achieves better performance than state-of-the-art MPI solutions on larger graphs.},
bibtype = {article},
author = {Zhao, Zhao and Chen, Langshi and Avram, Mihai and Li, Meng and Wang, Guanying and Butt, Ali and Khan, Maleq and Marathe, Madhav and Qiu, Judy and Vullikanti, Anil},
doi = {10.1109/TMSCS.2017.2768426},
journal = {IEEE Transactions on Multi-Scale Computing Systems},
number = {3}
}
Downloads: 0
{"_id":"YJ4Br9vZ7LkojtEqd","bibbaseid":"zhao-chen-avram-li-wang-butt-khan-marathe-etal-findingandcountingtreelikesubgraphsusingmapreduce-2018","authorIDs":[],"author_short":["Zhao, Z.","Chen, L.","Avram, M.","Li, M.","Wang, G.","Butt, A.","Khan, M.","Marathe, M.","Qiu, J.","Vullikanti, A."],"bibdata":{"title":"Finding and counting tree-like subgraphs using MapReduce","type":"article","year":"2018","pages":"217-230","volume":"4","websites":"https://ieeexplore.ieee.org/document/8090537/","month":"7","day":"1","id":"1abad963-1212-3047-a2d7-667a53ae393e","created":"2019-10-01T17:20:57.186Z","accessed":"2019-08-21","file_attached":false,"profile_id":"42d295c0-0737-38d6-8b43-508cab6ea85d","last_modified":"2020-05-11T14:43:32.716Z","read":false,"starred":false,"authored":"true","confirmed":"true","hidden":false,"citation_key":"Zhao2018","folder_uuids":"36d8ccf4-7085-47fa-8ab9-897283d082c5,3b35931e-fb6d-48f9-8e01-87ee16ef0331","private_publication":false,"abstract":"IEEE Several variants of the subgraph isomorphism problem, e.g., finding, counting and estimating frequencies of subgraphs in networks arise in a number of real world applications, such as web analysis, disease diffusion prediction and social network analysis. These problems are computationally challenging in having to scale to very large networks with millions of vertices. In this paper, we present SAHAD, a MapReduce algorithm for detecting and counting trees of bounded size using the elegant color coding technique developed by N. Alon et al. SAHAD is a randomized algorithm, and we show rigorous bounds on the approximation quality and the performance of it. SAHAD scales to very large networks comprising of < formula > < tex > $10^7$ < /tex > < /formula > - < formula > < tex > $10^8$ < /tex > < /formula > edges and tree-like (acyclic) templates with up to 12 vertices. Further, we extend our results by implementing SAHAD in the Harp framework, which is more of a high performance computing environment. The new implementation gives 100x improvement in performance over the standard Hadoop implementation and achieves better performance than state-of-the-art MPI solutions on larger graphs.","bibtype":"article","author":"Zhao, Zhao and Chen, Langshi and Avram, Mihai and Li, Meng and Wang, Guanying and Butt, Ali and Khan, Maleq and Marathe, Madhav and Qiu, Judy and Vullikanti, Anil","doi":"10.1109/TMSCS.2017.2768426","journal":"IEEE Transactions on Multi-Scale Computing Systems","number":"3","bibtex":"@article{\n title = {Finding and counting tree-like subgraphs using MapReduce},\n type = {article},\n year = {2018},\n pages = {217-230},\n volume = {4},\n websites = {https://ieeexplore.ieee.org/document/8090537/},\n month = {7},\n day = {1},\n id = {1abad963-1212-3047-a2d7-667a53ae393e},\n created = {2019-10-01T17:20:57.186Z},\n accessed = {2019-08-21},\n file_attached = {false},\n profile_id = {42d295c0-0737-38d6-8b43-508cab6ea85d},\n last_modified = {2020-05-11T14:43:32.716Z},\n read = {false},\n starred = {false},\n authored = {true},\n confirmed = {true},\n hidden = {false},\n citation_key = {Zhao2018},\n folder_uuids = {36d8ccf4-7085-47fa-8ab9-897283d082c5,3b35931e-fb6d-48f9-8e01-87ee16ef0331},\n private_publication = {false},\n abstract = {IEEE Several variants of the subgraph isomorphism problem, e.g., finding, counting and estimating frequencies of subgraphs in networks arise in a number of real world applications, such as web analysis, disease diffusion prediction and social network analysis. These problems are computationally challenging in having to scale to very large networks with millions of vertices. In this paper, we present SAHAD, a MapReduce algorithm for detecting and counting trees of bounded size using the elegant color coding technique developed by N. Alon et al. SAHAD is a randomized algorithm, and we show rigorous bounds on the approximation quality and the performance of it. SAHAD scales to very large networks comprising of < formula > < tex > $10^7$ < /tex > < /formula > - < formula > < tex > $10^8$ < /tex > < /formula > edges and tree-like (acyclic) templates with up to 12 vertices. Further, we extend our results by implementing SAHAD in the Harp framework, which is more of a high performance computing environment. The new implementation gives 100x improvement in performance over the standard Hadoop implementation and achieves better performance than state-of-the-art MPI solutions on larger graphs.},\n bibtype = {article},\n author = {Zhao, Zhao and Chen, Langshi and Avram, Mihai and Li, Meng and Wang, Guanying and Butt, Ali and Khan, Maleq and Marathe, Madhav and Qiu, Judy and Vullikanti, Anil},\n doi = {10.1109/TMSCS.2017.2768426},\n journal = {IEEE Transactions on Multi-Scale Computing Systems},\n number = {3}\n}","author_short":["Zhao, Z.","Chen, L.","Avram, M.","Li, M.","Wang, G.","Butt, A.","Khan, M.","Marathe, M.","Qiu, J.","Vullikanti, A."],"urls":{"Website":"https://ieeexplore.ieee.org/document/8090537/"},"biburl":"https://bibbase.org/service/mendeley/42d295c0-0737-38d6-8b43-508cab6ea85d","bibbaseid":"zhao-chen-avram-li-wang-butt-khan-marathe-etal-findingandcountingtreelikesubgraphsusingmapreduce-2018","role":"author","metadata":{"authorlinks":{}},"downloads":0},"bibtype":"article","creationDate":"2019-08-21T20:36:56.225Z","downloads":0,"keywords":[],"search_terms":["finding","counting","tree","subgraphs","using","mapreduce","zhao","chen","avram","li","wang","butt","khan","marathe","qiu","vullikanti"],"title":"Finding and counting tree-like subgraphs using MapReduce","year":2018,"biburl":"https://bibbase.org/service/mendeley/42d295c0-0737-38d6-8b43-508cab6ea85d","dataSources":["zgahneP4uAjKbudrQ","ya2CyA73rpZseyrZ8","R8AXtPTx5wP2dd25i"]}