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 .
A Framework for Index Bulk Loading and Dynamization
dc.contributor.author | Agarwal, Pankaj K. | |
dc.contributor.author | Arge, Lars | |
dc.contributor.author | Procopiuc, Octavian | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-21T19:00:03Z | |
dc.date.available | 2011-03-21T19:00:03Z | |
dc.date.issued | 2001 | |
dc.identifier.citation | P. K. Agarwal, L. Arge, O. Procopiuc, and J. S. Vitter. “A Framework for Index Bulk Loading and Dynamization,” Proceedings of the 28th Annual International Colloquium on Automata, Languages, and Programming (ICALP ’01), Crete, Greece, July 2001, published in Lecture Notes in Computer Science, 2076, Springer, Berlin, Germany, 115–127. http://dx.doi.org/10.1007/3-540-48224-5_10 | |
dc.identifier.uri | http://hdl.handle.net/1808/7213 | |
dc.description.abstract | In this paper we investigate automated methods for externalizing internal memory data structures. We consider a class of balanced trees that we call weight-balanced partitioning trees (or wp-trees) for indexing a set of points in Rd. Well-known examples of wp-trees include fed-trees, BBD-trees, pseudo quad trees, and BAR trees. These trees are defined with fixed degree and are thus suited for internal memory implementations. Given an efficient wp-tree construction algorithm, we present a general framework for automatically obtaining a new dynamic external data structure. Using this framework together with a new general construction (bulk loading) technique of independent interest, we obtain data structures with guaranteed good update performance in terms of I /O transfers. Our approach gives considerably improved construction and update I/O bounds of e.g. fed-trees and BBD-trees. | |
dc.language.iso | en_US | |
dc.publisher | Springer Verlag | |
dc.title | A Framework for Index Bulk Loading and Dynamization | |
dc.type | Article | |
kusw.kuauthor | Scott, Jeffery Vitter | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1007/3-540-48224-5_10 | |
kusw.oaversion | Scholarly/refereed, author accepted manuscript | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess |