4 citations · 4 across the 4 of their papers we have counts for
5 papers · 1 filter
Universal Perfect Samplers for Incremental Streams
Seth Pettie, Dingyu Wang
If , the -moment of a vector is and the -sampling problem i…
Harmonic Decomposition in Data Sketches
Dingyu Wang
In the turnstile streaming model, a dynamic vector is updated by a stream of entry-wise increments/decrements. Let $…
Simpler and Better Cardinality Estimators for HyperLogLog and PCSA
Seth Pettie, Dingyu Wang
\emph{Cardinality Estimation} (aka \emph{Distinct Elements}) is a classic problem in sketching with many industrial applications. Although sketching \emph{algorithms} are fairly si…
Non-Mergeable Sketching for Cardinality Estimation
Seth Pettie, Dingyu Wang, Longhui Yin
Cardinality estimation is perhaps the simplest non-trivial statistical problem that can be solved via sketching. Industrially-deployed sketches like HyperLogLog, MinHash, and PCSA…
Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
Seth Pettie, Dingyu Wang
Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching. In this paper we study the intrinsic tradeoff between…