[jira] [Updated] (HBASE-5139) Compute (weighted) median using AggregateProtocol

["Andrew Purtell (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/HBASE-5139?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Andrew Purtell updated HBASE-5139:
----------------------------------
    Resolution: Fixed
        Status: Resolved  (was: Patch Available)

Committed ages ago.
[~ted_yu], please consider setting fix versions appropriately.

> Compute (weighted) median using AggregateProtocol
> -------------------------------------------------
>
>                 Key: HBASE-5139
>                 URL: https://issues.apache.org/jira/browse/HBASE-5139
>             Project: HBase
>          Issue Type: Sub-task
>            Reporter: Ted Yu
>            Assignee: Ted 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 was sent by Atlassian JIRA
(v6.3.4#6332)