Database Reference
In-Depth Information
7.5.3 Bandwidth Aware Graph Partitioning .............................................. 243
7.5.3.1 Background on the Bisection in the Multilevel Graph
Partitioning ........................................................................ 243
7.5.3.2 Network Transfer due to Cross Edges ................................244
7.5.3.3 Partitioning the Machine Graph ........................................ 245
7.5.3.4 Network Performance Aware Partitioning ........................ 245
7.5.3.5 Partition Numbers ..............................................................246
7.6 Hierarchical Combination of Execution .......................................................246
7.7 Related Work on Graph Partitioning ............................................................ 247
7.7.1 Geometric Methods .......................................................................... 248
7.7.2 Spectral Methods .............................................................................. 248
7.7.3 Metaheuristic-Based Approaches ..................................................... 248
7.7.4 Streaming Graph Partitioning .......................................................... 248
7.7.5 Distributed Graph Partitioning Algorithms ...................................... 249
7.7.6 The Metis Framework ....................................................................... 249
7.8 Open Problems ............................................................................................. 249
7.8.1 Architectural Design ........................................................................ 249
7.8.2 Application Needs ............................................................................ 249
7.8.3 Computation Model .......................................................................... 250
7.8.4 Cost of Ownership ............................................................................ 250
7.9 Summary ...................................................................................................... 250
References .............................................................................................................. 250
7.1 INTRODUCTION
A wide variety of recent applications model their data in graphs/networks such as
social networks, web graphs, and protein-protein interaction networks. Efficient
processing for large graph data poses new challenges for almost all components of
state-of-the-art data management systems. To list a few examples: (i) graph data are
complex structures and cannot be efficiently stored as relational tables; (ii) the access
patterns of large graph processing are complex, which results in inefficient disk
accesses or network communications; and (iii) last but not least, to tackle scalability
issues, graph processing must be efficiently distributed in a networked environment.
Researchers have been actively proposing many innovative solutions to address the
new challenges of large graph processing. In particular, a notable number of techniques
have recently been proposed to utilize the cloud. The objectives of this chapter are
(i) to introduce typical examples of large graph processing, (ii) to give an overview of
existing cloud-based graph processing platforms, and more importantly, (iii) to empha-
size a network performance aware data partitioning approach, which bridges large
graph processing and cloud-based platforms. In particular, the network bandwidth may
not be uniform across the large network in a cloud; a network with higher bandwidth
between its machines can support more intermachine computation.
The chapter is structured as follows. We survey some typical examples of large graph
processing in Section 7.2. In Section 7.3, we list some representative cloud-based graph
processing platforms. Section 7.4 presents the network unevenness in cloud-based sys-
tems and Section 7.5 introduces network performance aware graph partitioning. For the
Search WWH ::
Custom Search