An externalization of the k-d tree
External searching is a fundamental problem with many applications in relational, object-oriented, spatial and temporal databases. The k-d tree or the multi-dimensional binary search tree used for associative searching, developed by J. L. Bentley in 1975, is an internal memory data structure. In this paper we develop an externalization of the k-d tree which occupies linear space, answers an orthogonal range query in square root time and supports updates in logarithmic time amortized.
k-d tree b-tree orthogonal range searching indexing global rebuilding