Relaxed k-d tree

A relaxed K-d tree or relaxed K-dimensional tree is a data structure which is a variant of K-d trees. Like K-dimensional trees, a relaxed K-dimensional tree stores a set of n-multidimensional records, each one having a unique K-dimensional key x=(x₀,... ,x_{K−1}). Unlike K-d trees, in a relaxed K-d tree, the discriminants in each node are arbitrary. Relaxed K-d trees were introduced in 1998.

Definitions

A relaxed K-d tree for a set of K-dimensional keys is a binary tree in which:

1. Each node contains a K-dimensional record and has associated an arbitrary discriminant j ∈ {0,1,...,K − 1}.
2. For every node with key x and discriminant j, the following invariant is true: any record in the left subtree with key y satisfies y_j < x_j, and any record in the right subtree with key y satisfies y_j ≥ x_j.

If K = 1, a relaxed K-d tree is a binary search tree.

As in a K-d tree, a relaxed K-d tree of size n induces a partition of the domain D into n+1 regions, each corresponding to a leaf in the K-d tree. The bounding box (or bounds array) of a node {x,j} is the region of the space delimited by the leaf in which x falls when it is inserted into the tree. Thus, the bounding box of the root {y,i} is [0,1]^K, the bounding box of the left subtree's root is [0,1] × ... × [0,y_i] × ... × [0,1], and so on.

Supported queries

The average time complexities in a relaxed K-d tree with n records are:

• Exact match queries: O(log n)
• Partial match queries: O(n^{1−f(s/K)}), where:
• s out of K attributes are specified
• with 0 < f(s/K) < 1, a real valued function of s/K
• Nearest neighbor queries: O(log n)

See also

• k-d tree
• implicit k-d tree, a k-d tree defined by an implicit splitting function rather than an explicitly-stored set of splits
• min/max k-d tree, a k-d tree that associates a minimum and maximum value with each of its nodes

References