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
1533
Venue
PODS
Year
2011
Pagerank
0.0001410593
Overall Rank
777 | 94.68%
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,146 Graph Sketches: Sparsification, Spanners, and Subgraphs 2012 PODS 0.00011984702
4,739 Vertex and Hyperedge Connectivity in Dynamic Graph Streams 2015 PODS 6.5285049e-05
5,068 Weighted Reservoir Sampling from Distributed Streams 2019 PODS 6.3770298e-05
5,110 Better Algorithms for Counting Triangles in Data Streams 2016 PODS 6.3609746e-05
5,669 Data Streams with Bounded Deletions 2018 PODS 6.1278944e-05
6,275 BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory 2017 PODS 5.9299343e-05
6,873 Triangle and Four Cycle Counting in the Data Stream Model 2020 PODS 5.7495468e-05
8,106 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 5.4853605e-05
8,267 Streaming Algorithms for Measuring H-Impact 2017 PODS 5.4574671e-05
10,162 On Sketching Trimmed Statistics 2026 PODS 5.093636e-05
10,168 Tight Lower Bounds for l2 Sampling 2026 PODS 5.093636e-05
10,171 Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond 2026 PODS 5.093636e-05
10,295 Sublime: Sublinear Error & Space for Unbounded Skewed Streams 2026 SIGMOD 5.093636e-05
10,646 Perfect Sampling in Turnstile Streams Beyond Small Moments 2025 PODS 5.093636e-05
10,647 Private Synthetic Data Generation in Bounded Memory 2025 PODS 5.093636e-05
10,651 Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces 2025 PODS 5.093636e-05
11,123 Streaming Algorithms with Few State Changes 2024 PODS 5.093636e-05
11,375 Applications of Sketching and Pathways to Impact 2023 PODS 5.093636e-05
11,519 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS 5.093636e-05
11,638 Frequent Elements with Witnesses in Data Streams 2021 PODS 5.093636e-05
11,894 Distributed Statistical Estimation of Matrix Products with Applications 2018 PODS 5.093636e-05
11,897 Distinct Sampling on Streaming Data with Near-Duplicates 2018 PODS 5.093636e-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
482 An Optimal Algorithm for the Distinct Elements Problem 2010 PODS 0.00017772185
1,600 Space-optimal Heavy Hitters with Strong Error Bounds 2009 PODS 0.00010240222
2,128 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1271562e-05
2,178 Optimal Sampling From Distributed Streams 2010 PODS 9.0159538e-05
2,576 Optimal Sampling from Sliding Windows 2009 PODS 8.3964437e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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