Built independently by an author, for readers. Read the story and support ChapterPal
ChapterPal Logo
Log inSign up

keyword

X-tree

An X-tree, or extended tree, is a spatial index data structure designed to store and query multidimensional and high-dimensional data efficiently. Extending traditional structures such as the R-tree and R*-tree, it addresses the performance degradation caused by overlapping bounding regions that naturally worsens as dimensionality increases. To mitigate this issue, the X-tree employs a specialized split algorithm that prioritizes minimizing bounding box overlap and introduces supernodes, which are enlarged directory nodes created when splitting would produce excessive overlap. By using supernodes instead of forced splits, the X-tree selectively transitions between a hierarchical tree structure and a linear search layout in high-overlap regions, thereby maintaining efficient retrieval times for complex spatial and point datasets.

1 item

The X-tree : An Index Structure for High-Dimensional Data

The X-tree : An Index Structure for High-Dimensional Data

S. Berchtold, D. Keim, H. Kriegel

OrganizationsLudwig Maximilian University of Munich

Why you should read this

Introduces the X-tree, an efficient high-dimensional indexing structure that avoids bounding-box overlap by combining an overlap-minimizing split algorithm with variable-sized supernodes to outperform standard R*-trees and TV-trees by orders of magnitude.

In this paper, we propose a new method for indexing large amounts of point and spatial data in high-dimensional space. An analysis shows that index structures such as the R*-tree are not adequate for indexing high-dimensional data sets. The major problem of R-tree-based index structures is the overlap of the bounding boxes in the directory, which increases with growing dimension. To avoid this problem, we introduce a new organization of the directory which uses a split algorithm minimizing overlap and additionally utilizes the concept of supernodes. The basic idea of overlap-minimizing split and supernodes is to keep the directory as hierarchical as possible, and at the same time to avoid splits in the directory that would result in high overlap. Our experiments show that for high-dimensional data, the X-tree outperforms the well-known R*-tree and the TV-tree by up to two orders of magnitude.

Added

2026-09-24