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 mreed@ku.edu .

Show simple item record

dc.contributor.authorVitter, Jeffrey Scott
dc.date.accessioned2011-03-21T20:35:16Z
dc.date.available2011-03-21T20:35:16Z
dc.date.issued1999
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. http://dx.doi.org/10.1007/3-540-48523-6_10
dc.identifier.urihttp://hdl.handle.net/1808/7227
dc.descriptionThe original publication is available at www.springerlink.com
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.language.isoen_US
dc.publisherSpringer Verlag
dc.titleOnline Data Structures in External Memory
dc.typeArticle
kusw.kuauthorVitter, Jeffrey Scott
kusw.oastatusfullparticipation
dc.identifier.doi10.1007/3-540-48523-6_10
kusw.oaversionScholarly/refereed, author accepted manuscript
kusw.oapolicyThis item meets KU Open Access policy criteria.
dc.rights.accessrightsopenAccess


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record