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

Summary: Formalizes management and mining of inverse distributions on data streams, showing forward and inverse views diverge under approximation. Proposes a dynamic inverse-sampling framework with provable guarantees for quantiles, equidepth histograms, heavy hitters, and rare-item counts, validated on network data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9307
Venue: VLDB
Year: 2005
Pagerank: 9.1073603e-05
Overall Rank: 2,282 | 84.13%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,040	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00014488943
1,094	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00014129658
2,789	Optimal Sampling from Sliding Windows	2009	PODS	8.1249652e-05
3,566	Fast Manhattan Sketches in Data Streams	2010	PODS	6.9629443e-05
6,190	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1645517e-05
6,286	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1280225e-05
10,353	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1945683e-05
10,358	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.1945683e-05
11,320	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.1945683e-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
18	On Random Sampling over Joins	1999	SIGMOD	0.00092385438
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072723062
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
308	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00028142852
323	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00027492196
378	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.0002497492
530	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00020803682
591	TelegraphCQ: Continuous Dataflow Processing	2003	SIGMOD	0.00019569071
865	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00015808172
1,222	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00013213129
2,182	Aurora: A Data Stream Management System	2003	SIGMOD	9.3449021e-05
3,102	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.5586568e-05
3,486	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0502199e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,080	Optimal Sampling From Distributed Streams	2010	PODS	9.5899129e-05
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
4,076	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4680854e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.3849295e-05
3,385	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.1580391e-05
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
11,833	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.1945683e-05
7,547	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS	4.7144329e-05
5,117	Sampling Algorithms in a Stream Operator	2005	SIGMOD	5.6825418e-05
12,108	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1945683e-05