{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T00:59:17Z","timestamp":1742950757800,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030050504"},{"type":"electronic","value":"9783030050511"}],"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_24","type":"book-chapter","created":{"date-parts":[[2018,12,6]],"date-time":"2018-12-06T16:38:48Z","timestamp":1544114328000},"page":"337-357","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Asynchronous Parallel Dijkstra\u2019s Algorithm on Intel Xeon Phi Processor"],"prefix":"10.1007","author":[{"given":"Weidong","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yifeng","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,7]]},"reference":[{"issue":"2","key":"24_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"U Brandes","year":"2010","unstructured":"Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163\u2013177 (2010)","journal-title":"J. Math. Sociol."},{"issue":"1","key":"24_CR2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2307\/3033543","volume":"40","author":"LC Freeman","year":"1977","unstructured":"Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 40(1), 35\u201341 (1977)","journal-title":"Sociometry"},{"issue":"22","key":"24_CR3","doi-asserted-by":"publisher","first-page":"7794","DOI":"10.1073\/pnas.0407994102","volume":"102","author":"R Guimer\u00e1","year":"2005","unstructured":"Guimer\u00e1, R., Mossa, S., Turtschi, A., Amaral, L.A.N.: The worldwide air transportation network: anomalous centrality, community structure, and cities\u2019 global roles. Proc. Natl. Acad. Sci. U.S.A. 102(22), 7794\u20137799 (2005)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"issue":"6833","key":"24_CR4","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1038\/35075138","volume":"411","author":"H Jeong","year":"2001","unstructured":"Jeong, H., Mason, S.P., Barab\u00e1si, A.L., Oltvai, Z.N.: Lethality and centrality in protein networks. Nature 411(6833), 41\u201342 (2001)","journal-title":"Nature"},{"issue":"3","key":"24_CR5","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1145\/321765.321768","volume":"20","author":"DB Johnson","year":"1973","unstructured":"Johnson, D.B.: A note on Dijkstra\u2019s shortest path algorithm. J. ACM 20(3), 385\u2013388 (1973)","journal-title":"J. ACM"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-19487-8_1","volume-title":"SWAT 88","author":"S Carlsson","year":"1988","unstructured":"Carlsson, S., Munro, J.I., Poblete, P.V.: An implicit binomial queue with constant insertion time. In: Karlsson, R., Lingas, A. (eds.) SWAT 1988. LNCS, vol. 318, pp. 1\u201313. Springer, Heidelberg (1988). \n                      https:\/\/doi.org\/10.1007\/3-540-19487-8_1"},{"issue":"3","key":"24_CR7","first-page":"338","volume":"34","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 338\u2013346 (1984)","journal-title":"J. ACM"},{"key":"24_CR8","unstructured":"yuhc: Pregel and shortest path algorithm in graphx (2015). \n                      http:\/\/note.yuhc.me\/2015\/03\/graphx-pregel-shortest-path\/"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Srinivasan, T., Balakrishnan, R., Gangadharan, S.A., Hayawardh, V.: A scalable parallelization of all-pairs shortest path algorithm for a high performance cluster environment. In: International Conference on Parallel and Distributed Systems, pp. 1\u20138 (2007)","DOI":"10.1109\/ICPADS.2007.4447721"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Madduri, K., Bader, D.A., Berry, J.W., Crobak, J.R.: Parallel shortest path algorithms for solving large-scale instances. In: Dimacs Implementation Challenge - The Shortest Path Problem, vol. 74, pp. 249\u2013290 (2011)","DOI":"10.1090\/dimacs\/074\/10"},{"key":"24_CR11","unstructured":"Intel xeon phi core micro-architecture (2016). \n                      https:\/\/software.intel.com\/en-us\/articles\/intel-xeon-phi-core-micro-architecture"},{"issue":"5","key":"24_CR12","doi-asserted-by":"publisher","first-page":"1637","DOI":"10.1137\/070698774","volume":"37","author":"AV Goldberg","year":"2008","unstructured":"Goldberg, A.V.: A practical shortest path algorithm with linear expected time. Siam J. Comput. 37(5), 1637\u20131655 (2008)","journal-title":"Siam J. Comput."},{"issue":"1","key":"24_CR13","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1287\/opre.27.1.161","volume":"27","author":"EV Denardo","year":"1979","unstructured":"Denardo, E.V., Fox, B.L.: Shortest-route methods: 1. reaching, pruning, and buckets. Oper. Res. 27(1), 161\u2013186 (1979)","journal-title":"Oper. Res."},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Zhu, A.D., Ma, H., Xiao, X., Luo, S., Tang, Y., Zhou, S.: Shortest path and distance queries on road networks: towards bridging theory and practice. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 857\u2013868 (2013)","DOI":"10.1145\/2463676.2465277"},{"key":"24_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/11427186_18","volume-title":"Experimental and Efficient Algorithms","author":"RH M\u00f6hring","year":"2005","unstructured":"M\u00f6hring, R.H., Schilling, H., Sch\u00fctz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speed up Dijkstra\u2019s algorithm. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 189\u2013202. Springer, Heidelberg (2005). \n                      https:\/\/doi.org\/10.1007\/11427186_18"},{"key":"24_CR16","volume-title":"kd-tree","author":"FP Miller","year":"2009","unstructured":"Miller, F.P., Vandome, A.F., Mcbrewster, J.: kd-tree. Alpha Press, Orlando (2009)"},{"key":"24_CR17","unstructured":"Karypis, G., Kumar, V.: METIS: a software package for partitioning unstructured graphs. In: International Cryogenics Monograph, pp. 121\u2013124 (1998)"},{"key":"24_CR18","unstructured":"9th DIMACS implementation challenge - shortest paths (2012). \n                      http:\/\/www.dis.uniroma1.it\/challenge9\/"},{"key":"24_CR19","unstructured":"Moore, E.F.: The shortest path through a maze. In: Proceedings of the International Symposium on the Theory of Switching, pp. 285\u2013292 (1959)"},{"key":"24_CR20","unstructured":"Berteskas, D., Gallagre, R.: Distributed asynchronous Bellman-ford algorithm. In: Data Networks (1987)"},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Cheng, C., Riley, R., Kumar, S.P.R., Garcialunaaceves, J.J.: A loop-free extended bellman-ford routing protocol without bouncing effect. In: Symposium Proceedings on Communications Architectures and Protocols, pp. 224\u2013236 (1989)","DOI":"10.1145\/75246.75269"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Chroboczek, J.: The Babel Routing Protocol. Heise Zeitschriften Verlag (2011)","DOI":"10.17487\/rfc6126"},{"issue":"8","key":"24_CR23","doi-asserted-by":"publisher","first-page":"2515","DOI":"10.1109\/26.310604","volume":"42","author":"B Awerbuch","year":"1994","unstructured":"Awerbuch, B., Bar-Noy, A., Gopal, M.: Approximate distributed bellman-ford algorithms. IEEE Trans. Commun. 42(8), 2515\u20132517 (1994)","journal-title":"IEEE Trans. Commun."},{"key":"24_CR24","unstructured":"Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Thirteenth ACM-SIAM Symposium on Discrete Algorithms (2002)"},{"key":"24_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/3-540-68530-8_33","volume-title":"Algorithms \u2014 ESA 1998","author":"U Meyer","year":"1998","unstructured":"Meyer, U., Sanders, P.: delta-stepping : a parallel single source shortest path algorithm. In: Bilardi, G., Italiano, G.F., Pietracaprina, A., Pucci, G. (eds.) ESA 1998. LNCS, vol. 1461, pp. 393\u2013404. Springer, Heidelberg (1998). \n                      https:\/\/doi.org\/10.1007\/3-540-68530-8_33"},{"key":"24_CR26","unstructured":"Micikevicius, P.: General parallel computation on commodity graphics hardware: case study with the all-pairs shortest paths problem. In: International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2004 21\u201324 June 2004, Las Vegas, Nevada, USA, pp. 1359\u20131365 (2004)"},{"key":"24_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-540-77220-0_21","volume-title":"High Performance Computing \u2013 HiPC 2007","author":"P Harish","year":"2007","unstructured":"Harish, P., Narayanan, P.J.: Accelerating Large graph algorithms on the GPU using CUDA. In: Aluru, S., Parashar, M., Badrinath, R., Prasanna, V.K. (eds.) HiPC 2007. LNCS, vol. 4873, pp. 197\u2013208. Springer, Heidelberg (2007). \n                      https:\/\/doi.org\/10.1007\/978-3-540-77220-0_21"},{"key":"24_CR28","unstructured":"Kranj\u010devi\u010d, M., Palossi, D., Pintarelli, S.: Parallel delta-stepping algorithm for shared memory architectures (2016)"},{"issue":"7","key":"24_CR29","doi-asserted-by":"publisher","first-page":"940","DOI":"10.1016\/j.jpdc.2012.02.007","volume":"73","author":"D Delling","year":"2013","unstructured":"Delling, D., Goldberg, A.V., Nowatzyk, A., Werneck, R.F.: PHAST: hardware-accelerated shortest path trees. J. Parallel Distrib. Comput. 73(7), 940\u2013952 (2013)","journal-title":"J. Parallel Distrib. Comput."},{"key":"24_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-540-68552-4_24","volume-title":"Experimental Algorithms","author":"R Geisberger","year":"2008","unstructured":"Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 319\u2013333. Springer, Heidelberg (2008). \n                      https:\/\/doi.org\/10.1007\/978-3-540-68552-4_24"},{"key":"24_CR31","unstructured":"Intel xeon phi processor 7210 (2016). \n                      https:\/\/ark.intel.com\/products\/94033\/Intel-Xeon-Phi-Processor-7210-16GB-1_30-GHz-64-core"},{"key":"24_CR32","unstructured":"Intel xeon phi x100 family coprocessor - the architecture, 12 November 2012. \n                      https:\/\/software.intel.com\/en-us\/articles\/intel-xeon-phi-coprocessor-codename-knights-corner"},{"issue":"2","key":"24_CR33","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.jda.2009.03.001","volume":"8","author":"JB Orlin","year":"2010","unstructured":"Orlin, J.B., Madduri, K., Subramani, K., Williamson, M.: A faster algorithm for the single source shortest path problem with few distinct positive lengths. J. Discrete Algorithms 8(2), 189\u2013198 (2010)","journal-title":"J. Discrete Algorithms"},{"issue":"5","key":"24_CR34","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1007\/s10766-015-0351-z","volume":"43","author":"H Ortega-Arranz","year":"2015","unstructured":"Ortega-Arranz, H., Torres, Y., Gonzalez-Escribano, A., Llanos, D.R.: Comprehensive evaluation of a new GPU-based approach to the shortest path problem. Int. J. Parallel Prog. 43(5), 918\u2013938 (2015)","journal-title":"Int. J. Parallel Prog."},{"issue":"2","key":"24_CR35","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1016\/j.ejor.2014.04.028","volume":"238","author":"A Sede\u00f1o-Noda","year":"2014","unstructured":"Sede\u00f1o-Noda, A., Gonz\u00e1lez-Barrera, J.D.: Fast and fine quickest path algorithm. Eur. J. Oper. Res. 238(2), 596\u2013606 (2014)","journal-title":"Eur. J. Oper. Res."}],"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_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T05:19:48Z","timestamp":1558329588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-05051-1_24"}},"subtitle":["How to Accelerate Irregular Memory Access Algorithm"],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030050504","9783030050511"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-05051-1_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"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"}}]}}