Randomized Computations on Large Data Sets: Tight Lower Bounds

Details Randomized Computations on Large Data Sets: Tight Lower Bounds Randomized Computations on Large Data Sets: Tight Lower Bounds

2007-03-15

arxiv.org/abs/cs/0703081v1

Computer Science

Databases

29 pages, 2 figures, full version of PODS'06 paper

Scientific paper

We study the randomized version of a computation model (introduced by Grohe, Koch, and Schweikardt (ICALP'05); Grohe and Schweikardt (PODS'05)) that restricts random access to external memory and internal memory space. Essentially, this model can be viewed as a powerful version of a data stream model that puts no cost on sequential scans of external memory (as other models for data streams) and, in addition, (like other external memory models, but unlike streaming models), admits several large external memory devices that can be read and written to in parallel. We obtain tight lower bounds for the decision problems set equality, multiset equality, and checksort. More precisely, we show that any randomized one-sided-error bounded Monte Carlo algorithm for these problems must perform Omega(log N) random accesses to external memory devices, provided that the internal memory size is at most O(N^(1/4)/log N), where N denotes the size of the input data. From the lower bound on the set equality problem we can infer lower bounds on the worst case data complexity of query evaluation for the languages XQuery, XPath, and relational algebra on streaming data. More precisely, we show that there exist queries in XQuery, XPath, and relational algebra, such that any (randomized) Las Vegas algorithm that evaluates these queries must perform Omega(log N) random accesses to external memory devices, provided that the internal memory size is at most O(N^(1/4)/log N).

Affiliated with

Also associated with

No associations

Rating

Randomized Computations on Large Data Sets: Tight Lower Bounds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Randomized Computations on Large Data Sets: Tight Lower Bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized Computations on Large Data Sets: Tight Lower Bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-363616