search

elastic / elasticsearch

Free and Open Source, Distributed, RESTful Search Engine
https://www.elastic.co/products/elasticsearch
Other
1.05k stars 24.83k forks source link

LogLog-β algorithm for cardinality estimation #22230

Closed costin closed 6 years ago

costin commented 7 years ago

Describe the feature: A new paper released this month introduces a new cardinality estimation algorithm called LogLog-Beta/β:

"The new algorithm uses only one formula and needs no additional bias corrections for the entire range of cardinalities, therefore, it is more efficient and simpler to implement. Our simulations show that the accuracy provided by the new algorithm is as good as or better than the accuracy provided by either of HyperLogLog or HyperLogLog++."

Some comments about its accuracy (graphs included) can be found in this PR.

colings86 commented 6 years ago

Closing this issuee for now, as mentioned in https://github.com/elastic/elasticsearch/pull/22323#issuecomment-314782891 the improvements in accuracy did not appear to be significant when we tested this so we are not going to pursue this for now