{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T14:10:36Z","timestamp":1691849436479},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,7,25]],"date-time":"2015-07-25T00:00:00Z","timestamp":1437782400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s10766-015-0374-5","type":"journal-article","created":{"date-parts":[[2015,7,24]],"date-time":"2015-07-24T08:27:30Z","timestamp":1437726450000},"page":"772-800","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Achieving Optimal Inter-Node Communication in Graph Partitioning Using Random Selection and Breadth-First Search"],"prefix":"10.1007","volume":"44","author":[{"given":"Srimanth","family":"Gadde","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William","family":"Acosta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jordan","family":"Ringenberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Green","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay","family":"Devabhaktuni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,25]]},"reference":[{"key":"374_CR1","doi-asserted-by":"crossref","unstructured":"Kang, U., Tsourakakis, C.E., Faloutsos, C.: PEGASUS: a peta-scale graph mining system implementation and observations. Data mining, 2009. In: Ninth IEEE International Conference on ICDM\u201909. IEEE (2009)","DOI":"10.1109\/ICDM.2009.14"},{"key":"374_CR2","unstructured":"Kang, U., et al.: HADI: Fast diameter estimation and mining in massive graphs with Hadoop. Carnegie Mellon University, School of Computer Science, Machine Learning Department (2008)"},{"key":"374_CR3","doi-asserted-by":"crossref","unstructured":"Malewicz, G., et al.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 International Conference on Management of data. ACM (2010)","DOI":"10.1145\/1807167.1807184"},{"key":"374_CR4","doi-asserted-by":"crossref","unstructured":"Shao, B., Wang, H., Li, Y.: The Trinity graph engine. Technical Report 161291, Microsoft Research (2012)","DOI":"10.1145\/2463676.2467799"},{"issue":"1","key":"374_CR5","first-page":"285","volume":"3","author":"Y Bu","year":"2010","unstructured":"Bu, Y., Howe, B., Balazinska, M., Ernst, M.D.: Haloop: efficient iterative data processing on large clusters. PVLDB 3(1), 285\u2013296 (2010)","journal-title":"PVLDB"},{"key":"374_CR6","unstructured":"Yanfeng, Z., et al.: Priter: a distributed framework for prioritized iterative computations. In: Proceedings of the 2nd ACM Symposium on Cloud Computing. ACM (2011)"},{"key":"374_CR7","unstructured":"Russell, P., Jinyang, L.: Piccolo: building fast, distributed programs with partitioned tables. In: Proceedings of the 9th USENIX Conference on Operating Systems Design and Implementation, USENIX Association (2010)"},{"key":"374_CR8","unstructured":"Matei, Z., et al.: Spark: cluster computing with working sets. In: Proceedings of the 2nd USENIX Conference on hot Topics in Cloud Computing, USENIX Association (2010)"},{"key":"374_CR9","unstructured":"Apache Incubator Giraph. http:\/\/incubator.apache.org\/giraph\/"},{"key":"374_CR10","volume-title":"The PageRank citation ranking: bringing order to the Web","author":"L Page","year":"1999","unstructured":"Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank citation ranking: bringing order to the Web. Technical Report, Stanford InfoLab (1999)"},{"issue":"2","key":"374_CR11","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1002\/net.3230140208","volume":"14","author":"D Narsingh","year":"1984","unstructured":"Narsingh, D., Chi-Yin, P.: Shortest-path algorithms: taxonomy and annotation. Networks 14(2), 275\u2013323 (1984)","journal-title":"Networks"},{"issue":"8","key":"374_CR12","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"key":"374_CR13","unstructured":"Sandeep, K.: A distributed algorithm for k-way graph partitioning. In: Proceedings of 25th Conference on EUROMICRO 2. IEEE (1999)"},{"issue":"1","key":"374_CR14","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1080\/10586458.2001.10504428","volume":"10","author":"A William","year":"2001","unstructured":"William, A., Fan, C., Linyuan, L.: A random graph model for power law graphs. Exp. Math. 10(1), 53\u201366 (2001)","journal-title":"Exp. Math."},{"key":"374_CR15","unstructured":"Rishan, C., et al.: Improving large graph processing on partitioned graphs in the cloud. In: Proceedings of the Third ACM Symposium on Cloud Computing. ACM (2012)"},{"key":"374_CR16","unstructured":"Isabelle, S., Gabriel, K.: Streaming graph partitioning for large distributed graphs. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM (2012)"},{"key":"374_CR17","volume-title":"Drawing Power Law Graphs. Graph Drawing","author":"A Reid","year":"2005","unstructured":"Reid, A., Fan, C., Lincoln, L.: Drawing Power Law Graphs. Graph Drawing. Springer, Berlin\/Heidelberg (2005)"},{"key":"374_CR18","first-page":"177","volume-title":"Spectra of Graphs","author":"BE Andries","year":"2012","unstructured":"Andries, B.E., Willem, H.H.: Distance-Regular Graphs. In: Brouwer, A.E., Haemers, W.H. (eds.) Spectra of Graphs, pp. 177\u2013185. Springer, New York (2012)"},{"key":"374_CR19","unstructured":"Richard, K.E., Peter, S.: Large-scale parallel breadth-first search. In: Proceedings of the National Conference on Artificial Intelligence. 20.3. AAAI Press, MIT Press: Menlo Park, Cambridge, London (1999) (2005)"},{"issue":"1","key":"374_CR20","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/0196-6774(90)90029-E","volume":"11","author":"MD Brendan","year":"1990","unstructured":"Brendan, M.D., Nicholas, C.W.: Uniform generation of random regular graphs of moderate degree. J. Algorithm 11(1), 52\u201367 (1990)","journal-title":"J. Algorithm"},{"key":"374_CR21","unstructured":"Hmetis. http:\/\/glaros.dtc.umn.edu\/gkhome\/metis\/hmetis\/"},{"key":"374_CR22","unstructured":"parMetis. http:\/\/glaros.dtc.umn.edu\/gkhome\/metis\/parmetis\/overview"},{"key":"374_CR23","volume-title":"Scotch: A Software Package for Static Mapping by Dual Recursive Partitioning of Process and Architecture Graphs. High-Performance Computing and Networking","author":"P Fran\u00e7ois","year":"1996","unstructured":"Fran\u00e7ois, P., Jean, R.: Scotch: A Software Package for Static Mapping by Dual Recursive Partitioning of Process and Architecture Graphs. High-Performance Computing and Networking. Springer, Berlin\/Heidelberg (1996)"},{"issue":"1","key":"374_CR24","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"D Jeffrey","year":"2008","unstructured":"Jeffrey, D., Sanjay, G.: MapReduce: simplified data processing on large clusters. Commun. ACM 51(1), 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"key":"374_CR25","unstructured":"Hung-chih, Y., et al.: Map-reduce-merge: simplified relational data processing on large clusters. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of data. ACM (2007)"},{"key":"374_CR26","unstructured":"Apache Hadoop. http:\/\/hadoop.apache.org\/"},{"key":"374_CR27","unstructured":"Apache Hama. http:\/\/hama.apache.org\/"},{"key":"374_CR28","unstructured":"GoldenOrb. http:\/\/goldenorbos.org\/"},{"key":"374_CR29","unstructured":"JPregel. http:\/\/kowshik.github.com\/JPregel\/"},{"key":"374_CR30","doi-asserted-by":"crossref","unstructured":"Salihoglu, S., Widom, J.: GPS: a graph processing system. In: Szalay, A., Budavari, T., Balazinska, M., Meliou, A., Sacan, A. (eds.) Proceedings of the 25th International Conference on Scientific and Statistical Database Management (SSDBM). ACM, New York, NY (2013). doi: 10.1145\/2484838.2484843","DOI":"10.1145\/2484838.2484843"},{"key":"374_CR31","unstructured":"Zhenyu, G., et al.: g2: A graph processing system for diagnosing distributed sytems. In: Proceedings of the 2011USENIX Annual Technical Conference, USENIXATC (2011)"},{"key":"374_CR32","doi-asserted-by":"crossref","unstructured":"Kyungho, J., et al.: Large graph processing based on remote memory system. In: 12th IEEE International Conference on High Performance Computing and Communications (HPCC). IEEE (2010)","DOI":"10.1109\/HPCC.2010.88"},{"key":"374_CR33","unstructured":"Jian, L., et al.: Cost-conscious scheduling for large graph processing in the cloud. In: IEEE 13th International Conference on High Performance Computing and Communications (HPCC). IEEE (2011)"},{"key":"374_CR34","unstructured":"Ulrich, M.: External memory BFS on undirected graphs with bounded degree. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics (2001)"},{"key":"374_CR35","volume-title":"External-Memory Breadth First Search with Sublinear I\/O. Algorithms-ESA 2002","author":"M Kurt","year":"2002","unstructured":"Kurt, M., Ulrich, M.: External-Memory Breadth First Search with Sublinear I\/O. Algorithms-ESA 2002. Springer, Berlin, Heidelberg (2002)"},{"key":"374_CR36","unstructured":"Yinglong, X., Viktor K.P.: Topologically adaptive parallel-first search on multicore processors. In: Proceedings of the 21st IASTED International Conference, vol. 668(77) (2009)"},{"key":"374_CR37","unstructured":"Deepak, A.: Design, implementation and experimental study of external memory BFS algorithms. Master thesis. Max-Planck-Institute f\u00fcr Informatik, Saarbr\u00fccken, Germany (2005)"},{"key":"374_CR38","unstructured":"Deepak, A., et al.: Improved external memory BFS implementation. In: Proceedings of the Workshop on Algorithm Engineering and Experiments (2007)"},{"key":"374_CR39","unstructured":"Zhou, R., Hansen, E.A: Breadth-first heuristic search. In Proceedings of the 14th International Conference on Automated Planning and Scheduling ICAPS, pp. 92\u2013100 (2004)"},{"key":"374_CR40","unstructured":"Zhou, R., Hansen, E.A: A breadth-first approach to memory-efficient graph search. In: Proceedings of the National Conference on Artificial Intelligence, vol. 21(2) (2006)"},{"key":"374_CR41","unstructured":"Todd, G., Saad, Y.: Heuristic algorithms for automation graph partitioning. University of Minnesota Supercomputer Institute, Minneapolis, MN 55415, pp. 94\u201329 (1994)"},{"issue":"2","key":"374_CR42","first-page":"215","volume":"29","author":"I Sahar","year":"2009","unstructured":"Sahar, I., Wael, E.: Computing breadth first search in large graph using hmetis partitioning. Eur. J. Sci. Res. 29(2), 215\u2013221 (2009)","journal-title":"Eur. J. Sci. Res."},{"key":"374_CR43","doi-asserted-by":"crossref","unstructured":"Shang, H., Kitsuregawa, M.: Efficient breadth-first search on large graphs with skewed degree distributions. In: Proceedings of the 16th International Conference on Extending Database Technology (EDBT \u201913), pp. 311\u2013322. ACM, New York, NY (2013). doi: 10.1145\/2452376.2452413","DOI":"10.1145\/2452376.2452413"},{"key":"374_CR44","unstructured":"Scott, B., et al.: Direction-optimizing breadth first search. In: International Conference for High Performance Computing, Networking, Storage and Analysis (SC). IEEE (2012)"},{"key":"374_CR45","unstructured":"David, A.B., et al.: Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2. Parallel processing, 2006, ICPP 2006. In: International Conference on IEEE (2006)"},{"key":"374_CR46","unstructured":"Aydin, B., Kamesh, M.: Parallel breadth-first search on distributed memory systems. In: Proceedings of 2011 International Conference for High performance Computing. Networking, Storage and Analysis. ACM (2011)"},{"key":"374_CR47","unstructured":"Shengqi, Y., et al.: Towards effective partition management for large graphs. In: Proceedings of the 2012 International Conference on Management of Data. ACM (2012)"},{"key":"374_CR48","doi-asserted-by":"crossref","unstructured":"Josep, M.P., et al.: The little engine (s) that could: scaling online social networks. ACM SIGCOMM Computer Communication Review, vol. 40(4) ACM (2010)","DOI":"10.1145\/1851275.1851227"},{"key":"374_CR49","unstructured":"Edmond, C., Keith, H., Andy, Y.: Distributed Breadth-First Search with 2-D Partitioning. LLNL, Technical Report. UCRL-CONF-210829 (2005)"},{"key":"374_CR50","volume-title":"Graph Partitioning for Efficient BFS in Shared-Nothing Parallel Systems. Web-Age Information Management","author":"M Victor","year":"2010","unstructured":"Victor, M., et al.: Graph Partitioning for Efficient BFS in Shared-Nothing Parallel Systems. Web-Age Information Management. Springer, Berlin Heidelberg (2010)"},{"key":"374_CR51","doi-asserted-by":"crossref","unstructured":"Buntinas, D., Mercier, G., Gropp, W.: Design and evaluation of nemesis, a scalable, low-latency, message-passing communication subsystem. In: Proceedings of the International Symposium on Cluster Computing and the Grid (2006)","DOI":"10.1109\/CCGRID.2006.31"},{"key":"374_CR52","doi-asserted-by":"crossref","unstructured":"Chai, L., Gao, Q., Panda, D.K.: Understanding the Impact of Multi-Core Architecture in Cluster Computing: A Case Study with Intel Dual-Core System, Cluster Computing and the Grid, 2007. Seventh IEEE International Symposium on CCGRID 2007. IEEE (2007)","DOI":"10.1109\/CCGRID.2007.119"},{"issue":"2","key":"374_CR53","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1109\/MC.2008.65","volume":"41","author":"T El-Ghazawi","year":"2008","unstructured":"El-Ghazawi, T., et al.: The promise of high-performance reconfigurable computing. IEEE Comput. 41(2), 69\u201376 (2008)","journal-title":"IEEE Comput."},{"key":"374_CR54","unstructured":"Powerlaw graph. http:\/\/www.sommer.jp\/graphs\/"},{"issue":"11","key":"374_CR55","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1002\/(SICI)1097-0258(19990615)18:11<1387::AID-SIM126>3.0.CO;2-V","volume":"18","author":"B Rosner","year":"1999","unstructured":"Rosner, B., Grove, D.: Use of the Mann\u2013Whitney $$U$$ U test for clustered data. Stat. Med. 18(11), 1387\u20131400 (1999)","journal-title":"Stat. Med."},{"issue":"11","key":"374_CR56","first-page":"73","volume":"6","author":"M \u017divorad","year":"2011","unstructured":"\u017divorad, M.: Application of Mann\u2013Whitney $$U$$ U test in research of professional training of primary school teachers. Metodi\u010dki Obzori 6(11), 73\u201379 (2011)","journal-title":"Metodi\u010dki Obzori"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-015-0374-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10766-015-0374-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-015-0374-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T13:34:16Z","timestamp":1691847256000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10766-015-0374-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,25]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["374"],"URL":"https:\/\/doi.org\/10.1007\/s10766-015-0374-5","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,25]]}}}