{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T23:10:48Z","timestamp":1760051448691,"version":"build-2065373602"},"reference-count":36,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2018,10,1]],"date-time":"2018-10-01T00:00:00Z","timestamp":1538352000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2018,10,1]],"date-time":"2018-10-01T00:00:00Z","timestamp":1538352000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61672315"],"award-info":[{"award-number":["61672315"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Grand Fundamental Research 973 Program of China","award":["2014CB340402"],"award-info":[{"award-number":["2014CB340402"]}]},{"name":"the Beijing Municipal Science and Technology Commission of China","award":["D151100000815003"],"award-info":[{"award-number":["D151100000815003"]}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Parallel and Distributed Computing"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1016\/j.jpdc.2017.09.007","type":"journal-article","created":{"date-parts":[[2017,10,12]],"date-time":"2017-10-12T03:15:45Z","timestamp":1507778145000},"page":"383-394","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":9,"special_numbering":"C","title":["Accelerating breadth-first graph search on a single server by dynamic edge trimming"],"prefix":"10.1016","volume":"120","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3480-5902","authenticated-orcid":false,"given":"Guangyan","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Shuhan","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"Jiwu","family":"Shu","sequence":"additional","affiliation":[]},{"given":"Qingda","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Weimin","family":"Zheng","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.jpdc.2017.09.007_b1","series-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm","first-page":"601","article-title":"A computational study of external-memory BFS algorithms","author":"Ajwani","year":"2006"},{"key":"10.1016\/j.jpdc.2017.09.007_b2","doi-asserted-by":"crossref","unstructured":"S. Beamer, K. Asanovi C, D. Patterson, Direction-optimizing breadth-first Search, in: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC\u201912, pp. 12:1\u201312:10, 2012.","DOI":"10.1109\/SC.2012.50"},{"year":"2015","series-title":"Benchmarking X-Stream and Graphchi","author":"Bindschaedler","key":"10.1016\/j.jpdc.2017.09.007_b3"},{"key":"10.1016\/j.jpdc.2017.09.007_b4","series-title":"Proceedings of the 20th International Conference on World Wide Web","first-page":"587","article-title":"Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks","author":"Boldi","year":"2011"},{"key":"10.1016\/j.jpdc.2017.09.007_b5","series-title":"Proc. of the Thirteenth International World Wide Web Conference","first-page":"595","article-title":"The WebGraph Framework I: compression techniques","author":"Boldi","year":"2004"},{"key":"10.1016\/j.jpdc.2017.09.007_b6","doi-asserted-by":"crossref","unstructured":"S. Cheng, G. Zhang, J. Shu, Q. Hu, W. Zheng, FastBFS: fast breadth-first graph search on a single server in: 2016 IEEE International Parallel and Distributed Processing Symposium, IPDPS\u201916, 2016, pp. 303\u2013312 http:\/\/dx.doi.org\/10.1109\/IPDPS.2016.71.","DOI":"10.1109\/IPDPS.2016.71"},{"key":"10.1016\/j.jpdc.2017.09.007_b7","doi-asserted-by":"crossref","unstructured":"J. Chhugani, N. Satish, C. Kim, J. Sewall, P. Dubey, Fast and efficient graph traversal algorithm for CPUs: Maximizing single-node efficiency, in: 2012 IEEE 26th International Parallel and Distributed Processing Symposium, IPDPS\u201912, 2012, pp. 378\u2013389, http:\/\/dx.doi.org\/10.1109\/IPDPS.2012.43.","DOI":"10.1109\/IPDPS.2012.43"},{"key":"10.1016\/j.jpdc.2017.09.007_b8","unstructured":"Friendster social network and ground-truth communities, 2012, URL http:\/\/snap.stanford.edu\/data\/com-Friendster.html."},{"key":"10.1016\/j.jpdc.2017.09.007_b9","unstructured":"J.E. Gonzalez, Y. Low, H. Gu, D. Bickson, C. Guestrin, PowerGraph: distributed graph-parallel computation on natural graphs, in: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI\u201912, 2012, pp. 17\u201330."},{"key":"10.1016\/j.jpdc.2017.09.007_b10","unstructured":"J.E. Gonzalez, R.S. Xin, A. Dave, D. Crankshaw, M.J. Franklin, I. Stoica, GraphX: Graph processing in a distributed dataflow framework, in: Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, OSDI\u201914, 2014, pp. 599\u2013613."},{"key":"10.1016\/j.jpdc.2017.09.007_b11","doi-asserted-by":"crossref","unstructured":"W.-S. Han, S. Lee, K. Park, J.-H. Lee, M.-S. Kim, J. Kim, H. Yu, TurboGraph: a fast parallel graph engine handling billion-scale graphs in a single PC, in: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD\u201913, 2013, pp. 77\u201385.","DOI":"10.1145\/2487575.2487581"},{"key":"10.1016\/j.jpdc.2017.09.007_b12","series-title":"Proceedings of the 23rd International Conference on Parallel Architectures and Compilation","first-page":"517","article-title":"Processing Big Data Graphs on Memory-Restricted Systems","author":"Harshvardhan","year":"2014"},{"key":"10.1016\/j.jpdc.2017.09.007_b13","doi-asserted-by":"crossref","unstructured":"S. Hong, S.K. Kim, T. Oguntebi, K. Olukotun, Accelerating CUDA graph algorithms at maximum warp in: Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, PPoPP\u201911, 2011, pp. 267\u2013276.","DOI":"10.1145\/1941553.1941590"},{"key":"10.1016\/j.jpdc.2017.09.007_b14","doi-asserted-by":"crossref","unstructured":"Z. Khayyat, K. Awara, A. Alonazi, H. Jamjoom, D. Williams, P. Kalnis, Mizan: a system for dynamic load balancing in large-scale graph processing, in: Proceedings of the 8th ACM European Conference on Computer Systems, EuroSys\u201913, 2013, pp. 169\u2013182.","DOI":"10.1145\/2465351.2465369"},{"issue":"3","key":"10.1016\/j.jpdc.2017.09.007_b15","doi-asserted-by":"crossref","first-page":"034008","DOI":"10.1088\/1748-9326\/3\/3\/034008","article-title":"Worldwide electricity used in data centers","volume":"3","author":"Koomey","year":"2008","journal-title":"Environ. Res. Lett."},{"key":"10.1016\/j.jpdc.2017.09.007_b16","doi-asserted-by":"crossref","unstructured":"H. Kwak, C. Lee, H. Park, S. Moon, What is Twitter, a social network or a news media? in: Proceedings of the 19th International Conference on World Wide Web, WWW\u201910, 2010, pp. 591\u2013600.","DOI":"10.1145\/1772690.1772751"},{"key":"10.1016\/j.jpdc.2017.09.007_b17","unstructured":"A. Kyrola, G. Blelloch, C. Guestrin, GraphChi: Large-scale graph computation on just a PC, in: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI\u201912, 2012, pp. 31\u201346."},{"key":"10.1016\/j.jpdc.2017.09.007_b18","doi-asserted-by":"crossref","unstructured":"C.E. Leiserson, T.B. Schardl, A Work-efficient parallel breadth-first search algorithm (or How to cope with the nondeterminism of reducers), in: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA\u201910, 2010, pp. 303\u2013314.","DOI":"10.1145\/1810479.1810534"},{"key":"10.1016\/j.jpdc.2017.09.007_b19","doi-asserted-by":"crossref","unstructured":"Z. Lin, M. Kahng, K.M. Sabrin, D.H.P. Chau, H. Lee, U. Kang, Mmap: fast billion-scale graph computation on a PC via memory mapping, in: Proceedings of the IEEE International Conference on Big Data, BigData\u201914, 2014, pp. 159\u2013164.","DOI":"10.1109\/BigData.2014.7004226"},{"issue":"8","key":"10.1016\/j.jpdc.2017.09.007_b20","doi-asserted-by":"crossref","first-page":"716","DOI":"10.14778\/2212351.2212354","article-title":"Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud","volume":"5","author":"Low","year":"2012","journal-title":"Proc. VLDB Endow."},{"key":"10.1016\/j.jpdc.2017.09.007_b21","doi-asserted-by":"crossref","unstructured":"L. Luo, M. Wong, W.-m. Hwu, An Effective GPU Implementation of Breadth-first Search, in: Proceedings of the 47th Design Automation Conference, DAC\u201910, 2010, pp. 52\u201355.","DOI":"10.1145\/1837274.1837289"},{"key":"10.1016\/j.jpdc.2017.09.007_b22","doi-asserted-by":"crossref","unstructured":"G. Malewicz, M. Austern, A. Bik, J. Dehnert, I. Horn, N. Leiser, C. Grzegorz, Pregel: a system for large-scale graph processing, in: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD\u201910, 2009, pp. 135\u2013146.","DOI":"10.1145\/1807167.1807184"},{"key":"10.1016\/j.jpdc.2017.09.007_b23","doi-asserted-by":"crossref","unstructured":"D. Merrill, M. Garland, A. Grimshaw, Scalable GPU graph traversal, in: Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP\u201912, 2012, pp. 117\u2013128.","DOI":"10.1145\/2145816.2145832"},{"key":"10.1016\/j.jpdc.2017.09.007_b24","unstructured":"R.C. Murphy, K.B. Wheeler, B.W. Barrett, J.A. Ang, Introducing the graph 500 Cray User\u2019s Group (CUG), 2010."},{"key":"10.1016\/j.jpdc.2017.09.007_b25","doi-asserted-by":"crossref","unstructured":"R. Pearce, M. Gokhale, N.M. Amato, Faster parallel traversal of scale free graphs at extreme scale with vertex delegates, in: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC\u201914, 2014, pp. 549\u2013559.","DOI":"10.1109\/SC.2014.50"},{"key":"10.1016\/j.jpdc.2017.09.007_b26","doi-asserted-by":"crossref","unstructured":"A. Roy, I. Mihailovic, W. Zwaenepoel, X-Stream: edge-centric graph processing using streaming partitions, in: Proceedings of the 24th ACM Symposium on Operating Systems Principles, SOSP\u201913, 2013, pp. 472\u2013488.","DOI":"10.1145\/2517349.2522740"},{"key":"10.1016\/j.jpdc.2017.09.007_b27","doi-asserted-by":"crossref","unstructured":"N. Satish, C. Kim, J. Chhugani, P. Dubey, Large-scale energy-efficient graph traversal: A path to efficient data-intensive supercomputing, in: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC\u201912, 2012, pp. 14:1\u201314:11.","DOI":"10.1109\/SC.2012.70"},{"issue":"10","key":"10.1016\/j.jpdc.2017.09.007_b28","doi-asserted-by":"crossref","first-page":"1381","DOI":"10.1109\/TPDS.2007.70811","article-title":"Efficient breadth-first search on the cell\/BE processor","volume":"19","author":"Scarpazza","year":"2008","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"10.1016\/j.jpdc.2017.09.007_b29","doi-asserted-by":"crossref","unstructured":"J. Shun, G.E. Blelloch, Ligra: a lightweight graph processing framework for shared memory, in: Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP\u201913, 2013, pp. 135\u2013146.","DOI":"10.1145\/2442516.2442530"},{"key":"10.1016\/j.jpdc.2017.09.007_b30","unstructured":"The Graph 500 List, 2014 URL http:\/\/www.graph500.org\/."},{"key":"10.1016\/j.jpdc.2017.09.007_b31","series-title":"2016 USENIX Annual Technical Conference","first-page":"507","article-title":"Load the Edges You Need: A Generic I\/O Optimization for Disk-based Graph Processing","author":"Vora","year":"2016"},{"key":"10.1016\/j.jpdc.2017.09.007_b32","doi-asserted-by":"crossref","unstructured":"P. Wang, K. Zhang, R. Chen, H. Chen, H. Guan, Replication-based fault-tolerance for large-scale graph processing, in: Proceedings of the 44th Annual IEEE\/IFIP International Conference on Dependable Systems and Networks, DSN\u201914, 2014, pp. 562\u2013573.","DOI":"10.1109\/DSN.2014.58"},{"key":"10.1016\/j.jpdc.2017.09.007_b33","doi-asserted-by":"crossref","unstructured":"C. Wilson, B. Boe, A. Sala, K.P.N. Puttaswamy, B.Y. Zhao, User Interactions in social networks and their implications, in: Proceedings of the 4th ACM European Conference on Computer Systems, EuroSys\u201909, 2009, pp. 205\u2013218.","DOI":"10.1145\/1519065.1519089"},{"key":"10.1016\/j.jpdc.2017.09.007_b34","doi-asserted-by":"crossref","unstructured":"X. Yan, P.S. Yu, J. Han, Graph Indexing: A Frequent Structure-based Approach, in: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, SIGMOD\u201904, 2004, pp. 335\u2013346.","DOI":"10.1145\/1007568.1007607"},{"key":"10.1016\/j.jpdc.2017.09.007_b35","doi-asserted-by":"crossref","unstructured":"P. Yuan, W. Zhang, C. Xie, H. Jin, L. Liu, K. Lee, Fast Iterative Graph Computation: A Path Centric Approach, in: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC\u201914, 2014, pp. 401\u2013412.","DOI":"10.1109\/SC.2014.38"},{"key":"10.1016\/j.jpdc.2017.09.007_b36","unstructured":"D. Zheng, D. Mhembere, R. Burns, J. Vogelstein, C.E. Priebe, A.S. Szalay, FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs, in: Proceedings of the 13th USENIX Conference on File and Storage Technologies, FAST\u201915, 2015, pp. 45\u201358."}],"container-title":["Journal of Parallel and Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0743731517302617?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0743731517302617?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T22:29:44Z","timestamp":1760048984000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0743731517302617"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":36,"alternative-id":["S0743731517302617"],"URL":"https:\/\/doi.org\/10.1016\/j.jpdc.2017.09.007","relation":{},"ISSN":["0743-7315"],"issn-type":[{"type":"print","value":"0743-7315"}],"subject":[],"published":{"date-parts":[[2018,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Accelerating breadth-first graph search on a single server by dynamic edge trimming","name":"articletitle","label":"Article Title"},{"value":"Journal of Parallel and Distributed Computing","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jpdc.2017.09.007","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2017 Elsevier Inc. All rights reserved.","name":"copyright","label":"Copyright"}]}}