{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:36:26Z","timestamp":1783035386151,"version":"3.54.6"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p>\n            Graph analytics on social networks, Web data, and communication networks has been widely used in a plethora of applications. Many graph analytics algorithms are based on breadth-first search (BFS) graph traversal, which is not only time-consuming for large datasets but also involves much redundant computation when executed multiple times from different start vertices. In this paper, we propose\n            <jats:italic>Multi-Source BFS<\/jats:italic>\n            (MS-BFS), an algorithm that is designed to run multiple concurrent BFSs over the same graph on a single CPU core while scaling up as the number of cores increases. MS-BFS leverages the properties of\n            <jats:italic>small-world networks<\/jats:italic>\n            , which apply to many real-world graphs, and enables efficient graph traversal that: (i) shares common computation across concurrent BFSs; (ii) greatly reduces the number of random memory accesses; and (iii) does not incur synchronization costs. We demonstrate how a real graph analytics application---all-vertices closeness centrality---can be efficiently solved with MS-BFS. Furthermore, we present an extensive experimental evaluation with both synthetic and real datasets, including Twitter and Wikipedia, showing that MS-BFS provides almost linear scalability with respect to the number of cores and excellent scalability for increasing graph sizes, outperforming state-of-the-art BFS algorithms by more than one order of magnitude when running a large number of BFSs.\n          <\/jats:p>","DOI":"10.14778\/2735496.2735507","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"449-460","source":"Crossref","is-referenced-by-count":71,"title":["The more the merrier"],"prefix":"10.14778","volume":"8","author":[{"given":"Manuel","family":"Then","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moritz","family":"Kaufmann","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fernando","family":"Chirigati","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tuan-Anh","family":"Hoang-Vu","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kien","family":"Pham","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alfons","family":"Kemper","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Neumann","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huy T.","family":"Vo","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Graph 500 Benchmark 2014. http:\/\/www.graph500.org\/.  Graph 500 Benchmark 2014. http:\/\/www.graph500.org\/."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2010.46"},{"issue":"21","key":"e_1_2_1_3_1","first-page":"11149","volume":"97","author":"Amaral L. A. N.","year":"2000","journal-title":"Classes of Small-World Networks. PNAS"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380718.2380723"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2006.34"},{"key":"e_1_2_1_6_1","first-page":"1","volume-title":"Small-world Network Analysis and Partitioning: An Open-source Parallel Graph Framework for the Exploration of Large-scale Networks. In IPDPS","author":"Bader D. A.","year":"2008"},{"key":"e_1_2_1_7_1","first-page":"1","volume-title":"Direction-Optimizing Breadth-First Search. In SC '12","author":"Beamer S.","year":"2012"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2513591.2527070"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063384.2063471"},{"key":"e_1_2_1_11_1","first-page":"1","volume-title":"Breaking the Speed and Scalability Barriers for Graph Exploration on Distributed-Memory Machines. In SC '12","author":"Checconi F.","year":"2012"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350247"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592101"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2012.43"},{"key":"e_1_2_1_15_1","unstructured":"Faunus -- Graph Analytics Engine 2014. http:\/\/thinkaurelius.github.io\/faunus\/.  Faunus -- Graph Analytics Engine 2014. http:\/\/thinkaurelius.github.io\/faunus\/."},{"key":"e_1_2_1_16_1","volume-title":"POOSC","author":"Gregor D.","year":"2005"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488433"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.14"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767867"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12599-010-0127-3"},{"key":"e_1_2_1_21_1","unstructured":"LDBC Social Network Data Generator 2014. https:\/\/github.com\/ldbc\/ldbc_snb_datagen.  LDBC Social Network Data Generator 2014. https:\/\/github.com\/ldbc\/ldbc_snb_datagen."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.224"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626407002843"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_26_1","unstructured":"Neo4j 2014. http:\/\/neo4j.com\/.  Neo4j 2014. http:\/\/neo4j.com\/."},{"key":"e_1_2_1_27_1","first-page":"196","volume-title":"Hwang. Efficient Top-K Closeness Centrality Search. In ICDE '14","author":"Olsen P.","year":"2014"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593661"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2169090.2169092"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.70"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467799"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733013"},{"key":"e_1_2_1_33_1","unstructured":"Titan -- Distributed Graph Database 2014. http:\/\/thinkaurelius.github.io\/titan\/.  Titan -- Distributed Graph Database 2014. http:\/\/thinkaurelius.github.io\/titan\/."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2735496.2735507","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:31:18Z","timestamp":1672219878000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2735496.2735507"}},"subtitle":["efficient multi-source graph traversal"],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.14778\/2735496.2735507"],"URL":"https:\/\/doi.org\/10.14778\/2735496.2735507","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}