Name
Abstract | ||
|---|---|---|
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 Multi-Source BFS (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 small-world networks, 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.14778/2735496.2735507 | VLDB |
Field | DocType | Volume |
Data mining,Graph database,Synchronization,Graph traversal,Computer science,Theoretical computer science,Graph bandwidth,Multi-core processor,Multi-source,Database,Scalability,Computation | Journal | 8 |
Issue | ISSN | Citations |
4 | 2150-8097 | 20 |
PageRank | References | Authors |
0.79 | 23 | 8 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel Then | 1 | 43 | 4.73 |
| Moritz Kaufmann | 2 | 23 | 2.53 |
| Fernando Seabra Chirigati | 3 | 205 | 16.38 |
| Tuan-Anh Hoang-Vu | 4 | 26 | 1.19 |
| Kien Pham | 5 | 20 | 1.12 |
| Alfons Kemper | 6 | 3519 | 769.50 |
| Thomas Neumann | 7 | 2523 | 156.50 |
| Huy T. Vo | 8 | 1035 | 61.10 |