Databases Reference
In-Depth Information
in [
5
,
9
]. However, a graph partitioning algorithm alone may not produce a solution
that is optimized for all the objectives and constraints of our optimization problem.
With S-PUT we show that such an algorithm can provide a good set of initial
partition assignments that can later be significantly improved upon by EA.
3.2
Algorithm
The S-PUT algorithm consists of two phases. In the
Initial Partitioning
phase, a
graph partitioning algorithm is used to obtain the initial population for the EA
process. In the
Final Partitioning
phase, the EA process takes place to result in
the final set of optimized partitioning assignments.
3.2.1
Initial Partitioning
It is observed that if we denote
f
ij
D
r
i
e
ij
C
r
j
e
ji
, the total read load can be
expressed as
N
N
N
M
X
X
X
X
C
1
2
read
D
L
r
i
f
ij
.1
p
is
/p
js
:
i
D
1
i
D
1
j
D
1
s
D
1
read
, we need to minimize
Thus, to minimize L
X
N
X
N
X
M
f
ij
.1
p
is
/p
js
:
i
D
1
j
D
1
s
D
1
This quantity is the sum of f
ij
of pairs of socially-connected users, i and j ,
who are assigned to different servers. Consider an undirected weighted graph G
formed by the vertices and links of the original social graph, where each vertex
i of G is associated with a weight
w
i
and each link (i , j )ofG with a weight
f
ij
. Our optimization problem is equivalent to finding an optimal partitioning of
graph G into M components such that (1) the edge cut, i.e., sum of the weights
of inter-component links, is minimum (to minimize L
read
), and (2) the total vertex
weight of each component is balanced (to satisfy the balancing constraint). This
is one of constrained weighted graph partitioning problems known to be NP-hard
[
3
,
18
,
23
,
26
], but there are well-approximated heuristic algorithms. Among them is
METIS [
18
], arguably the best approximate algorithm for partitioning a large graph
into equally weighted components with minimum edge cut. METIS can partition a
1-million-node graph in 256 parts in just a few seconds on today's PCs.
In S-PUT, we first obtain a set of partition assignments, each being a result of
applying METIS on graph G using a different “seed.” Seed is a random factor used
Search WWH ::
Custom Search