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 |