M. ADAM
An externalization of the k-d tree

Abstract. 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.

READ THE PDF