Bkd-tree: A dynamic scalable kd-tree


Journal Article

In this paper we propose a new index structure, called the Bkd-tree, for indexing large multi-dimensional point data sets. The Bkd-tree is an I/O-efficient dynamic data structure based on the kd-tree. We present the results of an extensive experimental study showing that unlike previous attempts on making external versions of the kd-tree dynamic, the Bkd-tree maintains its high space utilization and excellent query and update performance regardless of the number of updates performed on it. © Springer-Verlag Berlin Heidelberg 2003.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 2003

Published In

Volume / Issue

  • 2750 /

Start / End Page

  • 46 - 65

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Digital Object Identifier (DOI)

  • 10.1007/978-3-540-45072-6_4

Citation Source

  • Scopus