Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling

Summary: Formalizes inverse-distribution streaming, showing forward-distribution sketches can fail for frequency-of-frequencies queries. Introduces dynamic inverse sampling with provable space, time, and accuracy guarantees for quantiles, histograms, heavy hitters, and rare-item detection. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h4910d0554184bbe4
Venue: VLDB
Year: 2005
Pagerank: 8.9239861e-05
Overall Rank: 2,171 | 85.41%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (AT&T)
2. S. Muthukrishnan (Rutgers University)
3. Irina Rozenbaum (Rutgers University)

BibTeX Citation

@article{cormode_vldb05,
        title = {{Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling}},
        author = {Cormode, Graham and Muthukrishnan, S. and Rozenbaum, Irina},
        journal = {PVLDB},
        series = {{VLDB} '05},
        volume = {31},
        pages = {25--36},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
805	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00013794691
1,169	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011726145
2,624	Optimal Sampling from Sliding Windows	2009	PODS	8.2095532e-05
4,446	Fast Manhattan Sketches in Data Streams	2010	PODS	6.5969248e-05
5,851	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9718136e-05
6,011	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.9143905e-05
11,089	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.9793485e-05
11,094	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.9793485e-05
11,828	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.9793485e-05
12,197	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052121228
57	On Random Sampling over Joins	1999	SIGMOD	0.00040108301
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
240	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023435436
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021914399
510	TelegraphCQ: Continuous Dataflow Processing	2003	SIGMOD	0.00017065714
519	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016942879
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.000134266
1,290	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00011157506
1,946	Aurora: A Data Stream Management System	2003	SIGMOD	9.3249193e-05
3,094	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6533343e-05
3,272	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.4734096e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,219	Optimal Sampling From Distributed Streams	2010	PODS
2	742	Dynamic Multidimensional Histograms	2002	SIGMOD
3	3,678	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD
4	9,496	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB
5	3,038	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
6	909	Finding Frequent Items in Data Streams	2008	VLDB
7	12,329	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD
8	7,973	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS
9	5,318	Sampling Algorithms in a Stream Operator	2005	SIGMOD
10	12,596	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS