Sampling Algorithms in a Stream Operator

Summary: Introduces a generic stream sample operator for one-pass sampling and aggregations on high-speed data streams. Implemented in Gigascope for IP monitoring; evaluated on live traffic, enabling versatile, low-overhead support for stream-sampling algorithms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3681
Venue: SIGMOD
Year: 2005
Pagerank: 6.3238562e-05
Overall Rank: 5,193 | 64.38%
DOI: 10.1145/1066157.1066159

Incoming Non-self Citations Over Time

Authors

1. Theodore Johnson (AT&T)
2. S. Muthukrishnan (Rutgers University)
3. Irina Rozenbaum (Rutgers University)

BibTeX Citation

@inproceedings{johnson_sigmod05,
        title = {{Sampling Algorithms in a Stream Operator}},
        author = {Johnson, Theodore and Muthukrishnan, S. and Rozenbaum, Irina},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066159},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066159},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
819	Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters	2016	SIGMOD	0.00013815639
3,332	A Heartbeat Mechanism and its Application in Gigascope	2005	VLDB	7.5129799e-05
4,211	The Adversarial Robustness of Sampling	2020	PODS	6.8299006e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-05
12,538	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB	5.093636e-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
25	NiagaraCQ: A Scalable Continuous Query System for Internet Databases	2000	SIGMOD	0.00054667018
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00036378991
111	TelegraphCQ: Continuous Dataflow Processing for an Uncertain World	2003	CIDR	0.00032990214
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
150	Query Processing, Resource Management, and Approximation in a Data Stream Management System	2003	CIDR	0.00029208207
167	Monitoring Streams – A New Class of Data Management Applications	2002	VLDB	0.0002757283
230	Gigascope: A Stream Database for Network Applications	2003	SIGMOD	0.00023891474
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
3,044	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.820774e-05
4,925	Query Languages and Data Models for Database Sequences and Data Streams	2004	VLDB	6.442888e-05
5,916	Tables As a Paradigm for Querying and Restructuring	1996	PODS	6.0433046e-05
6,817	ATLAS: a Small but Complete SQL Extension for Data Mining and Data Streams	2003	VLDB	5.764503e-05
8,404	Adaptive Sampling for Geometric Problems over Data Streams	2004	PODS	5.4323688e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB
2	4,229	On Biased Reservoir Sampling in the Presence of Stream Evolution	2006	VLDB
3	2,988	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS
4	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
5	11,897	Distinct Sampling on Streaming Data with Near-Duplicates	2018	PODS
6	7,815	Sketching Unaggregated Data Streams for Subpopulation-Size Queries	2007	PODS
7	11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD
8	8,379	Sampling Big Ideas in Query Optimization	2023	PODS
9	2,178	Optimal Sampling From Distributed Streams	2010	PODS
10	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS