Average case analysis of region search in balanced k-d trees

In this paper a fiie is considered to be a collection of records, each of which is an ordered k-tuple of values,Each component of a record is called a key.

Abstract

In this paper a fiie is considered to be a collection of records, each of which is an ordered k-tuple of values (~0, rl, r2, . . . . rk). Each component of a record is called a key. Given a file we want to retrieve records according to the specification of a query. A simple query specifies a value for each key. A part&&match que,g specifies only s key values, leaving unspecified (k s) keys. A region query specifies for each key i, a range of values (I& ui). Similarly we call a p&al region query, one which specifies intervals only for s of the k keys. A k-d tree is a binary tree, used for storvng the records of a file. For each node we choose one of the keys to be the discriminating key or the discriminator of the node. The value of the discriminator of the node is used for partitioning the set of records that are stored in the descendants of the node. All records with this particular key less than the discriminator value go to the left subtree of the node, and all the others go to the right subtree. Following Bentley [ 1) we choose the lp mod k]th key as the discriminator of every node at level p. Associated with every node of the tree, we have a region of the k-dimensional space, where all of its descendants must lie. This region is defined by a set of bounds on the key values of the prlssible descendants of the node.