Dingyu Wang

most citedInformation Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon

4 citations · 4 across the 1 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026★ 4 cited

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…

cs.DS2024

Harmonic Decomposition in Data Sketches

Dingyu Wang

In the turnstile streaming model, a dynamic vector $x = (x_{1}, \dots, x_{n}) \in Z^{n}$ is updated by a stream of entry-wise increments/decrements. Let $…

cs.DS2024

Universal Perfect Samplers for Incremental Streams

Seth Pettie, Dingyu Wang

If $G : R_{+} \to R_{+}$ , the $G$ -moment of a vector $x \in R_{+}^{n}$ is $G (x) = \sum_{v \in [n]} G (x (v))$ and the $G$ -sampling problem i…