DBScholar

Back to papers

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
hda2df881b9256ee5
Venue
PODS
Year
2011
Pagerank
0.00013788161
Overall Rank
805 | 94.60%
DOI
10.1145/1989284.1989289

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{jowhari_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989289},
        doi = {10.1145/1989284.1989289},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jowhari, Hossein and Saglam, Mert and Tardos, Gábor},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank Citing Paper Year Venue Pagerank
1,170 Graph Sketches: Sparsification, Spanners, and Subgraphs 2012 PODS 0.00011720594
4,848 Vertex and Hyperedge Connectivity in Dynamic Graph Streams 2015 PODS 6.3794281e-05
5,197 Weighted Reservoir Sampling from Distributed Streams 2019 PODS 6.2316663e-05
5,237 Better Algorithms for Counting Triangles in Data Streams 2016 PODS 6.2153078e-05
5,780 Data Streams with Bounded Deletions 2018 PODS 5.9949139e-05
6,398 BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory 2017 PODS 5.7971271e-05
6,969 Triangle and Four Cycle Counting in the Data Stream Model 2020 PODS 5.6289911e-05
7,703 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 5.4728588e-05
8,442 Streaming Algorithms for Measuring H-Impact 2017 PODS 5.3324907e-05
10,391 On Sketching Trimmed Statistics 2026 PODS 4.9769913e-05
10,397 Tight Lower Bounds for l2 Sampling 2026 PODS 4.9769913e-05
10,400 Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond 2026 PODS 4.9769913e-05
10,518 Sublime: Sublinear Error & Space for Unbounded Skewed Streams 2026 SIGMOD 4.9769913e-05
11,098 Perfect Sampling in Turnstile Streams Beyond Small Moments 2025 PODS 4.9769913e-05
11,099 Private Synthetic Data Generation in Bounded Memory 2025 PODS 4.9769913e-05
11,103 Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces 2025 PODS 4.9769913e-05
11,477 Streaming Algorithms with Few State Changes 2024 PODS 4.9769913e-05
11,697 Applications of Sketching and Pathways to Impact 2023 PODS 4.9769913e-05
11,834 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS 4.9769913e-05
11,951 Frequent Elements with Witnesses in Data Streams 2021 PODS 4.9769913e-05
12,200 Distributed Statistical Estimation of Matrix Products with Applications 2018 PODS 4.9769913e-05
12,203 Distinct Sampling on Streaming Data with Near-Duplicates 2018 PODS 4.9769913e-05
Previous Page 1 / 1 Next

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
494 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017379171
1,636 Space-optimal Heavy Hitters with Strong Error Bounds 2009 PODS 0.00010011919
2,173 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 8.9197633e-05
2,221 Optimal Sampling From Distributed Streams 2010 PODS 8.8114999e-05
2,626 Optimal Sampling from Sliding Windows 2009 PODS 8.205667e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 12,203 Distinct Sampling on Streaming Data with Near-Duplicates 2018 PODS
2 5,780 Data Streams with Bounded Deletions 2018 PODS
3 11,098 Perfect Sampling in Turnstile Streams Beyond Small Moments 2025 PODS
4 1,636 Space-optimal Heavy Hitters with Strong Error Bounds 2009 PODS
5 11,690 Towards Better Bounds for Finding Quasi-Identifiers * 2023 PODS
6 5,326 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS
7 6,573 An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems 2016 PODS
8 11,834 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS
9 10,400 Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond 2026 PODS
10 10,397 Tight Lower Bounds for l2 Sampling 2026 PODS