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
