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 | |