{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T10:51:59Z","timestamp":1775299919124,"version":"3.50.1"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030050504","type":"print"},{"value":"9783030050511","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-05051-1_8","type":"book-chapter","created":{"date-parts":[[2018,12,6]],"date-time":"2018-12-06T16:38:48Z","timestamp":1544114328000},"page":"106-121","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["PruX: Communication Pruning of Parallel BFS in the Graph 500 Benchmark"],"prefix":"10.1007","author":[{"given":"Menghan","family":"Jia","sequence":"first","affiliation":[]},{"given":"Yiming","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Dongsheng","family":"Li","sequence":"additional","affiliation":[]},{"given":"Songzhu","family":"Mei","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,12,7]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Agarwal, V., Petrini, F., Pasetto, D., Bader, D.A.: Scalable graph exploration on multicore processors. In: High Performance Computing, Networking, Storage and Analysis, pp. 1\u201311 (2010)","DOI":"10.1109\/SC.2010.46"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Ajwani, D., Meyer, U., Osipov, V.:. Improved external memory BFS implementation. In: The Workshop on Algorithm Engineering & Experiments (2007)","DOI":"10.1137\/1.9781611972870.1"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Akkary, H., Driscoll, M.A.: A dynamic multithreading processor. In: 1998 Proceedings of ACM\/IEEE International Symposium on Microarchitecture, Micro-31, pp. 226\u2013236 (1998)","DOI":"10.1109\/MICRO.1998.742784"},{"issue":"3","key":"8_CR4","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1109\/TIT.1987.1057314","volume":"33","author":"B Awerbuch","year":"2003","unstructured":"Awerbuch, B., Gallager, R.: A new distributed algorithm to find breadth first search trees. IEEE Trans. Inf. Theory 33(3), 315\u2013322 (2003)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Bader, D.A., Madduri, K.: Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2, vol. 34, no. 2, pp. 523\u2013530 (2006)","DOI":"10.1109\/ICPP.2006.34"},{"key":"8_CR6","doi-asserted-by":"crossref","unstructured":"Beamer, S., Patterson, D.: Direction-optimizing breadth-first search. In: International Conference on High Performance Computing, Networking, Storage and Analysis, p. 12 (2012)","DOI":"10.1109\/SC.2012.50"},{"issue":"3","key":"8_CR7","first-page":"351","volume":"60","author":"SM Bidstrup","year":"1988","unstructured":"Bidstrup, S.M., Grady, C.P.L.: SSSP: simulation of single-sludge processes. Journal 60(3), 351\u2013361 (1988)","journal-title":"Journal"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Bulu, A.: Parallel breadth-first search on distributed memory systems, pp. 1\u201312 (2011)","DOI":"10.1145\/2063384.2063471"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Checconi, F., Petrini, F.: Traversing trillions of edges in real time: graph exploration on large-scale parallel machines. In: IEEE International Parallel and Distributed Processing Symposium, pp. 425\u2013434 (2014)","DOI":"10.1109\/IPDPS.2014.52"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Chow, E., Henderson, K., Yoo, A.: Distributed breadth-first search with 2-D partitioning. Lawrence Livermore National Laboratory (2005)","DOI":"10.2172\/919217"},{"key":"8_CR11","first-page":"165","volume":"8","author":"J Dongarra","year":"1994","unstructured":"Dongarra, J., et al.: Special issue - MPI - a message passing interface standard. Int. J. Supercomput. Appl. High Perform. Comput. 8, 165 (1994)","journal-title":"Int. J. Supercomput. Appl. High Perform. Comput."},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Duran, A., Klemm, M.: The Intel\u00ae many integrated core architecture. In: International Conference on High Performance Computing and Simulation, pp. 365\u2013366 (2012)","DOI":"10.1109\/HPCSim.2012.6266938"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Greathouse, J.L., Daga, M.: Efficient sparse matrix-vector multiplication on GPUs using the CSR storage format. In: High Performance Computing, Networking, Storage, pp. 769\u2013780 (2015)","DOI":"10.1109\/SC.2014.68"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Jose, J., Potluri, S., Tomko, K., Panda, D.K.: Designing scalable graph500 benchmark with hybrid MPI+ OpenSHMEM programming models (2013)","DOI":"10.1007\/978-3-642-38750-0_9"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Leiserson, C.E., Schardl, T.B.: A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers). In: SPAA 2010: Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures, Thira, Santorini, Greece, June, pp. 303\u2013314 (2010)","DOI":"10.1145\/1810479.1810534"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Lu, H., Tan, G., Chen, M., Sun, N.: Reducing communication in parallel breadth-first search on distributed memory systems, pp. 1261\u20131268 (2015)","DOI":"10.1109\/CSE.2014.243"},{"issue":"01","key":"8_CR17","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1142\/S0129626407002843","volume":"17","author":"A Lumsdaine","year":"2007","unstructured":"Lumsdaine, A., Gregor, D., Hendrickson, B., Berry, J.: Challenges in parallel graph processing. Parallel Process. Lett. 17(01), 5\u201320 (2007)","journal-title":"Parallel Process. Lett."},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Luo, L., Wong, M., Hwu, W.M.: An effective GPU implementation of breadth-first search. In: Design Automation Conference, pp. 52\u201355 (2010)","DOI":"10.1145\/1837274.1837289"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Malewicz, G., et al.: Pregel: a system for large-scale graph processing. In: ACM SIGMOD International Conference on Management of Data, pp. 135\u2013146 (2010)","DOI":"10.1145\/1807167.1807184"},{"key":"8_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/978-3-319-27308-2_20","volume-title":"Euro-Par 2015: Parallel Processing Workshops","author":"S Sallinen","year":"2015","unstructured":"Sallinen, S., Gharaibeh, A., Ripeanu, M.: Accelerating direction-optimized breadth first search on hybrid architectures. In: Hunold, S., et al. (eds.) Euro-Par 2015. LNCS, vol. 9523, pp. 233\u2013245. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-27308-2_20"},{"key":"8_CR21","unstructured":"Snir, M.: MPI : The Complete Reference, pp. 4038\u20134040 (2010)"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Su, B.Y., Brutch, T.G., Keutzer, K.: Parallel BFS graph traversal on images using structured grid, pp. 4489\u20134492 (2010)","DOI":"10.1109\/ICIP.2010.5652307"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Yoo, A., Chow, E., Henderson, K., Mclendon, W., Hendrickson, B., Catalyurek, U.: A scalable distributed parallel breadth-first search algorithm on BlueGene\/L. In: Proceedings of the ACM\/IEEE SC 2005 Conference on Supercomputing, p. 25 (2005)","DOI":"10.1109\/SC.2005.4"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Architectures for Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-05051-1_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T09:52:47Z","timestamp":1775296367000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-05051-1_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030050504","9783030050511"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-05051-1_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"7 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICA3PP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Architectures for Parallel Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guangzhou","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 November 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 November 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ica3pp2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/nsclab.org\/ica3pp2018\/authors.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"407","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"141","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"50","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"35% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"2.3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"7.3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}