Sketching Unaggregated Data Streams for Subpopulation-Size Queries

Summary: Streaming sketches for unaggregated packet streams that provide unbiased, post-hoc estimators of flow subpopulation sizes (e.g., per-application or per-AS) without per-flow state. Introduces step sample-and-hold that substantially beats Cisco sampled NetFlow and approaches pre-aggregated accuracy. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1434
Venue: PODS
Year: 2007
Pagerank: 5.538404e-05
Overall Rank: 7,815 | 46.39%
DOI: 10.1145/1265530.1265566

Incoming Non-self Citations Over Time

Authors

1. Edith Cohen (AT&T)
2. Nick Duffield (AT&T)
3. Haim Kaplan (Tel Aviv University)
4. Carsten Lund (AT&T)
5. Mikkel Thorup (AT&T)

BibTeX Citation

@inproceedings{cohen_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Sketching Unaggregated Data Streams for Subpopulation-Size Queries}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265566},
        doi = {10.1145/1265530.1265566},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cohen, Edith and Duffield, Nick and Kaplan, Haim and Lund, Carsten and Thorup, Mikkel},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	8.0058242e-05
3,481	Tighter Estimation using Bottom k Sketches	2008	VLDB	7.376137e-05
12,538	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00077458002
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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,697	Sketching Probabilistic Data Streams	2007	SIGMOD
2	1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB
3	4,623	Multiple Aggregations Over Data Streams	2005	SIGMOD
4	2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB
5	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
6	12,724	Join-Distinct Aggregate Estimation over Update Streams	2005	PODS
7	2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD
8	5,193	Sampling Algorithms in a Stream Operator	2005	SIGMOD
9	817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD
10	12,538	Composable, Scalable, and Accurate Weight Summarization of Unaggregated Data Sets	2009	VLDB