Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems

Summary: Near-optimal Lp-samplers: O(ε^{-p} log^2 n) space for p∈(1,2), O(ε^{-1} log^2 n) for p∈(0,1), and an O(log^2 n)-bit zero-error L0-sampler. Leads to O(log^2 n)-space duplicate detection and Ω(log^2 n) lower bounds via augmented-indexing, matching upper bounds for sampling, duplicates, and heavy hitters. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1534
Venue: PODS
Year: 2011
Pagerank: 0.00011576632
Overall Rank: 1,245 | 91.35%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,339	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.0001120043
4,930	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	6.5040855e-05
5,018	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	6.4668518e-05
6,157	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	6.0326862e-05
6,619	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	5.8801548e-05
7,083	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	5.7603009e-05
7,972	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.5699277e-05
10,365	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	5.1725247e-05
10,366	Private Synthetic Data Generation in Bounded Memory	2025	PODS	5.1725247e-05
10,370	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	5.1725247e-05
10,905	Streaming Algorithms with Few State Changes	2024	PODS	5.1725247e-05
11,172	Applications of Sketching and Pathways to Impact	2023	PODS	5.1725247e-05
11,322	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	5.1725247e-05
11,443	Frequent Elements with Witnesses in Data Streams	2021	PODS	5.1725247e-05
11,773	Streaming Algorithms for Measuring H-Impact	2017	PODS	5.1725247e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
536	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017011367
1,643	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010200355
2,308	Optimal Sampling From Distributed Streams	2010	PODS	8.858717e-05
2,422	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.6722118e-05
2,934	Optimal Sampling from Sliding Windows	2009	PODS	8.01483e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,370	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	5.1725247e-05
5,592	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS	6.222801e-05
4,124	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS	6.9485903e-05
2,621	Independent Range Sampling	2014	PODS	8.3985309e-05
10,365	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	5.1725247e-05
1,643	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010200355
11,165	Towards Better Bounds for Finding Quasi-Identifiers *	2023	PODS	5.1725247e-05
5,556	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	6.2357201e-05
6,321	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.9738105e-05
11,322	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	5.1725247e-05