You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@hbase.apache.org by "Zhihong Yu (Created) (JIRA)" <ji...@apache.org> on 2012/01/06 19:49:40 UTC
[jira] [Created] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Compute (weighted) median using AggregateProtocol
-------------------------------------------------
Key: HBASE-5139
URL: https://issues.apache.org/jira/browse/HBASE-5139
Project: HBase
Issue Type: Sub-task
Reporter: Zhihong Yu
Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
This can be done in two passes.
The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
(start-rowkey, partial-sum-of-values, partial-sum-of-weights)
The start-rowkey is used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
The second pass involves scanning the region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Hadoop QA (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13183443#comment-13183443 ]
Hadoop QA commented on HBASE-5139:
----------------------------------
-1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12510074/5139-v2.txt
against trunk revision .
+1 @author. The patch does not contain any @author tags.
+1 tests included. The patch appears to include 3 new or modified tests.
+1 javadoc. The javadoc tool did not generate any warning messages.
-1 javac. The patch appears to cause mvn compile goal to fail.
-1 findbugs. The patch appears to cause Findbugs (version 1.3.9) to fail.
+1 release audit. The applied patch does not increase the total number of release audit warnings.
-1 core tests. The patch failed these unit tests:
Test results: https://builds.apache.org/job/PreCommit-HBASE-Build/720//testReport/
Console output: https://builds.apache.org/job/PreCommit-HBASE-Build/720//console
This message is automatically generated.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt, 5139.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: (was: 5139.txt)
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Hadoop QA (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13191261#comment-13191261 ]
Hadoop QA commented on HBASE-5139:
----------------------------------
-1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12511514/5139.addendum
against trunk revision .
+1 @author. The patch does not contain any @author tags.
-1 tests included. The patch doesn't appear to include any new or modified tests.
Please justify why no new tests are needed for this patch.
Also please list what manual steps were performed to verify this patch.
-1 patch. The patch command could not apply the patch.
Console output: https://builds.apache.org/job/PreCommit-HBASE-Build/836//console
This message is automatically generated.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt, 5139.addendum
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Hudson (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13191941#comment-13191941 ]
Hudson commented on HBASE-5139:
-------------------------------
Integrated in HBase-TRUNK-security #86 (See [https://builds.apache.org/job/HBase-TRUNK-security/86/])
HBASE-5139 Addendum handles startRow being null for the case where median is in the first region
tedyu :
Files :
* /hbase/trunk/src/main/java/org/apache/hadoop/hbase/client/coprocessor/AggregationClient.java
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt, 5139.addendum
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Hudson (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13184393#comment-13184393 ]
Hudson commented on HBASE-5139:
-------------------------------
Integrated in HBase-TRUNK #2620 (See [https://builds.apache.org/job/HBase-TRUNK/2620/])
HBASE-5139 Compute (weighted) median using AggregateProtocol
tedyu :
Files :
* /hbase/trunk/src/main/java/org/apache/hadoop/hbase/client/coprocessor/AggregationClient.java
* /hbase/trunk/src/main/java/org/apache/hadoop/hbase/coprocessor/AggregateImplementation.java
* /hbase/trunk/src/main/java/org/apache/hadoop/hbase/coprocessor/AggregateProtocol.java
* /hbase/trunk/src/test/java/org/apache/hadoop/hbase/coprocessor/TestAggregateProtocol.java
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: (was: 5139.txt)
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13184264#comment-13184264 ]
Zhihong Yu commented on HBASE-5139:
-----------------------------------
I am going to integrate patch v2 if there is no objection.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: 5139.txt
Patch now supports weighted median
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Hudson (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13191886#comment-13191886 ]
Hudson commented on HBASE-5139:
-------------------------------
Integrated in HBase-TRUNK #2645 (See [https://builds.apache.org/job/HBase-TRUNK/2645/])
HBASE-5139 Addendum handles startRow being null for the case where median is in the first region
tedyu :
Files :
* /hbase/trunk/src/main/java/org/apache/hadoop/hbase/client/coprocessor/AggregationClient.java
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt, 5139.addendum
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: (was: 5139.txt)
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: 5139.addendum
Addendum that handles startRow being null for the case where median is in the first region.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt, 5139.addendum
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: 5139-v2.txt
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Comment: was deleted
(was: -1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12510074/5139-v2.txt
against trunk revision .
+1 @author. The patch does not contain any @author tags.
+1 tests included. The patch appears to include 3 new or modified tests.
+1 javadoc. The javadoc tool did not generate any warning messages.
-1 javac. The patch appears to cause mvn compile goal to fail.
-1 findbugs. The patch appears to cause Findbugs (version 1.3.9) to fail.
+1 release audit. The applied patch does not increase the total number of release audit warnings.
-1 core tests. The patch failed these unit tests:
Test results: https://builds.apache.org/job/PreCommit-HBASE-Build/720//testReport/
Console output: https://builds.apache.org/job/PreCommit-HBASE-Build/720//console
This message is automatically generated.)
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Assigned] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Assigned) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu reassigned HBASE-5139:
---------------------------------
Assignee: Zhihong Yu
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13184320#comment-13184320 ]
Zhihong Yu commented on HBASE-5139:
-----------------------------------
Integrated to TRUNK.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Description:
Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
This can be done in two passes.
The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
(partial-sum-of-values, partial-sum-of-weights)
The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
In that case, sequential scanning seems to be the solution which is slower than the above approach.
was:
Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
This can be done in two passes.
The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
(start-rowkey, partial-sum-of-values, partial-sum-of-weights)
The start-rowkey is used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
In that case, sequential scanning seems to be the solution which is slower than the above approach.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13183480#comment-13183480 ]
Zhihong Yu commented on HBASE-5139:
-----------------------------------
I want to point out that weighted median computation in patch v2 is only for reference.
Consider the case where cf:cq1, the value column, has different data type from cf:cq2, the weight column. Two ColumnInterpreters should be provided, one for value column and one for weight column.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Hadoop QA (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13183488#comment-13183488 ]
Hadoop QA commented on HBASE-5139:
----------------------------------
-1 overall. Here are the results of testing the latest attachment
http://issues.apache.org/jira/secure/attachment/12510076/5139-v2.txt
against trunk revision .
+1 @author. The patch does not contain any @author tags.
+1 tests included. The patch appears to include 3 new or modified tests.
-1 javadoc. The javadoc tool appears to have generated -151 warning messages.
+1 javac. The applied patch does not increase the total number of javac compiler warnings.
-1 findbugs. The patch appears to introduce 81 new Findbugs (version 1.3.9) warnings.
+1 release audit. The applied patch does not increase the total number of release audit warnings.
-1 core tests. The patch failed these unit tests:
org.apache.hadoop.hbase.mapreduce.TestImportTsv
org.apache.hadoop.hbase.mapred.TestTableMapReduce
org.apache.hadoop.hbase.mapreduce.TestHFileOutputFormat
Test results: https://builds.apache.org/job/PreCommit-HBASE-Build/721//testReport/
Findbugs warnings: https://builds.apache.org/job/PreCommit-HBASE-Build/721//artifact/trunk/patchprocess/newPatchFindbugsWarnings.html
Console output: https://builds.apache.org/job/PreCommit-HBASE-Build/721//console
This message is automatically generated.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Hudson (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13184367#comment-13184367 ]
Hudson commented on HBASE-5139:
-------------------------------
Integrated in HBase-TRUNK-security #73 (See [https://builds.apache.org/job/HBase-TRUNK-security/73/])
HBASE-5139 Compute (weighted) median using AggregateProtocol
tedyu :
Files :
* /hbase/trunk/src/main/java/org/apache/hadoop/hbase/client/coprocessor/AggregationClient.java
* /hbase/trunk/src/main/java/org/apache/hadoop/hbase/coprocessor/AggregateImplementation.java
* /hbase/trunk/src/main/java/org/apache/hadoop/hbase/coprocessor/AggregateProtocol.java
* /hbase/trunk/src/test/java/org/apache/hadoop/hbase/coprocessor/TestAggregateProtocol.java
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Status: Patch Available (was: Open)
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt, 5139.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: (was: 5139-v2.txt)
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: 5139.txt
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: 5139-v2.txt
Patch version 2 modifies some javadoc and utilizes scanner caching in pass 2.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139-v2.txt, 5139.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Attachment: 5139.txt
Patch v1 shows how un-weighted median is calculated.
A simple test is included.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
> Assignee: Zhihong Yu
> Attachments: 5139.txt
>
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (partial-sum-of-values, partial-sum-of-weights)
> The start rowkey (supplied by coprocessor framework) would be used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (HBASE-5139) Compute (weighted) median using
AggregateProtocol
Posted by "Zhihong Yu (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Zhihong Yu updated HBASE-5139:
------------------------------
Description:
Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
This can be done in two passes.
The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
(start-rowkey, partial-sum-of-values, partial-sum-of-weights)
The start-rowkey is used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
In that case, sequential scanning seems to be the solution which is slower than the above approach.
was:
Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
This can be done in two passes.
The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
(start-rowkey, partial-sum-of-values, partial-sum-of-weights)
The start-rowkey is used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
The second pass involves scanning the region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
In that case, sequential scanning seems to be the solution which is slower than the above approach.
> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
> Key: HBASE-5139
> URL: https://issues.apache.org/jira/browse/HBASE-5139
> Project: HBase
> Issue Type: Sub-task
> Reporter: Zhihong Yu
>
> Suppose cf:cq1 stores numeric values and optionally cf:cq2 stores weights. This task finds out the median value among the values of cf:cq1 (See http://www.stat.ucl.ac.be/ISdidactique/Rhelp/library/R.basic/html/weighted.median.html)
> This can be done in two passes.
> The first pass utilizes AggregateProtocol where the following tuple is returned from each region:
> (start-rowkey, partial-sum-of-values, partial-sum-of-weights)
> The start-rowkey is used to sort the tuples. This way we can determine which region (called R) contains the (weighted) median. partial-sum-of-weights can be 0 if unweighted median is sought
> The second pass involves scanning the table, beginning with startrow of region R and computing partial (weighted) sum until the threshold of S/2 is crossed. The (weighted) median is returned.
> However, this approach wouldn't work if there is mutation in the underlying table between pass one and pass two.
> In that case, sequential scanning seems to be the solution which is slower than the above approach.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira