Lower bounds for processing data with few random accesses to external memory

ABSTRACT

We consider a scenario where we want to query a large dataset that is stored in external memory and does not fit into main memory. The most constrained resources in such a situation are the size of the main memory and the number of random accesses to external memory. We note that sequentially streaming data from external memory through main memory is much less prohibitive.

We propose an abstract model of this scenario in which we restrict the size of the main memory and the number of random accesses to external memory, but admit arbitrary sequential access. A distinguishing feature of our model is that it allows the usage of unlimited external memory for storing intermediate results, such as several hard disks that can be accessed in parallel.

In this model, we prove lower bounds for the problem of sorting a sequence of strings (or numbers), the problem of deciding whether two given sets of strings are equal, and two closely related decision problems. Intuitively, our results say that there is no algorithm for the problems that uses internal memory space bounded by N^1−ϵ and at most o(log N) random accesses to external memory, but unlimited “streaming access”, both for writing to and reading from external memory. (Here, N denotes the size of the input and ϵ is an arbitrary constant greater than 0.) We even permit randomized algorithms with one-sided bounded error. We also consider the problem of evaluating database queries and prove similar lower bounds for evaluating relational algebra queries against relational databases and XQuery and XPath queries against XML-databases.

REFERENCES

• 1: Gagan Aggarwal , Mayur Datar , Sridhar Rajagopalan , Matthias Ruhl, On the Streaming Model Augmented with a Sorting Primitive, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.540-549, October 17-19, 2004 [doi>10.1109/FOCS.2004.48]
• 2: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 3: Lars Arge , Peter Bro Miltersen, On showing lower bounds for external-memory computational geometry problems, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 4: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 5: Ziv Bar-Yossef , Marcus Fontoura , Vanja Josifovski, On the memory requirements of XPath evaluation over XML streams, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055584]
• 6: Ziv Bar-Yossef , Marcus Fontoura , Vanja Josifovski, Buffering in query evaluation over XML streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065195]
• 7: Paul Beame , Dang-Trinh Huynh-Ngoc, On the Value of Multiple Read/Write Streams for Approximating Frequency Moments, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.499-508, October 25-28, 2008 [doi>10.1109/FOCS.2008.52]
• 8: Paul Beame , T. S. Jayram , Atri Rudra, Lower bounds for randomized read/write stream algorithms, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250891]
• 9: Jian-er Chen , Chee-Keng Yap, Reversal complexity, SIAM Journal on Computing, v.20 n.4, p.622-638, Aug. 1991 [doi>10.1137/0220039]
• 10: Erdös, P., and Szekeres, G. 1935. A combinatorial problem in geometry. Compos. Math. 2, 463--470.
• 11: Martin Grohe , André Hernich , Nicole Schweikardt, Randomized computations on large data sets: tight lower bounds, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142387]
• 12: Grohe, M., Koch, C., and Schweikardt, N. 2005. The complexity of querying external memory and streaming data. In Proceedings of 15th International Symposium on Fundamentals of Computation Theory (FCT 2005). Lecture Notes in Computer Science, vol. 3623. Springer-Verlag, Berlin, Germany, 1--16.
• 13: Martin Grohe , Christoph Koch , Nicole Schweikardt, Tight lower bounds for query processing on streaming and external memory data, Theoretical Computer Science, v.380 n.1-2, p.199-217, July 2007 [doi>10.1016/j.tcs.2007.02.062]
• 14: Martin Grohe , Nicole Schweikardt, Lower bounds for sorting with few random accesses to external memory, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065197]
• 15: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 16: André Hernich , Nicole Schweikardt, Reversal complexity revisited, Theoretical Computer Science, v.401 n.1-3, p.191-205, July, 2008 [doi>10.1016/j.tcs.2008.04.026]
• 17: Ulrich Meyer , Peter Sanders , Jop Sibeyn, Algorithms for Memory Hierarchies, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 18: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 19: Munro, J. I., and Paterson, M. S. 1980. Selection and sorting with limited storage. Theoret. Comput. Sci. 12, 315--323.
• 20: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 21: Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley, Reading, MA.
• 22: Nicole Schweikardt, Machine models and lower bounds for query processing, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265537]
• 23: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 24: Wagner, K., and Wechsung, G. 1986. Computational Complexity. VEB Deutscher Verlag der Wissenschaften, Berlin, Germany.
• 25: World Wide Web Consortium. 2005. XML Path Language (XPath) 2.0. W3C Candidate Recommendation 3 November 2005. http://www.w3.org/TR/xpath20/.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Relational databases

General Terms:
Languages, Theory

Keywords:
Complexity, XML, data streams, query optimization, query processing, real-time data, semi-structured data