case object EdgePartition2D extends PartitionStrategy with Product with Serializable
Assigns edges to partitions using a 2D partitioning of the sparse edge adjacency matrix,
guaranteeing a 2 * sqrt(numParts)
bound on vertex replication.
Suppose we have a graph with 12 vertices that we want to partition over 9 machines. We can use the following sparse matrix representation:
__________________________________ v0 | P0 * | P1 | P2 * | v1 | **** | * | | v2 | ******* | ** | **** | v3 | ***** | * * | * | ---------------------------------- v4 | P3 * | P4 *** | P5 ** * | v5 | * * | * | | v6 | * | ** | **** | v7 | * * * | * * | * | ---------------------------------- v8 | P6 * | P7 * | P8 * *| v9 | * | * * | | v10 | * | ** | * * | v11 | * <-E | *** | ** | ----------------------------------
The edge denoted by E
connects v11
with v1
and is assigned to processor P6
. To get the
processor number we divide the matrix into sqrt(numParts)
by sqrt(numParts)
blocks. Notice
that edges adjacent to v11
can only be in the first column of blocks (P0, P3,
P6)
or the last
row of blocks (P6, P7, P8)
. As a consequence we can guarantee that v11
will need to be
replicated to at most 2 * sqrt(numParts)
machines.
Notice that P0
has many edges and as a consequence this partitioning would lead to poor work
balance. To improve balance we first multiply each vertex id by a large prime to shuffle the
vertex locations.
When the number of partitions requested is not a perfect square we use a slightly different method where the last column can have a different number of rows than the others while still maintaining the same size per block.
- Source
- PartitionStrategy.scala
- Alphabetic
- By Inheritance
- EdgePartition2D
- Product
- Equals
- PartitionStrategy
- Serializable
- AnyRef
- Any
- Hide All
- Show All
- Public
- Protected
Value Members
- final def !=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def ##: Int
- Definition Classes
- AnyRef → Any
- final def ==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
- final def asInstanceOf[T0]: T0
- Definition Classes
- Any
- def clone(): AnyRef
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.CloneNotSupportedException]) @IntrinsicCandidate() @native()
- final def eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- def equals(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef → Any
- final def getClass(): Class[_ <: AnyRef]
- Definition Classes
- AnyRef → Any
- Annotations
- @IntrinsicCandidate() @native()
- def getPartition(src: VertexId, dst: VertexId, numParts: PartitionID): PartitionID
Returns the partition number for a given edge.
Returns the partition number for a given edge.
- Definition Classes
- EdgePartition2D → PartitionStrategy
- final def isInstanceOf[T0]: Boolean
- Definition Classes
- Any
- final def ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
- final def notify(): Unit
- Definition Classes
- AnyRef
- Annotations
- @IntrinsicCandidate() @native()
- final def notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @IntrinsicCandidate() @native()
- def productElementName(n: Int): String
- Definition Classes
- Product
- def productElementNames: Iterator[String]
- Definition Classes
- Product
- final def synchronized[T0](arg0: => T0): T0
- Definition Classes
- AnyRef
- final def wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
- final def wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException]) @native()
- final def wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.InterruptedException])
Deprecated Value Members
- def finalize(): Unit
- Attributes
- protected[lang]
- Definition Classes
- AnyRef
- Annotations
- @throws(classOf[java.lang.Throwable]) @Deprecated
- Deprecated
(Since version 9)