Abstract | ||
---|---|---|
Many emerging applications are built upon large, un-structured datasets that exhibit highly irregular (or even nearly random) memory access patterns. Examples include informatics applications, and other problems that are often represented by unstructured graph-based data structures. It is well known that these applications are challenging for conventional architectures to execute (either serially or in parallel). The Depth First Search (DFS) benchmark pro-posed in this work uses the Boost Graph Library to perform a depth-first search on a large power-law graph, represent-ing "small world" phenomena. The graph in question ex-hibits a small average distance between any two vertices, a small diameter, and has a few high-degree vertices with a large number of low-degree vertices. Graphs such as this appear in many fields, including networking, biology, social networks, and data mining. Many of these applications are of critical importance to researchers, and the challenge of executing them on conventional machines increases as the graph size grows. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1109/IISWC.2006.302741 | PROCEEDINGS OF THE IEEE INTERNATIONAL SYMPOSIUM ON WORKLOAD CHARACTERIZATION |
Keywords | DocType | Citations |
data mining,power law,data structure,depth first search,social network,graph theory | Conference | 10 |
PageRank | References | Authors |
1.66 | 3 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Richard Murphy | 1 | 10 | 1.66 |
Jonathan W. Berry | 2 | 445 | 46.01 |
William Mclendon | 3 | 176 | 13.59 |
Bruce Hendrickson | 4 | 1669 | 214.08 |
Douglas Gregor | 5 | 318 | 22.35 |
Andrew Lumsdaine | 6 | 2754 | 236.74 |