Loading...
Online Data Structures in External Memory
Vitter, Jeffrey Scott
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
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.
Description
The original publication is available at www.springerlink.com
Date
1999
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Verlag
Research Projects
Organizational Units
Journal Issue
Keywords
Citation
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