Hypergraph-based locality-enhancing methods for graph operations in Big Data applications
Author:
- 20 November 2023
- journal article
- research article
- Published by SAGE Publications in The International Journal of High Performance Computing Applications
- Vol. 38 (3) , 210-224
Abstract
The need for speeding up data analytics increases inevitably due to the need for extracting valuable information from social media, data generated by smart devices with sensors, patterns of people’s communications over the web, items viewed and bought by global-scale customers, cloud applications, etc., all of which take part in the “Big Data.” Such kind of interaction data is very well represented as sparse graphs to enable the graph analytics, which requires efficient underlying kernels. The breadth-first search (BFS)-based traversal is a commonly used kernel in graph algorithms such as the betweenness centrality algorithm for centrality analysis. In this work, we focus on parallel BFS operations and propose hypergraph-based combinatorial models that aim at reducing cache misses and hence exploiting data locality during the parallel BFS operations. Our models are based on finding new vertex visit orders so that locality in accessing the data associated with vertices is exploited. Experiments on graphs arising in a wide range of applications show that our proposed models achieve on average 9% performance improvement in the CPU-based Ligra data analytics framework.Keywords
This publication has 60 references indexed in Scilit:
- Augmented Betweenness Centrality for Environmentally Aware Traffic Monitoring in Transportation NetworksJournal of Intelligent Transportation Systems, 2012
- The Combinatorial BLAS: design, implementation, and applicationsThe International Journal of High Performance Computing Applications, 2011
- The future of microprocessorsCommunications of the ACM, 2011
- PEGASUS: mining peta-scale graphsKnowledge and Information Systems, 2010
- BROKERAGE QUALIFICATIONS IN RINGING OPERATIONS*Criminology, 2008
- Centrality and network flowSocial Networks, 2005
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplicationIEEE Transactions on Parallel and Distributed Systems, 1999
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- A Set of Measures of Centrality Based on BetweennessSociometry, 1977