Class: Quantile::Estimator
- Inherits:
-
Object
- Object
- Quantile::Estimator
- Defined in:
- lib/quantile/estimator.rb
Overview
Note:
Estimator is not concurrency safe.
Estimate quantile values efficiently where both the rank and the inaccuracy allowance are known a priori. This is accomplished via Graham Cormode and S. Muthukrishnan’s Effective Computation of Biased Quantiles over Data Streams in ICDE’05.
Instance Method Summary collapse
-
#initialize(*invariants) ⇒ Estimator
constructor
Create a streaming quantile estimator.
-
#observe(value) ⇒ Object
Observe a sample value with this Estimator.
-
#query(rank) ⇒ Numeric
Get a quantile value for a given rank.
Constructor Details
#initialize(*invariants) ⇒ Estimator
Create a streaming quantile estimator.
34 35 36 37 38 39 40 41 42 43 44 45 |
# File 'lib/quantile/estimator.rb', line 34 def initialize(*invariants) if invariants.empty? invariants = [Quantile.new(0.5, 0.05), Quantile.new(0.90, 0.01), Quantile.new(0.99, 0.001)] end @invariants = invariants @buffer = [] @head = nil @observations = 0 @items = 0 end |
Instance Method Details
#observe(value) ⇒ Object
Observe a sample value with this Quantile::Estimator.
52 53 54 55 56 57 |
# File 'lib/quantile/estimator.rb', line 52 def observe(value) @buffer << value if @buffer.size == BUFFER_SIZE flush end end |
#query(rank) ⇒ Numeric
Get a quantile value for a given rank.
67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
# File 'lib/quantile/estimator.rb', line 67 def query(rank) flush current = @head if current.nil? return 0 end mid_rank = (rank * @observations).floor max_rank = mid_rank + (invariant(mid_rank, @observations) / 2).floor rank = 0.0 while !current.successor.nil? rank += current.rank if rank + current.successor.rank + current.successor.delta > max_rank return current.value end current = current.successor end return current.value end |