Continuous Distributed Counting for Non-monotonic Streams

Summary: Randomized algorithms for continual distributed counting on non‑monotonic streams with unknown drift μ, adversarial site assignment but random arrivals, achieving expected communication Õ(min{k/(|μ|ε), k n/ε, n}) with matching lower bounds. Extends to fractional Brownian inputs and yields F2 estimation and Bayesian linear regression applications. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1586
Venue: PODS
Year: 2012
Pagerank: 5.7496345e-05
Overall Rank: 6,871 | 52.86%
DOI: 10.1145/2213556.2213597

Incoming Non-self Citations Over Time

Authors

1. Zhenming Liu (Harvard University; Microsoft)
2. Božidar Radunović (Microsoft)
3. Milan Vojnović (Microsoft)

BibTeX Citation

@inproceedings{liu_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{Continuous Distributed Counting for Non-monotonic Streams}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213597},
        doi = {10.1145/2213556.2213597},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Liu, Zhenming and Radunović, Božidar and Vojnović, Milan},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,026	Variability in Data Streams	2016	PODS	5.093636e-05
12,054	Scalable Approximate Query Tracking over Highly Distributed Data Streams	2016	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
722	Adaptive Filters for Continuous Queries over Distributed Data Streams	2003	SIGMOD	0.00014627248
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
1,400	Power-Conserving Computation of Order-Statistics over Sensor Networks	2004	PODS	0.00010890603
2,178	Optimal Sampling From Distributed Streams	2010	PODS	9.0159538e-05
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	7.0856664e-05
3,856	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS	7.0690791e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,919	Optimal Bounds for Approximate Counting	2022	PODS
2	7,488	Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming	2022	VLDB
3	691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS
4	550	Distributed Top-K Monitoring	2003	SIGMOD
5	1,433	Communication-Efficient Distributed Monitoring of Thresholded Counts	2006	SIGMOD
6	7,479	Distributed Online Tracking	2015	SIGMOD
7	6,697	Continuous Matrix Approximation on Distributed Data	2014	VLDB
8	3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS
9	3,856	Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks	2012	PODS
10	12,026	Variability in Data Streams	2016	PODS