{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:10:03Z","timestamp":1750255803004,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,5,1]],"date-time":"2009-05-01T00:00:00Z","timestamp":1241136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,5]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>\n            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            <jats:italic>N<\/jats:italic>\n            <jats:sup>1\u2212\u03b5<\/jats:sup>\n            and at most\n            <jats:italic>o<\/jats:italic>\n            (log\n            <jats:italic>N<\/jats:italic>\n            ) random accesses to external memory, but unlimited \u201cstreaming access\u201d, both for writing to and reading from external memory. (Here,\n            <jats:italic>N<\/jats:italic>\n            denotes the size of the input and \u03b5 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.\n          <\/jats:p>","DOI":"10.1145\/1516512.1516514","type":"journal-article","created":{"date-parts":[[2009,5,19]],"date-time":"2009-05-19T16:47:42Z","timestamp":1242751662000},"page":"1-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Lower bounds for processing data with few random accesses to external memory"],"prefix":"10.1145","volume":"56","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"Humboldt-Universit\u00e4t, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Hernich","sequence":"additional","affiliation":[{"name":"Goethe-Universit\u00e4t, Frankfurt am Main, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicole","family":"Schweikardt","sequence":"additional","affiliation":[{"name":"Goethe-Universit\u00e4t, Frankfurt am Main, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,5,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.48"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Arge L. and Miltersen P. 1999. On showing lower bounds for external memory computational geometry problems. In External Memory Algorithms and Visualization J. M. Abello and J. S. Vitter Eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS New York 139--159.   Arge L. and Miltersen P. 1999. On showing lower bounds for external memory computational geometry problems. In External Memory Algorithms and Visualization J. M. Abello and J. S. Vitter Eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS New York 139--159.","DOI":"10.1090\/dimacs\/050\/08"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055584"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065195"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.52"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250891"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220039"},{"key":"e_1_2_1_10_1","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u00f6s P.","year":"1935","journal-title":"Compos. Math."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142387"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11537311_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.062"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065197"},{"volume":"50","volume-title":"Eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science","author":"Henzinger M. R.","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.026"},{"volume":"2625","volume-title":"Algorithms for Memory Hierarchies. Lecture Notes in Computer Science","author":"Meyer U.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge MA.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge MA.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90061-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_2_1_21_1","unstructured":"Papadimitriou C. H. 1994. Computational Complexity. Addison-Wesley Reading MA.  Papadimitriou C. H. 1994. Computational Complexity. Addison-Wesley Reading MA."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265537"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/384192.384193"},{"key":"e_1_2_1_24_1","unstructured":"Wagner K. and Wechsung G. 1986. Computational Complexity. VEB Deutscher Verlag der Wissenschaften Berlin Germany.  Wagner K. and Wechsung G. 1986. Computational Complexity. VEB Deutscher Verlag der Wissenschaften Berlin Germany."},{"key":"e_1_2_1_25_1","unstructured":"World Wide Web Consortium. 2005. XML Path Language (XPath) 2.0. W3C Candidate Recommendation 3 November 2005. http:\/\/www.w3.org\/TR\/xpath20\/.  World Wide Web Consortium. 2005. XML Path Language (XPath) 2.0. W3C Candidate Recommendation 3 November 2005. http:\/\/www.w3.org\/TR\/xpath20\/."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1516512.1516514","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1516512.1516514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:06Z","timestamp":1750253406000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1516512.1516514"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["10.1145\/1516512.1516514"],"URL":"https:\/\/doi.org\/10.1145\/1516512.1516514","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2009,5]]},"assertion":[{"value":"2006-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}