Harman Patil (Editor)

Relaxed k d tree

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit
Type
  
Multidimensional BST

Average
  
Worst Case

O(log n)
  
O(n)

Invented
  
1998

O(n)
  
O(n)

Invented by
  
Amalia Duch, Vladimir Estivill-Castro and Conrado Martínez

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=(x0,... ,xK−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.

Contents

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 right subtree with key y satisfies yj < xj and any record in the left subtree with key y satisfies yj ≥ xj.

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,yi] × ... × [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(n1−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)

    • References

    Relaxed k-d tree Wikipedia
    (Text) CC BY-SA