Relaxed k-d tree

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 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.[2]

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.

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)[3]

• 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