• antirez's avatar
    HyperLogLog approximated cardinality caching. · 7acccc7e
    antirez authored
    The more we add elements to an HyperLogLog counter, the smaller is
    the probability that we actually update some register.
    
    From this observation it is easy to see how it is possible to use
    caching of a previously computed cardinality and reuse it to serve
    HLLCOUNT queries as long as no register was updated in the data
    structure.
    
    This commit does exactly this by using just additional 8 bytes for the
    data structure to store a 64 bit unsigned integer value cached
    cardinality. When the most significant bit of the 64 bit integer is set,
    it means that the value computed is no longer usable since at least a
    single register was modified and we need to recompute it at the next
    call of HLLCOUNT.
    
    The value is always stored in little endian format regardless of the
    actual CPU endianess.
    7acccc7e
hyperloglog.c 21.4 KB