Name
Abstract | ||
|---|---|---|
Approximate computing enables processing of large-scale graphs by trading off quality for performance. Approximate computing techniques have become critical not only due to the emergence of parallel architectures but also due to the availability of large scale datasets enabling data-driven discovery. Using two prototypical graph algorithms, PageRank and community detection, we present several approximate computing heuristics to scale the performance with minimal loss of accuracy. We present several heuristics including loop perforation, data caching, incomplete graph coloring and synchronization, and evaluate their efficiency. We demonstrate performance improvements of up to 83% for PageRank and up to 450x for community detection, with low impact on accuracy for both the algorithms. We expect the proposed approximate techniques will enable scalable graph analytics on data of importance to several applications in science and their subsequent adoption to scale similar graph algorithms. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/HiPC.2017.00013 | 2017 IEEE 24th International Conference on High Performance Computing (HiPC) |
Keywords | Field | DocType |
Approximate Computing,Graph Algorithms,PageRank,Community Detection,Parallel Algorithms | PageRank,Graph algorithms,Synchronization,Parallel algorithm,Computer science,Parallel computing,Heuristics,Scalability,Graph coloring,Approximate computing | Conference |
ISSN | ISBN | Citations |
1094-7256 | 978-1-5386-2294-0 | 0 |
PageRank | References | Authors |
0.34 | 14 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ajay Panyala | 1 | 12 | 3.97 |
| Omer Subasi | 2 | 41 | 6.34 |
| Mahantesh Halappanavar | 3 | 218 | 33.64 |
| Kalyanaraman, Ananth | 4 | 221 | 31.95 |
| Daniel G. Chavarría-miranda | 5 | 281 | 25.00 |
| Sriram Krishnamoorthy | 6 | 1202 | 86.68 |