A framework for index bulk loading and dynamization
Published
Conference Paper
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 RdWell-known examples of wp-trees include kdtrees, BBD-trees, pseudo-quad-trees, and BAR-trees. Given an efficient external wp-tree construction algorithm, we present a general framework for automatically obtaining a 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 for e.g. external kd-trees and BBD-trees. © 2011 Springer-Verlag Berlin Heidelberg.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; Arge, L; Procopiuc, O; Vittery, JS
Published Date
- January 1, 2001
Published In
Volume / Issue
- 2076 LNCS /
Start / End Page
- 115 - 127
Electronic International Standard Serial Number (EISSN)
- 1611-3349
International Standard Serial Number (ISSN)
- 0302-9743
International Standard Book Number 10 (ISBN-10)
- 3540422870
International Standard Book Number 13 (ISBN-13)
- 9783540422877
Digital Object Identifier (DOI)
- 10.1007/3-540-48224-5_10
Citation Source
- Scopus