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=. 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 left subtree with key y satisfies yj < xj, and any record in the right subtree with key y satisfies yj ≥ xj.
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 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 K, the bounding box of the left subtree's root is ×... × ×... ×, and so on.
Supported queries
The average time complexities in a relaxed K-d tree with n records are:- Exact match queries: O
- Partial match queries: O, where:
- * s out of K attributes are specified
- * with 0 < f < 1, a real valued function of s/K
- Nearest neighbor queries: O