Paper Info
Title
Graph partitioning strategies for efficient BFS in shared-nothing parallel systems
Abstract
Traversing massive graphs as efficiently as possible is essential for many applications. Many common operations on graphs, such as calculating the distance between two nodes, are based on the Breadth First Search traversal. However, because of the exhaustive exploration of all the nodes and edges of the graph, this operation might be very time consuming. A possible solution is distributing the graph among the nodes of a shared-nothing parallel system. Nevertheless, this operation may generate a large amount of inter-node communication. In this paper, we propose two graph partitioning techniques and improve previous distributed versions of BFS in order to reduce this communication.
Year
DOI
Venue
2010
10.1007/978-3-642-16720-1_2
WAIM Workshops
Keywords
Field
DocType
possible solution,massive graph,efficient bfs,exhaustive exploration,large amount,inter-node communication,breadth first search traversal,common operation,time consuming,shared-nothing parallel system,graph databases,graph partitioning,breadth first search,parallel systems
Graph operations,Block graph,Comparability graph,Modular decomposition,Computer science,Parallel computing,Theoretical computer science,Graph product,Pathwidth,Graph partition,Graph (abstract data type)
Conference
Volume
ISSN
ISBN
6185
0302-9743
3-642-16719-5
Citations 
PageRank 
References 
5
0.49
7
Authors
5
Name
Order
Citations
PageRank
Victor Muntés-Mulero120422.79
Norbert Martinez-Bazan2484.98
Josep-Lluís Larriba-Pey3132.41
Esther Pacitti475793.78
Patrick Valduriez534591306.40