Module: HyperLogLog::Algorithm

Included in:
Counter, TimeSeriesCounter
Defined in:
lib/algorithm.rb

Instance Method Summary collapse

Instance Method Details

#initialize(redis, b = 10) ⇒ Object 



7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
# File 'lib/algorithm.rb', line 7

def initialize(redis, b=10)
  raise "Accuracy not supported. Please choose a value of b between 4 and 16" if b < 4 || b > 16
  @redis = redis
  @bits_in_hash = 32 - b
  @m = (2 ** b).to_i
  if @m == 16
    @alpha = 0.673
  elsif @m == 32
    @alpha = 0.697
  elsif @m == 64
    @alpha = 0.709
  else
    @alpha = 0.7213/(1 + 1.079/@m)
  end
end

#intersection(counter_names, time = 0) ⇒ Object

Estimate the cardinality of the intersection of several sets. We do this by using the principle of inclusion and exclusion to represent the size of the intersection as the alternating sum of an exponential number of cardinalities of unions of smaller sets.



27
28
29
30
31
32
33
34
 
# File 'lib/algorithm.rb', line 27

def intersection(counter_names, time=0)
  icount = (1..counter_names.length).map do |k|
    counter_names.combination(k).map do |group|
      ((k % 2 == 0) ? -1 : 1) * union_helper(group, time)
    end.inject(0, :+)
  end.inject(0, :+)
  [icount, 0].max
end