DBScholar

Back to papers

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
9498
Venue
VLDB
Year
2005
Pagerank
9.1271562e-05
Overall Rank
2,128 | 85.41%
DOI
-

Incoming Non-self Citations Over Time

Authors

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
777 Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems 2011 PODS 0.0001410593
1,146 Graph Sketches: Sparsification, Spanners, and Subgraphs 2012 PODS 0.00011984702
2,576 Optimal Sampling from Sliding Windows 2009 PODS 8.3964437e-05
4,370 Fast Manhattan Sketches in Data Streams 2010 PODS 6.7387541e-05
5,733 A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets 2006 VLDB 6.1062071e-05
5,891 Maintaining Bernoulli Samples over Evolving Multisets 2007 PODS 6.0495154e-05
10,646 Perfect Sampling in Turnstile Streams Beyond Small Moments 2025 PODS 5.093636e-05
10,651 Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces 2025 PODS 5.093636e-05
11,519 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS 5.093636e-05
11,897 Distinct Sampling on Streaming Data with Near-Duplicates 2018 PODS 5.093636e-05
Previous Page 1 / 1 Next

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.00052982574
54 On Random Sampling over Joins 1999 SIGMOD 0.00040810225
122 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00031260115
149 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00029226907
230 Gigascope: A Stream Database for Network Applications 2003 SIGMOD 0.00023891474
235 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00023783792
255 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00023174541
288 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00022296371
505 TelegraphCQ: Continuous Dataflow Processing 2003 SIGMOD 0.00017285498
508 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00017275873
838 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.0001370404
1,274 Querying and Mining Data Streams: You Only Get One Look 2002 SIGMOD 0.00011377527
1,888 Aurora: A Data Stream Management System 2003 SIGMOD 9.5338565e-05
3,044 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.820774e-05
3,197 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD 7.6439415e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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