hbase-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Zhihong Yu (Updated) (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (HBASE-5139) Compute (weighted) median using AggregateProtocol
Date Mon, 09 Jan 2012 22:59:42 GMT

     [ 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

        

Mime
View raw message