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.

Duke Authors

Cited Authors

  • Agarwal, PK; Arge, L; Procopiuc, O; Vittery, JS

Published Date

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

Citation Source

  • Scopus