Database Reference
In-Depth Information
The ideal partition sketch represents the iterative partition process with the optimal
bisection on each partition. In each bisection, the optimal bisection minimizes the
number of cross-partition edges between the two generated partitions. This is the best
case that existing bisection-based algorithms [44,46,47] can achieve. Partitioning with
optimal bisections does not necessarily result in partitions with the globally minimum
number of cross-partition edges. However, existing studies [44,46] have demonstrated
that they can achieve relatively good partitioning quality, approaching the global opti-
mum. Furthermore, the ideal partition sketch exhibits a few interesting properties:
7.5.2.1.1 Local Optimality
Denote
C
(
n
1
,
n
2
) as the number of cross-partition edges between two nodes
n
1
and
n
2
in the partition sketch. Given any two nodes
n
1
and
n
2
with a common parent node p
in the ideal partition sketch, we have
C
(
n
1
,
n
2
) is the minimum among all the possible
bisections on
p
.
By definition of the ideal partition sketch, the local optimality is achieved on each
bisection.
7.5.2.1.2 Monotonicity
Suppose the total number of cross-partition edges among any partitions at the same
level
l
in the partition sketch to be
T
l
. The monotonicity of the ideal partition sketch
is that
T
i
≤
T
j
, if
i
≤
j
.
Proof (sketch).
According to multilevel graph partitioning, a cross-partition edge
in level
i
is still a cross-partition edge in level
i
+ 1. Additionally, more cross-partition
edges are created during the bi-section at level
i
. Thus, the set of cross-partition edge
in level
i
is a subset of that in level
i
+ 1. Thus,
T
i
≤
T
i
+1
. Therefore,
T
i
≤
T
j
, if
i
≤
j
. □
The monotonicity reflects the increase in the number of cross-partition edges in
the recursive partitioning process.
7.5.2.1.3 Proximity
Given any two nodes
n
1
and
n
2
with a common parent node
p
, any other two nodes
n
3
and
n
4
with a common parent node
p
′, and
p
and
p
′ are with the same parent, we
have
C
(
n
1
,
n
2
) +
C
(
n
3
,
n
4
) ≥
C
(
n
π(1)
, n
π(2)
) +
C
(
n
π(3)
,
n
π(4)
) where π is any permutation
on (1, 2, 3, 4).
Proof (sketch).
According to local optimality, we know that
C
(
p
,
p
′) =
C
(
n
1
,
n
3
) +
C
(
n
1
,
n
4
) +
C
(
n
2
,
n
3
) +
C
(
n
2
,
n
4
) is the minimum. Thus, we have
C
(
n
1
,
n
2
) +
C
(
n
1
,
n
4
) +
C
(
n
3
,
n
2
) +
C
(
n
3
,
n
4
) ≥
C
(
p
,
p
′)
(7.1)
C
(
n
1
,
n
2
) +
C
(
n
1
,
n
3
) +
C
(
n
4
,
n
2
) +
C
(
n
4
,
n
3
) ≥
C
(
p
,
p
′)
(7.2)
Substituting
C
(
p
,
p
′), we have
C
(
n
1
,
n
3
) +
C
(
n
2
,
n
4
) ≤
C
(
n
1
,
n
2
) +
C
(
n
3
,
n
4
)
(7.3)
C
(
n
2
,
n
3
) +
C
(
n
1
,
n
4
) ≤
C
(
n
1
,
n
2
) +
C
(
n
3
,
n
4
)
(7.4)
Search WWH ::
Custom Search