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: 9308
Venue: VLDB
Year: 2005
Pagerank: 9.1507118e-05
Overall Rank: 2,269 | 84.24%
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
922	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00015254436
1,117	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001386123
2,807	Optimal Sampling from Sliding Windows	2009	PODS	8.096649e-05
3,557	Fast Manhattan Sketches in Data Streams	2010	PODS	6.9711051e-05
6,192	Maintaining Bernoulli Samples over Evolving Multisets	2007	PODS	5.1596405e-05
6,285	A Dip in the Reservoir: Maintaining Sample Synopses of Evolving Datasets	2006	VLDB	5.1231886e-05
10,365	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1905499e-05
10,370	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.1905499e-05
11,322	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.1905499e-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.00092569117
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072660894
168	Approximate Frequency Counts over Data Streams	2002	VLDB	0.0003915627
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
324	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00027465124
380	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00024943236
531	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.0002079072
590	TelegraphCQ: Continuous Dataflow Processing	2003	SIGMOD	0.00019552343
874	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001568356
1,222	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00013205769
2,188	Aurora: A Data Stream Management System	2003	SIGMOD	9.3378116e-05
3,108	Processing Set Expressions over Continuous Update Streams	2003	SIGMOD	7.5547127e-05
3,491	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.0436671e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,068	Optimal Sampling From Distributed Streams	2010	PODS	9.638573e-05
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
4,080	Quantiles over Data Streams: An Experimental Study	2013	SIGMOD	6.4619407e-05
9,162	Estimating Quantiles from the Union of Historical and Streaming Data	2017	VLDB	4.380727e-05
831	Finding Frequent Items in Data Streams	2008	VLDB	0.00016094846
3,391	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.1427968e-05
11,841	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.1905499e-05
7,545	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS	4.7099128e-05
5,119	Sampling Algorithms in a Stream Operator	2005	SIGMOD	5.6774637e-05
12,116	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS	4.1905499e-05