hyperbitbit

HyperBitBit

Initial implementation of HyperBitBit as seen on the presentation by Robert Sedgewick, that aims to beat HyperLogLog in practice:

Necessary characteristics of a better algorithm

• Makes one pass through the stream.
• Uses a few dozen machine instructions per value
• Uses a few hundred bits
• Achieves 10% relative accuracy or better

Conjecture. On practical data, HyperBitBit, for N < 2^64,

• Uses 128 + 6 bits. (in this implementation case 128 + 8)
• Estimates cardinality within 10% of the actual.

Note

This is an implementation that still needs iterations and experimentation. Any help is more than welcome.

• Small cardinalities are way off
• Reinsertings same value increases counter (unlike HyperLogLog)

Using

// Create HyperBitBit
hbb := hyperbitbit.New()

// Add value to HyperBitBit
hbb.Add([]byte("hello"))

// Returns cardinality
hbb.Cardinality()

Initial Results

From demo

2017/03/21 23:16:49
        file:  data/words-1
        exact: 150
        estimate: 1380
        ratio: 89.13%
2017/03/21 23:16:49
        file:  data/words-2
        exact: 1308
        estimate: 1869
        ratio: 30.02%
2017/03/21 23:16:49
        file:  data/words-3
        exact: 76205
        estimate: 62486
        ratio: -21.96%
2017/03/21 23:16:49
        file:  data/words-4
        exact: 235886
        estimate: 255417
        ratio: 7.65%
2017/03/21 23:16:50
        file:  data/words-5
        exact: 349900
        estimate: 317192
        ratio: -10.31%
2017/03/21 23:16:50
        file:  data/words-6
        exact: 479829
        estimate: 448578
        ratio: -6.97%
2017/03/21 23:16:50
        total
        exact: 660131
        estimate: 648276
        ratio: -1.83%