You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by viirya <gi...@git.apache.org> on 2015/02/20 19:19:12 UTC
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
GitHub user viirya opened a pull request:
https://github.com/apache/spark/pull/4706
[SPARK-5927][MLlib] Modify FPGrowth's partition strategy to reduce transactions in partitions
Currently FPGrowth does not really partition the transactions used for building trees. So every partition almost gets all transactions to build prefix trees even many transactions are not needed for them to generate the fp. This pr tries to modify the partition strategy and reduce the transactions sent to partitions.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/viirya/spark-1 fp_partition
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/4706.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #4706
----
commit dd8a0a7551f29f7eafb41fe24c2b0ac6dc8e8dd4
Author: Liang-Chi Hsieh <vi...@gmail.com>
Date: 2015-02-20T17:58:04Z
Modify FP's partition strategy to reduce transactions in partitions.
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75367804
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/27809/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75305283
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/27784/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75292072
[Test build #27784 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27784/consoleFull) for PR 4706 at commit [`dd8a0a7`](https://github.com/apache/spark/commit/dd8a0a7551f29f7eafb41fe24c2b0ac6dc8e8dd4).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75383344
Say we have ranks 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and two partitions. With HashPartitioner, the mapping is
(0, 2, 4, 6, 8) -> part 0, (1, 3, 5, 7, 9) -> part 1. With the partitioning scheme you proposed, the mapping is
(0, 1, 2, 3, 4) -> Part 0, (5, 6, 7, 8, 9) -> part 1. This will reduce the shuffle size to part 1 but increases the the load on part 0. For a parallel algorithm, we care more about the wall-clock time. I think it will increase the overall time. I can also give examples that yours won't work well.
~~~
1 3 5
2 4 6
1 3 7
2 4 8
1 3 9
~~~
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75365170
[Test build #27809 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27809/consoleFull) for PR 4706 at commit [`a91ae90`](https://github.com/apache/spark/commit/a91ae9076dce651f8351aad6cb1e880a9cb9c620).
* This patch merges cleanly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75298534
@viirya Could you explain your changes? `partitioner.getPartition(item)` will return a partition id in `[0, numPartitions)`. For every transaction and for any partition, we send at most one slice of the transaction to the partition. I don't see how this PR changes the behavior.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75513467
okay. let's close this if you think it is not working.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75305273
[Test build #27784 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27784/consoleFull) for PR 4706 at commit [`dd8a0a7`](https://github.com/apache/spark/commit/dd8a0a7551f29f7eafb41fe24c2b0ac6dc8e8dd4).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by viirya <gi...@git.apache.org>.
Github user viirya closed the pull request at:
https://github.com/apache/spark/pull/4706
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75599387
@viirya Your proposal definitely works better in some cases, while the current implementation works better in some others. I think we both agree on this. The question is which partitioning scheme fits real datasets better. I don't have a clear answer. If there are some standard benchmark datasets, we can compare the performance.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75365051
Currently, since we are using HashPartitioner and item rankings to decide the partition, you get a very even distribution. When the given partition number is less than the number of items, this distribution is inefficient.
For example, assume we have the transactions including 9 items as:
"r z h k p a b d e"
"z y x w v u t s a b c"
"s x o n r a c i"
"x z y m t s q e b c"
"z a u"
"x z y r q t p a n m"
As we use 2 partitions, the current implementation generates such partitions:
Map(1 -> List(0, 2, 3, 4, 6, 7), 0 -> List(0, 2, 3, 4, 6, 7, 8))
Map(1 -> List(0, 1, 4, 5), 0 -> List(0, 1, 4))
Map(1 -> List(0, 1, 2, 3, 4, 6, 7), 0 -> List(0, 1, 2, 3, 4, 6, 7, 8))
Map(1 -> List(0, 1), 0 -> List(0))
Map(1 -> List(1, 2, 5), 0 -> List(1, 2, 5, 6, 8))
Map(1 -> List(0, 1, 2, 3, 5, 7), 0 -> List(0, 1, 2))
For the transaction `List(0, 1, 2, 3, 4, 6, 7, 8)` and `List(0, 2, 3, 4, 6, 7, 8)`, two partition almost copy same items.
With this pr:
Map(1 -> List(0, 1, 4, 5), 0 -> List(0, 1, 4))
Map(1 -> List(0, 2, 3, 4, 6, 7, 8), 0 -> List(0, 2, 3, 4))
Map(1 -> List(0, 1, 2, 3, 4, 6, 7, 8), 0 -> List(0, 1, 2, 3, 4))
Map(0 -> List(0, 1))
Map(1 -> List(0, 1, 2, 3, 5, 7), 0 -> List(0, 1, 2, 3))
Map(1 -> List(1, 2, 5, 6, 8), 0 -> List(1, 2)
Now `List(0, 1, 2, 3, 4, 6, 7, 8)` generates two partitions `List(0, 1, 2, 3, 4, 6, 7, 8)` and `List(0, 1, 2, 3, 4)`. `List(0, 2, 3, 4, 6, 7, 8)` generates `List(0, 2, 3, 4, 6, 7, 8)` and `List(0, 2, 3, 4)`.
Then for the partition 0, it has less items to build its prefix tree. For the partition 1, it has the same items to build its tree as before.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75422885
Because of the design of Parallel FP-Growth (implemented in `genCondTransactions`), when we have the ranks 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and two partitions, original mapping would be (0, 1, 2, 3, 4, 5, 6, 7, 8) -> part 0, (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) -> part 1. The algorithm scans the ranks (`filtered` in `genCondTransactions`) from right to left. For a rank it first sees, it takes the slice from its potition to most left (`filtered.slice(0, i + 1)`).
With the partitioning scheme I proposed, we would get the mapping (0, 1, 2, 3, 4) -> part 0, (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) -> part 1.
You can see my previous comment where the case is 9 items and 2 partitions.
The current:
Map(1 -> List(0, 1, 2, 3, 4, 6, 7), 0 -> List(0, 1, 2, 3, 4, 6, 7, 8))
The propose:
Map(1 -> List(0, 1, 2, 3, 4, 6, 7, 8), 0 -> List(0, 1, 2, 3, 4))
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by viirya <gi...@git.apache.org>.
Github user viirya commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75689302
@mengxr I see. Thanks.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75367802
[Test build #27809 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/27809/consoleFull) for PR 4706 at commit [`a91ae90`](https://github.com/apache/spark/commit/a91ae9076dce651f8351aad6cb1e880a9cb9c620).
* This patch **passes all tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request: [SPARK-5927][MLlib] Modify FPGrowth's partitio...
Posted by mengxr <gi...@git.apache.org>.
Github user mengxr commented on the pull request:
https://github.com/apache/spark/pull/4706#issuecomment-75502698
@viirya As I mentioned, the partitioning scheme you proposed will make the first partition (which contains the most frequent items) very heavy load and slows down the entire process. Please check the example I gave. Using a random partitioning scheme helps distribute the work. It may increase the total shuffle size in some cases but the work loads are more balanced.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org