X-tree

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject. Please help improve the article with a good introductory style.

This article is about a tree data structure for storing data in multiple dimensions. For the XTree file manager, see XTree.

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

[edit] External links

• The X-tree: An Index Structure for High-Dimensional Data
• A X-tree reference implementation in C++, written by Hans-Peter Kriegel