ATTENTION: The software behind KU ScholarWorks is being upgraded to a new version. Starting July 15th, users will not be able to log in to the system, add items, nor make any changes until the new version is in place at the end of July. Searching for articles and opening files will continue to work while the system is being updated. If you have any questions, please contact Marianne Reed at .

Show simple item record

dc.contributor.authorVitter, Jeffrey Scott
dc.identifier.citationJ. 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.
dc.descriptionThe original publication is available at
dc.description.abstractThe 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.
dc.publisherSpringer Verlag
dc.titleOnline Data Structures in External Memory
kusw.kuauthorVitter, Jeffrey Scott
kusw.oaversionScholarly/refereed, author accepted manuscript
kusw.oapolicyThis item meets KU Open Access policy criteria.

Files in this item


This item appears in the following Collection(s)

Show simple item record