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:
# Each node contains a K-dimensional record and has associated an arbitrary discriminant ''j ∈ ''.
# For every node with key ''x'' and discriminant ''j'', the following invariant is true: any record in the right subtree with key y satisfies ''y_j < x_j'' and any record in the left 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 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 is ,1sup>K, the bounding box of the left subtree's root is ,1× ... × ,y_i× ... × ,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

{{Reflist

Trees (data structures)