Relaxed k-d tree explained
| 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.[1]
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.[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 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 [0,1]K, the bounding box of the left subtree's root is [0,1] × ... × [0,y<sub>i</sub>] × ... × [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)[3]
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
Notes and References
- Book: Randomized K-Dimensional Binary Search Trees. Duch. Amalia. Estivill-Castro. Vladimir. Martínez. Conrado. 1998-12-14. Springer Berlin Heidelberg. 9783540653851. Chwa. Kyung-Yong. Lecture Notes in Computer Science. 198–209. en. 10.1007/3-540-49381-6_22. Ibarra. Oscar H.. 10.1.1.55.3293. registration.
- Duch. Amalia. Martínez. Conrado. Improving the Performance of Multidimensional Search Using Fingers. ACM Journal of Experimental Algorithmics. 2005. 10. 10.1145/1064546.1180615. 2130863. 23 August 2016.
- Book: Chwa. Kyung-Yong. Ibarra. Oscar H.. Algorithms and Computation: 9th International Symposium, ISAAC'98, Taejon, Korea, December 14-16, 1998, Proceedings. Springer. 9783540493815. 202–203. 23 August 2016. en. 2003-06-29.
