Online Data Structures in External Memory
Vitter, Jeffrey Scott
Scholarly/refereed, author accepted manuscript
MetadataShow full item record
The data sets for many of today's computer applications are too large to t within the computer's internal memory and must instead be stored on external storage devices such as disks. A major performance bottleneck can be the input/output communication (or I/O) between the external and internal memories. In this paper we discuss a variety of online data structures for external memory, some very old and some very new, such as hashing (for dictionaries), B-trees (for dictionaries and 1-D range search), bu er trees (for batched dynamic problems), interval trees with weight-balanced B-trees (for stabbing queries), priority search trees (for 3-sided 2-D range search), and R-trees and other spatial structures. We also discuss several open problems along the way.
The original publication is available at www.springerlink.com
J. S. Vitter. “Online Data Structures in External Memory,” invited paper in Proceedings of the 6th Biannual Workshop on Algorithms and Data Structures (WADS ’99), Vancouver, Canada, August 1999, published in Lecture Notes in Computer Science, 1668, Springer, Berlin, Germany. Also appears as an invited paper in Proceedings of the 26th Annual International Colloquium on Automata, Languages, and Programming (ICALP ’99), Prague, Czech Republic, July 1999, published in Lecture Notes in Computer Science, 1644, Springer, Berlin, Germany, 119–133. http://dx.doi.org/10.1007/3-540-48523-6_10
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.