Loading...
A Framework for Index Bulk Loading and Dynamization
Agarwal, Pankaj K. Arge, Lars Procopiuc, Octavian Vitter, Jeffrey Scott
Agarwal, Pankaj K.
Arge, Lars
Procopiuc, Octavian
Vitter, Jeffrey Scott
Citations
Altmetric:
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.
Description
Date
2001
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Verlag
Files
Loading...
AAP01.pdf
Adobe PDF, 170.68 KB
Research Projects
Organizational Units
Journal Issue
Keywords
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