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.9197633e-05
Overall Rank: 2,173 | 85.40%
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.00013788161
1,170	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00011720594
2,626	Optimal Sampling from Sliding Windows	2009	PODS	8.205667e-05
4,448	Fast Manhattan Sketches in Data Streams	2010	PODS	6.5938243e-05
5,854	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.9689965e-05
6,011	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.911598e-05
11,098	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.9769913e-05
11,103	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.9769913e-05
11,834	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.9769913e-05
12,203	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS	4.9769913e-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.00052097907
57	On Random Sampling over Joins	1999	SIGMOD	0.00040095727
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030586757
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028621958
240	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023425462
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023354266
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022713652
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021908194
511	TelegraphCQ: Continuous Dataflow Processing	2003	SIGMOD	0.00017058115
518	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016938992
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013420431
1,290	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00011155963
1,947	Aurora: A Data Stream Management System	2003	SIGMOD	9.320509e-05
3,096	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6497893e-05
3,273	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.469873e-05

Semantically Similar Papers

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