Login
Login

Relaxed k-d tree

{{Short description|Multidimensional search tree for spatial coordinates.}}

{{DISPLAYTITLE:Relaxed k-d tree}}

{{Infobox data structure

|name= Relaxed k-d tree

|type= Multidimensional BST

|invented_by= Amalia Duch, Vladimir Estivill-Castro and Conrado Martínez

|invented_year= 1998

|space_avg= O(n)

|space_worst= O(n)

|search_avg= O(log n)

|search_worst= O(n)

|insert_avg= O(log n)

|insert_worst= O(n)

|delete_avg= O(log n)

|delete_worst= O(n)

}}

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.{{Cite book|title=Randomized K-Dimensional Binary Search Trees|last1=Duch|first1=Amalia|last2=Estivill-Castro|first2=Vladimir|last3=Martínez|first3=Conrado|date=1998-12-14|publisher=Springer Berlin Heidelberg|isbn=9783540653851|editor-last=Chwa|editor-first=Kyung-Yong|series=Lecture Notes in Computer Science|pages=[https://archive.org/details/algorithmscomput0000isaa/page/198 198–209]|language=en|doi=10.1007/3-540-49381-6_22|editor-last2=Ibarra|editor-first2=Oscar H.|citeseerx=10.1.1.55.3293|url-access=registration|url=https://archive.org/details/algorithmscomput0000isaa/page/198}}

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 yj < xj, and any record in the right subtree with key y satisfies yj ≥ xj.{{cite journal|last1=Duch|first1=Amalia|last2=Martínez|first2=Conrado|title=Improving the Performance of Multidimensional Search Using Fingers|journal=ACM Journal of Experimental Algorithmics|date=2005|volume=10|doi=10.1145/1064546.1180615|s2cid=2130863|url=http://www.cs.upc.edu/~conrado/research/papers/jea-dm05.pdf|accessdate=23 August 2016}}

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){{cite book|last1=Chwa|first1=Kyung-Yong|last2=Ibarra|first2=Oscar H.|title=Algorithms and Computation: 9th International Symposium, ISAAC'98, Taejon, Korea, December 14-16, 1998, Proceedings|publisher=Springer|isbn=9783540493815|pages=202–203|url=https://books.google.com/books?id=MhNqCQAAQBAJ&dq=Relaxed+k-d+tree+exact+match+queries&pg=PA202|accessdate=23 August 2016|language=en|date=2003-06-29}}

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}}

Category:Trees (data structures)