We describe a new cardinality estimation algorithm that is extremely space-efficient. It applies one of three novel estimators to the compressed state of the Flajolet-Martin-85 coupon collection process. In an apples-to-apples empirical comparison against compressed HyperLogLog sketches, the new algorithm simultaneously wins on all three dimensions of the time space accuracy tradeoff. Our prototype uses the zstd compression library, and produces sketches that are smaller than the entropy of HLL, so no possible implementation of compressed HLL can match its space efficiency. The paper's technical contributions include analyses and simulations of the three new estimators, accurate values for the entropies of FM85 and HLL, and a non-trivial method for estimating a double asymptotic limit via simulation.
The HLL family of sketches began with the FM85 paper @cite_1 , which proposed an estimator based on the average position of the leftmost uncollected coupon in each row. Because the sketch required @math words of memory, the authors speculated that a lossy 8-column sliding window into the coupon tableau might suffice. With the benefit of hindsight we know that this specific idea didn't pan out, but this shows that at the very beginning of the field it was understood that sketches can be smaller than naive implementations would suggest.
@cite_1
1994945255 2963274201 2171217544 2010859647
Many datasets, including market basket data, text or hypertext documents, and events recorded in different locations or time periods, can be modeled as a collection of sets over a ground set of keys. Common queries over such data, including similarity or association rules are represented as the weight or selectivity of keys that satisfy some selection predicate defined over keys' attributes and memberships in particular sets. On massive data sets, exact computation of such aggregates can be inefficient or infeasible, and therefore, approximate queries are processed over sketches of the sets. Sketches based on coordinated random samples are scalable and flexible and well suited for many applications. Queries are resolved by producing a sketch of the union of sets used in the predicate from the sketches of these sets and then applying an estimator to this union-sketch. We derive novel tighter (unbiased) estimators that leverage sampled keys that are present in the union of applicable sketches but excluded from the union sketch. We establish analytically that our estimators dominate estimators applied to the union-sketch for all queries and data sets. Empirical evaluation on synthetic and real data reveals that on typical applications we can expect a 25 4 fold reduction in estimation error. This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An e approximate quantile sketch receives a stream of items x1,·,xn and allows one to approximate the rank of any query item up to additive error e n with probability at least 1-δ.The rank of a query x is the number of stream items such that xi ≤ x. The minimal sketch size required for this task is trivially at least 1 e.Felber and Ostrovsky obtain a O((1 e)log(1 e)) space sketch for a fixed δ.Without restrictions on the nature of the stream or the ratio between e and n, no better upper or lower bounds were known to date. This paper obtains an O((1 e)log log (1 δ)) space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching for which an Ω((1 e)log(1 e)) lower bound is known. One of our contributions is a novel representation and modification of the widely used merge-and-reduce construction. This modification allows for an analysis which is both tight and extremely simple. The same technique was reported, in private communications, to be useful for improving other sketching objectives and geometric coreset constructions. Motivated by the study of peer-to-peer file swarming systems a la BitTorrent, we introduce a probabilistic model of coupon replication systems. These systems consist of users aiming to complete a collection of distinct coupons. Users enter the system with an initial coupon provided by a bootstrap server, acquire other coupons from other users, and leave once they complete their coupon collection. For open systems, with exogenous user arrivals, we derive stability condition for a layered scenario, where encounters are between users holding the same number of coupons. We also consider a system where encounters are between users chosen uniformly at random from the whole population. We show that sojourn time in both systems is asymptotically optimal as the number of coupon types becomes large. We also consider closed systems with no exogenous user arrivals. In a special scenario where users have only one missing coupon, we evaluate the size of the population ultimately remaining in the system, as the initial number of users N goes to infinity. We show that this size decreases geometrically with the number of coupons K. In particular, when the ratio K log(N) is above a critical threshold, we prove that this number of leftovers is of order log(log(N)). These results suggest that, under the assumption that the bootstrap server is not a bottleneck, the performance does not depend critically on either altruistic user behavior or on load-balancing strategies such as rarest first. Motivated by the study of peer-to-peer file swarming systems a la BitTorrent, we introduce a probabilistic model of coupon replication systems. These systems consist of users, aiming to complete a collection of distinct coupons. Users are characterised by their current collection of coupons, and leave the system once they complete their coupon collection. The system evolution is then specified by describing how users of distinct types meet, and which coupons get replicated upon such encounters.For open systems, with exogenous user arrivals, we derive necessary and sufficient stability conditions in a layered scenario, where encounters are between users holding the same number of coupons. We also consider a system where encounters are between users chosen uniformly at random from the whole population. We show that performance, captured by sojourn time, is asymptotically optimal in both systems as the number of coupon types becomes large.We also consider closed systems with no exogenous user arrivals. In a special scenario where users have only one missing coupon, we evaluate the size of the population ultimately remaining in the system, as the initial number of users, N, goes to infinity. We show that this decreases geometrically with the number of coupons, K. In particular, when the ratio K log(N) is above a critical threshold, we prove that this number of left-overs is of order log(log(N)).These results suggest that performance of file swarming systems does not depend critically on either altruistic user behavior, or on load balancing strategies such as rarest first.