X-tree - Computer Science | Wiki eduNitas.com

In computer science, an X-tree is an index tree structure based on the R-tree used for storing data in many dimensions. It differs from R-trees, R+-trees and R*-trees because it emphasizes prevention of overlap in the bounding boxes, which increasingly becomes a problem in high dimensions. In cases where nodes cannot be split without preventing overlap, the node split will be deferred, resulting in super-nodes. In extreme cases, the tree will linearize, which defends against worst-case behaviors observed in some other data structures.

References

Berchtold, Stefan; Keim, Daniel A.; Kriegel, Hans-Peter (1996). "The X-tree: An Index Structure for High-Dimensional Data". Proceedings of the 22nd VLDB Conference (Mumbai, India): 28–39.

Trees in computer science

Binary trees	Binary search tree (BST) Cartesian tree MVP Tree Top tree T-tree

Self-balancing binary search trees	AA tree AVL tree LLRB tree Red–black tree Scapegoat tree Splay tree Treap

B-trees	B+ tree B*-tree B^x-tree UB-tree 2-3 tree 2-3-4 tree (a,b)-tree Dancing tree Htree

Tries	Suffix tree Radix tree Ternary search tree X-fast trie Y-fast trie

Binary space partitioning (BSP) trees	Quadtree Octree k-d tree Implicit k-d tree VP tree

Non-binary trees	Exponential tree Fusion tree Interval tree PQ tree Range tree SPQR tree Van Emde Boas tree

Spatial data partitioning trees	R-tree R+ tree R* tree X-tree M-tree Segment tree Hilbert R-tree Priority R-tree

Other trees	Heap Hash calendar Hash tree Finger tree Order statistic tree Metric tree Cover tree BK-tree Doubly chained tree iDistance Link-cut tree Fenwick tree Log-structured merge-tree