Randomized Computations on Large Data Sets: Tight Lower Bounds
Summary: Establishes tight Ω(log N) lower bounds on random external-memory accesses for randomized one-sided Monte Carlo algorithms for set/multiset equality and checksort in a model with free sequential scans and parallel external devices. Infers Ω(log N) bounds for Las Vegas evaluation of some XQuery/XPath/relational-algebra queries when internal memory ≤ O(√N/ log N). (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Martin Grohe (Humboldt University of Berlin)
- 2. André Hernich (Humboldt University of Berlin)
- 3. Nicole Schweikardt (Humboldt University of Berlin)
BibTeX Citation
@inproceedings{grohe_pods06,
address = {New York, NY, USA},
series = {{PODS} '06},
title = {{Randomized Computations on Large Data Sets: Tight Lower Bounds}},
url = {https://dl.acm.org/doi/10.1145/1142351.1142387},
doi = {10.1145/1142351.1142387},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Grohe, Martin and Hernich, André and Schweikardt, Nicole},
year = {2006}
}Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,488 | Machine Models and Lower Bounds for Query Processing | 2007 | PODS | 5.4153038e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 4 of 4 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 26 | Models and Issues in Data Stream Systems | 2002 | PODS | 0.00052982574 |
| 3,659 | On the Memory Requirements of XPath Evaluation over XML Streams | 2004 | PODS | 7.2176232e-05 |
| 5,247 | Buffering in Query Evaluation over XML Streams | 2005 | PODS | 6.3009176e-05 |
| 12,723 | Lower Bounds for Sorting with Few Random Accesses to External Memory | 2005 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 817 | Processing Complex Aggregate Queries over Data Streams | 2002 | SIGMOD |
| 2 | 12,467 | Conditioning and Aggregating Uncertain Data Streams: Going Beyond Expectations | 2010 | VLDB |
| 3 | 14,482 | EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract) | 1984 | SIGMOD |
| 4 | 3,659 | On the Memory Requirements of XPath Evaluation over XML Streams | 2004 | PODS |
| 5 | 4,472 | Relative Error Streaming Quantiles | 2021 | PODS |
| 6 | 443 | Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets | 1999 | SIGMOD |
| 7 | 644 | The Complexity of Query Reliability | 1998 | PODS |
| 8 | 1,656 | Characterizing Memory Requirements for Queries over Continuous Data Streams | 2002 | PODS |
| 9 | 2,777 | Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration | 2020 | PODS |
| 10 | 12,723 | Lower Bounds for Sorting with Few Random Accesses to External Memory | 2005 | PODS |