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.00014129658
Overall Rank: 1,094 | 92.40%
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,040	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00014488943
2,884	BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory	2017	PODS	7.9620506e-05
4,718	Weighted Reservoir Sampling from Distributed Streams	2019	PODS	5.9749691e-05
5,046	Better Algorithms for Counting Triangles in Data Streams	2016	PODS	5.7405307e-05
6,864	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS	4.9050236e-05
7,031	Vertex and Hyperedge Connectivity in Dynamic Graph Streams	2015	PODS	4.8561505e-05
8,203	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	4.5596344e-05
10,353	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1945683e-05
10,354	Private Synthetic Data Generation in Bounded Memory	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
10,901	Streaming Algorithms with Few State Changes	2024	PODS	4.1945683e-05
11,169	Applications of Sketching and Pathways to Impact	2023	PODS	4.1945683e-05
11,320	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.1945683e-05
11,440	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.1945683e-05
11,765	Streaming Algorithms for Measuring H-Impact	2017	PODS	4.1945683e-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
383	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00024820873
1,629	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00011085267
2,080	Optimal Sampling From Distributed Streams	2010	PODS	9.5899129e-05
2,282	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1073603e-05
2,789	Optimal Sampling from Sliding Windows	2009	PODS	8.1249652e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,358	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.1945683e-05
5,066	Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem	2017	PODS	5.7223891e-05
2,749	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS	8.1773535e-05
2,203	Independent Range Sampling	2014	PODS	9.2981095e-05
10,353	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1945683e-05
1,629	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00011085267
11,162	Towards Better Bounds for Finding Quasi-Identifiers *	2023	PODS	4.1945683e-05
5,956	A Tight Lower Bound for Comparison-Based Quantile Summaries	2020	PODS	5.2566971e-05
6,418	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.0696932e-05
11,320	Truly Perfect Samplers for Data Streams and Sliding Windows	2022	PODS	4.1945683e-05