Tight Lower Bounds for Query Processing on Streaming and External Memory Data

Details Tight Lower Bounds for Query Processing on Streaming and External Memory Data Tight Lower Bounds for Query Processing on Streaming and External Memory Data

2005-04-29

arxiv.org/abs/cs/0505002v1

Computer Science

Databases

25 pages, 4 figures, to appear in Proc. ICALP 2005; extended version with appendix

Scientific paper

We study a clean machine model for external memory and stream processing. We show that the number of scans of the external data induces a strict hierarchy (as long as work space is sufficiently small, e.g., polylogarithmic in the size of the input). We also show that neither joins nor sorting are feasible if the product of the number $r(n)$ of scans of the external memory and the size $s(n)$ of the internal memory buffers is sufficiently small, e.g., of size $o(\sqrt[5]{n})$. We also establish tight bounds for the complexity of XPath evaluation and filtering.

Affiliated with

Also associated with

No associations

Rating

Tight Lower Bounds for Query Processing on Streaming and External Memory Data 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 Tight Lower Bounds for Query Processing on Streaming and External Memory Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight Lower Bounds for Query Processing on Streaming and External Memory Data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-678425