Abstract
Counting the number of unique items in a data set is of interest in many applications. For example, the owner of a web property, e.g., a video sharing website, a social media website, a search engine, etc., benefits from knowing the number of unique visitors to their site, the number of unique people that a certain advertisement was shown to, etc. This disclosure describes a practical cardinality estimator that uses O(m + log log N) space and has a conjectured O(1/sqrt(m)) relative error, where m is an accuracy parameter and N is the maximum cardinality that is to be reported. The cardinality estimator improves upon the best-known space bounds of prior cardinality estimators and matches on relative error.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Recommended Citation
N/A, "LinearLegions: A Linear Size Cardinality Estimator", Technical Disclosure Commons, (November 29, 2020)
https://www.tdcommons.org/dpubs_series/3830