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

S. BerchtoldD. KeimH. Kriegel

article2001VLDB1,612 citations

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.

Listen

Modern database applications across multimedia retrieval, molecular biology, and computer-aided design increasingly rely on high-dimensional feature vectors to index large collections of data. Standard tree-based spatial indexes, particularly the widely used R*-tree, suffer severe performance degradation when applied to data with more than a few dimensions. The article addresses this operational bottleneck by analyzing why existing indexing methods fail in higher dimensions and introducing the X-tree (Extended Node Tree), a hybrid index structure designed to maintain efficient point and spatial data retrieval as dimensionality grows.

The main objective of the article is to demonstrate that the performance collapse in conventional spatial indexes stems from directory boundary overlap, and to introduce and evaluate the X-tree as an alternative structure that minimizes overlap through specialized split algorithms and variable-sized directory nodes called supernodes.

To evaluate this solution, the authors conducted extensive empirical benchmarking using both synthetic uniform datasets and real-world datasets, including polygon shape descriptors and computer-aided design spatial objects. The tests spanned dimensions ranging from 2 to 16, index sizes up to 100 megabytes per test dataset across a total disk footprint of roughly 10 gigabytes, and compared the X-tree against both the R*-tree and the TV-tree under point and nearest-neighbor search workloads.

The findings show that directory bounding box overlap in standard R*-trees increases rapidly, reaching approximately 80% to 90% at 4 to 5 dimensions and approaching 100% beyond 6 to 10 dimensions, forcing search queries to scan nearly every directory branch. By deferring splits that produce excessive overlap and instead forming sequential supernodes, the X-tree outperformed the R*-tree by up to two orders of magnitude, executing point queries up to 450 times faster and nearest-neighbor queries 10 to 20 times faster in 16 dimensions. Compared to the TV-tree, the X-tree achieved search speedups between 4 and 12 times while delivering data insertion rates up to 8 times faster than the R*-tree and 30 times faster than the TV-tree.

These results indicate that systems relying on high-dimensional similarity searches can dramatically reduce disk input/output bottlenecks and central processing unit query overhead by adopting hybrid hierarchical-linear index structures. Rather than suffering the severe latency penalties of random disk access across overlapping tree nodes, the X-tree provides robust scalability as database size grows logarithmically, ensuring that high-dimensional search applications remain computationally feasible and cost-effective.

Organizations handling high-dimensional vector search should consider adopting overlap-minimizing indexing mechanisms like the X-tree in place of traditional multi-dimensional trees. For practical deployments, directory node replacement policies should prioritize retaining supernodes in main memory to optimize cache efficiency. The article notes ongoing development of a parallelized implementation of the X-tree and specialized nearest-neighbor algorithms to further accelerate search speeds on very large and highly complex datasets.

The evaluations were conducted on data up to 16 dimensions and test database sizes up to 100 megabytes, which fully demonstrated the structural advantages of the design. However, system architects should account for increased supernode sizes in extremely high dimensions or with extended spatial shapes, where speed advantages over traditional structures are somewhat lower than with pure point data.

Ludwig Maximilian University of Munich high dimensional data index structure spatial data X-tree high-dimensional data index structure

elki-project/elki Berchtold et al (2001).pdf

Paper: The R*-tree: an efficient and robust access method for points and rectangles, Norbert Beckmann et al. (1990). Introduces the R*-tree and its overlap-minimization heuristics, which serve as the direct baseline that the X-tree extends and modifies to handle high-dimensional spaces.
Paper: R-trees: a dynamic index structure for spatial searching, Antonin Guttman (1984). Presents the foundational spatial access method and bounding-box hierarchy upon which the entire family of R-tree variants, including the X-tree, is built.
Paper: Nearest neighbor queries, N. Roussopoulos et al. (1995). Establishes the standard branch-and-bound nearest-neighbor search algorithms on spatial index trees that the X-tree adopts and benchmarks against.
Paper: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Roger Weber et al. (1998). Provides the formal analysis demonstrating why hierarchical space-partitioning structures collapse in high dimensions, supplying the theoretical context for the X-tree's hybrid design.
Paper: M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Paolo Ciaccia et al. (1997). Offers key foundational background on dynamic indexing for similarity search in higher dimensions within the generalized search tree framework.
Paper: Similarity Search in High Dimensions via Hashing, Aristides Gionis et al. (1999). Introduces locality-sensitive hashing as a non-tree alternative for high-dimensional nearest-neighbor retrieval, framing the trade-offs between exact tree structures and approximate hashing.

Paper: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Alexandr Andoni et al. (2008). Advances high-dimensional similarity search beyond exact tree indexes like the X-tree by establishing near-optimal locality-sensitive hashing for approximate retrieval.
Paper: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, Yu. A. Malkov et al. (2016). Develops hierarchical graph-based indexing to overcome the scalability bottlenecks of tree-based structures in high-dimensional nearest-neighbor search.
Paper: DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node, Suhas Jayaram Subramanya et al. (2019). Scales high-dimensional similarity search to billion-point datasets by optimizing graph indexes for secondary storage, progressing past disk-based tree architectures.
Paper: Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval, Yunchao Gong et al. (2013). Applies vector quantization and binary hashing to compress high-dimensional feature spaces, addressing memory and retrieval efficiency from a complementary representation perspective.
Paper: Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search, Hervé Jégou et al. (2008). Combines binary embeddings with inverted file indexing to scale high-dimensional visual feature searches to millions of images.

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

Abstract

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.

Topics

high dimensional data index structure spatial data

Keywords

X-tree high-dimensional data index structure overlap-free split dimension nearest neighbor queries point queries extended spatial data

1. Introduction
2. Problems of (R-tree-based) Index Structures in High-Dimensional Space
2.1 Definition of Overlap
2.2 Experimental Evaluation of Overlap in R*-tree Directories
3. The X-tree
3.1 Structure of the X-tree
3.2 Algorithms
3.3 Determining the Overlap-Minimal Split
4. Performance Evaluation
5. Conclusions
Acknowledgment
References

Knowls

Knowl 1 — X-tree Hybrid Directory Structure and Supernodes
model/method
The X-tree (eXtended node tree) is a multidimensional spatial index designed to prevent performance degradation caused by high directory overlap in high-dimensional spaces. The tree consists of three node types:
1. Data nodes: Leaf nodes storing rectilinear minimum bounding rectangles (MBRs) paired with pointers to raw spatial or point objects.
2. Normal directory nodes: Standard internal nodes of size equal to the disk block size, storing sub-MBRs and pointers to child directory or data nodes.
3. Supernodes: Variable-sized directory nodes spanning an integer multiple $m \ge 2$ of the disk block size stored in contiguous disk pages.
The X-tree organizes its directory as a hybrid between a hierarchical tree and a flat linear array. In low dimensions with low overlap, the directory remains strictly hierarchical (like an $\text{R}^*$ -tree). In high dimensions where any directory split would produce intolerable bounding-box overlap, splits are omitted and nodes are converted into or expanded as supernodes. In the extreme case of very high dimensionality or extreme overlap, the directory degenerates into a single root supernode that is scanned linearly.

When memory space is constrained, replacement of cached nodes is governed by a priority function:

$\text{Priority} = c_t \cdot \text{type} + c_l \cdot \text{level} + c_s \cdot \text{size}$

where $\text{type}$ distinguishes normal directory nodes from supernodes, $\text{level}$ is the tree level, $\text{size}$ is the block count, and the weighting constants satisfy $c_t \gg c_l \approx c_s$ to favor retaining supernodes and higher levels in main memory.
Knowl 2 — X-tree Directory Node Insertion Algorithm
algorithm
The insertion procedure traverses the directory hierarchy to insert a new data object, maintaining the hybrid hierarchical/supernode structure by preventing splits that induce high overlap.
Input: DataObject obj, DirectoryNode current_node
Output: ReturnStatus (SPLIT, SUPERNODE, or NO_SPLIT), Node *new_node
follow = choose_subtree(current_node, obj)
return_value, new_son = follow.insert(obj)
current_node.update_mbr(follow.calc_mbr())
if return_value == SPLIT then
    current_node.add_mbr(new_son.calc_mbr())
    if current_node.num_of_mbrs() > CAPACITY then
        split_success, s1, s2 = current_node.split(current_node.mbrs)
        if split_success == TRUE then
            current_node.set_mbrs(s1)
            new_node = new DirectoryNode(s2)
            return SPLIT, new_node
        else
            new_node = new SuperNode(current_node.mbrs)
            return SUPERNODE, new_node
        end if
    end if
else if return_value == SUPERNODE then
    current_node.remove_son(follow)
    current_node.insert_son(new_son)
end if
return NO_SPLIT, null
If the recursive insert causes a child node to overflow and split, the new MBR is added to current_node. If current_node overflows, it invokes the split algorithm. If a valid topological or overlap-minimal split exists, the node splits into two directory nodes; otherwise, it is converted into (or extended by one block as) a supernode and returns SUPERNODE to update the parent pointer.
Knowl 3 — X-tree Directory Node Split Algorithm
algorithm
The directory node split algorithm attempts to partition an overflowing set of MBRs using topological heuristics, falls back to an overlap-minimal split based on split history, and triggers supernode creation if no balanced low-overlap split can be found.
Input: SetOfMBR in, Threshold MAX_OVERLAP, Threshold MIN_FANOUT
Output: Boolean success, SetOfMBR out1, SetOfMBR out2
t1, t2 = topological_split(in)
r1 = calc_mbr(t1)
r2 = calc_mbr(t2)
if overlap(r1, r2) > MAX_OVERLAP then
    t1, t2 = overlap_minimal_split(in)
    if num_mbrs(t1) < MIN_FANOUT or num_mbrs(t2) < MIN_FANOUT then
        return FALSE, null, null
    end if
end if
out1 = t1
out2 = t2
return TRUE, out1, out2
The algorithm executes three checks in sequence:
1. Topological Split: Generates partitions $t_1, t_2$ using standard geometric heuristics (e.g., the $\text{R}^*$ -tree split heuristic).
2. Overlap Check: Computes the overlap between bounding boxes $r_1$ and $r_2$ . If the overlap exceeds $\text{MAX\_OVERLAP}$ (typically $20\%$ ), the topological split is discarded and an overlap-minimal split is calculated from the node's split history tree.
3. Balance Check: If the overlap-minimal partition produces underfilled nodes ( $|t_1| < \text{MIN\_FANOUT}$ or $|t_2| < \text{MIN\_FANOUT}$ , where $\text{MIN\_FANOUT}$ is set between $35\%$ and $45\%$ of node capacity), the split fails and returns FALSE, signaling the caller to allocate or extend a supernode.
Knowl 4 — Existence and Determination of Overlap-Free Splits via Split History
theoretical result
Let $S = \{\text{mbr}_1, \dots, \text{mbr}_n\}$ be a set of MBRs in an overflowing directory node, and let $\text{Split}(S) = (S_1, S_2)$ be a partition such that $S = S_1 \cup S_2$ and $S_1 \cap S_2 = \emptyset$ .
- Lemma 1: For uniformly distributed point data, an overlap-free split (i.e., $\|\text{MBR}(S_1) \cap \text{MBR}(S_2)\| = 0$ ) is possible if and only if there exists a dimension $d \in \{1, \dots, D\}$ along which all MBRs in $S$ have been previously split.
- Lemma 2: For point data, an overlap-free split always exists.
Every directory node maintains a binary split history tree (or split tree) whose leaf nodes correspond to the current MBRs in $S$ and whose internal nodes are labeled with the dimension along which a prior split occurred. Because all MBRs descended from the root of the split tree share the initial split dimension $SD$ assigned at the split tree root, partitioning $S$ into $S_1$ (leaves of the left subtree of the root) and $S_2$ (leaves of the right subtree of the root) guarantees an overlap-free split along axis $SD$ .

While an overlap-free split along dimension $SD$ always exists, the resulting partition $(S_1, S_2)$ is not guaranteed to be balanced (e.g., when insertions are skewed), which may necessitate the creation of a supernode instead.
Knowl 5 — Cost-Optimal Maximum Overlap Threshold for Directory Node Splitting
equation
The maximum acceptable overlap threshold $\text{MaxO}$ (denoted as MAX_OVERLAP) determines when an overlap-producing split should be rejected in favor of reading a double-block supernode:

$\text{MaxO} = \frac{T_{Tr} + T_{CPU}}{T_{IO} + T_{Tr} + T_{CPU}}$

where:
- $T_{IO}$ is the disk page access/seek time.
- $T_{Tr}$ is the transfer time to read one disk block from secondary storage into main memory.
- $T_{CPU}$ is the CPU time required to process one disk block.
The threshold is derived by equating the cost of sequentially reading a supernode of size $2 \cdot \text{BlockSize}$ ( $T_{IO} + 2(T_{Tr} + T_{CPU})$ ) to the expected cost of reading two separate split directory blocks with probability $\text{MaxO}$ and one block with probability $(1 - \text{MaxO})$ ( $2\text{MaxO}(T_{IO} + T_{Tr} + T_{CPU}) + (1 - \text{MaxO})(T_{IO} + T_{Tr} + T_{CPU})$ ).

For representative system constants ( $T_{IO} = 20\text{ ms}$ , $T_{Tr} = 4\text{ ms}$ , and $T_{CPU} = 1\text{ ms}$ ), the optimal threshold is:

$\text{MaxO} = \frac{4 + 1}{20 + 4 + 1} = \frac{5}{25} = 20\%$
Knowl 6 — Geometric and Data-Weighted Overlap in Spatial Directory Nodes
definition
For a spatial directory node containing $n$ minimum bounding hyperrectangles $\{R_1, \dots, R_n\}$ :
1. Geometric Overlap: The fraction of the total bounded volume covered by more than one directory hyperrectangle:
$\text{Overlap} = \frac{\left\| \bigcup_{i, j \in \{1, \dots, n\}, i \ne j} (R_i \cap R_j) \right\|}{\left\| \bigcup_{i \in \{1, \dots, n\}} R_i \right\|}$

where $\|A\|$ denotes the geometric volume of region $A$ . This metric assumes uniformly distributed queries.
1. Weighted Overlap: The fraction of data points $P$ located inside regions covered by multiple directory hyperrectangles:
$\text{WeightedOverlap} = \frac{\left| \left\{ p \in P \mid p \in \bigcup_{i, j \in \{1, \dots, n\}, i \ne j} (R_i \cap R_j) \right\} \right|}{\left| \left\{ p \in P \mid p \in \bigcup_{i \in \{1, \dots, n\}} R_i \right\} \right|}$

where $|A|$ denotes the count of data elements contained in region $A$ . This metric estimates query performance when the query distribution follows a non-uniform data distribution.
1. Multi-Overlap: The sum of overlapping volumes weighted by the exact number of overlapping hyperrectangles at each point in space, divided by the total volume.
Knowl 7 — Expected Storage Utilization of Supernodes
theoretical result
For a supernode of size $m \cdot \text{BlockSize}$ (where $m \ge 2$ ), the expected storage utilization under uniformly distributed data is higher than the standard $\approx 66\%$ utilization of normal single-block directory nodes ( $m=1$ ).

Assuming a fixed amount of data occupies $X \cdot m$ blocks in a maximally filled node and $X \cdot \frac{m^2}{m-1}$ blocks in a minimally filled node, the average number of blocks required is:

$\frac{X \cdot m + X \cdot \frac{m^2}{m - 1}}{2} = X \cdot \frac{m(2m - 1)}{2(m - 1)}$

The expected storage utilization as a function of the supernode block multiplier $m$ is:

$\text{StorageUtilization}(m) = \frac{X \cdot m}{X \cdot \frac{m(2m - 1)}{2(m - 1)}} = \frac{2m - 2}{2m - 1}$

For $m = 5$ , the expected storage utilization reaches $\frac{8}{9} \approx 88.9\%$ , increasing monotonically toward $100\%$ as $m \to \infty$ .
Knowl 8 — Directory Size in the Root-Supernode Case
equation
When high dimensionality or overlap prevents hierarchical splits throughout the tree, the directory structure of the X-tree degenerates into a single root supernode containing the entries of the lowest directory level. In this case, the directory size scales linearly with dimension $D$ according to:

$\text{DirSize}(D) = \frac{\text{DatabaseSize}}{\text{BlockSize} \cdot \text{StorageUtil}} \cdot 2 \cdot \text{BytesFloat} \cdot D$

where:
- $\text{DatabaseSize}$ is the total byte size of the raw database.
- $\text{BlockSize}$ is the byte size of a disk page (e.g., $4096\text{ bytes}$ ).
- $\text{StorageUtil}$ is the fractional storage utilization of data leaf nodes (e.g., $0.66$ ).
- $\text{BytesFloat}$ is the storage size of a floating-point coordinate (e.g., $4\text{ bytes}$ ).
- $D$ is the number of dimensions (each dimension requires $2$ floats per MBR to store lower and upper bounds).
For a $1\text{ GB}$ database of $16$ -dimensional data with a $4\text{ KB}$ block size and $66\%$ data node storage utilization, the root supernode directory requires $\approx 44\text{ MB}$ , compared to $\approx 72\text{ MB}$ for a fully hierarchical directory.
Knowl 9 — Empirical Query and Insertion Performance of X-tree vs. R*-tree and TV-tree
empirical result
Experiments evaluated the X-tree against the $\text{R}^*$ -tree and TV-tree using $4\text{ KB}$ block sizes on datasets up to $100\text{ MB}$ ( $D = 2$ to $16$ ) comprising synthetic uniform points, real Fourier shape descriptor point data, and real CAD manifold spatial data:
- Point Queries on Real Point Data ( $70\text{ MB}$ Fourier): X-tree search time speedup over the $\text{R}^*$ -tree reached $\approx 90\times$ for $D = 4$ and $\approx 320\times$ for $D = 8$ .
- Point Queries on Synthetic Data ( $100\text{ MB}$ Uniform): Search speedup over $\text{R}^*$ -tree was $\approx 30\times$ at $D = 8$ and reached $\approx 270\times$ at $D = 16$ . Total search time scaled logarithmically with database size ( $20\text{ MB}$ to $100\text{ MB}$ at $D = 16$ ).
- Nearest-Neighbor Queries (10-NN): Speedup of X-tree over $\text{R}^*$ -tree was $\approx 10\times$ for $D = 6$ and $\approx 20\times$ for $D = 16$ , with significant reductions in both page accesses and CPU distance-sorting time.
- Extended Spatial Data (Real CAD): Due to inherent overlap among extended spatial objects, the speedup of X-tree over $\text{R}^*$ -tree was lower than on point data but still reached $\approx 8\times$ for $D = 16$ .
- Comparison with TV-tree: The X-tree was $4\times$ to $12\times$ faster than the TV-tree across tested dimensions, while the $\text{R}^*$ -tree outperformed the TV-tree for $D < 16$ .
- Insertion Throughput: X-tree insertions were up to $10.45\times$ faster than $\text{R}^*$ -tree and $\approx 30\times$ faster than TV-tree, achieving $\approx 170\text{ insertions/sec}$ for a $150\text{ MB}$ 16-dimensional point index.

Coverage note — Omitted brief mentions of standard nearest neighbor, range query, delete, and update implementations as they are straightforward adaptations of standard R*-tree operations. Also omitted future work remarks regarding parallel X-tree implementation.

References

1.Agrawal R., Faloutsos C., Swami A.: ‘Efficient Similarity Search in Sequence Databases’, Proc. 4th Int. Conf. on Foundations of Data Organization and Algorithms, Evanston, ILL, 1993, in: Lecture Notes in Computer Science, Vol. 730, Springer, 1993, pp. 69-84.
2.Altschul S. F., Gish W., Miller W., Myers E. W., Lipman D. J.: ‘A Basic Local Alignment Search Tool’, Journal of Molecular Biology, Vol. 215, No. 3, 1990, pp. 403-410.
3.Beckmann N., Kriegel H.-P., Schneider R., Seeger B.: ‘The R-tree: An Efficient and Robust Access Method for Points and Rectangles*’, Proc. ACM SIGMOD Int. Conf. on Management of Data, Atlantic City, NJ, 1990, pp. 322-331.
4.Dunn G., Everitt B.: ‘An Introduction to Mathematical Taxonomy’, Cambridge University Press, Cambridge, MA, 1982.
5.Faloutsos C., Barber R., Flickner M., Hafner J., et al.: ‘Efficient and Effective Querying by Image Content’, Journal of Intelligent Information Systems, 1994, Vol. 3, pp. 231-262.
6.Faloutsos C., Lin K.: ‘FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets’, Proc. ACM SIGMOD Int. Conf. on Management of Data, San Jose, CA, 1995, pp. 163-174.
7.Guttman A.: ‘R-trees: A Dynamic Index Structure for Spatial Searching’, Proc. ACM SIGMOD Int. Conf. on Management of Data, Boston, MA, 1984, pp. 47-57.
8.Günther O., Noltemeier H.: ‘Spatial Database Indices For Large Extended Objects’, Proc. 7th Int. Conf. on Data Engineering, 1991, pp. 520-527.
9.Harman H. H.: ‘Modern Factor Analysis’, University of Chicago Press, 1967.
10.Jagadish H. V.: ‘A Retrieval Technique for Similar Shapes’, Proc. ACM SIGMOD Int. Conf. on Management of Data, 1991, pp. 208-217.
11.Kukich K.: ‘Techniques for Automatically Correcting Words in Text’, ACM Computing Surveys, Vol. 24, No. 4, 1992, pp. 377-440.
12.Kruskal J. B., Wish M.: ‘Multidimensional Scaling’, SAGE publications, Beverly Hills, 1978.
13.Lin K., Jagadish H. V., Faloutsos C.: ‘The TV-tree: An Index Structure for High-Dimensional Data’, VLDB Journal, Vol. 3, 1995, pp. 517-542.
14.Mehrotra R., Gary J. E.: ‘Feature-Based Retrieval of Similar Shapes’, Proc. 9th Int. Conf. on Data Engineering, Vienna, Austria, 1993, pp. 108-115.
15.Mehrotra R., Gary J. E.: ‘Feature-Index-Based Similar Shape Retrieval’, Proc. of the 3rd Working Conf. on Visual Database Systems, 1995, pp. 46-65.
16.Murase H., Nayar S. K.: ‘Three-Dimensional Object Recognition from Appearance-Parametric Eigenspace Method’, Systems and Computers in Japan, Vol. 26, No. 8, 1995, pp. 45-54.
17.Nievergelt J., Hinterberger H., Sevcik K. C.: ‘The Grid File: An Adaptable, Symmetric Multikey File Structure’, ACM Trans. on Database Systems, Vol. 9, No. 1, 1984, pp. 38-71.
18.Roussopoulos N., Kelley S., Vincent F.: ‘Nearest Neighbor Queries’, Proc. ACM SIGMOD Int. Conf. on Management of Data, San Jose, CA, 1995, pp. 71-79.
19.Robinson J. T.: ‘The K-D-B-tree: A Search Structure for Large Multidimensional Dynamic Indexes’, Proc. ACM SIGMOD Int. Conf. on Management of Data, 1981, pp. 10-18.
20.Shoichet B. K., Bodian D. L., Kuntz I. D.: ‘Molecular Docking Using Shape Descriptors’, Journal of Computational Chemistry, Vol. 13, No. 3, 1992, pp. 380-397.
21.Shawney H., Hafner J.: ‘Efficient Color Histogram Indexing’, Proc. Int. Conf. on Image Processing, 1994, pp. 66-70.
22.Seeger B., Kriegel H.-P.: ‘The Buddy Tree: An Efficient and Robust Access Method for Spatial Data Base Systems’, Proc. 16th Int. Conf. on Very Large Data Bases, Brisbane, Australia, 1990, pp. 590-601.
23.Sellis T., Roussopoulos N., Faloutsos C.: ‘The R+-Tree: A Dynamic Index for Multi-Dimensional Objects’, Proc. 13th Int. Conf. on Very Large Databases, Brighton, England, 1987, pp 507-518.
24.White, D., Jain R.: ‘Similarity Indexing with the SS-tree’, Proc. 12th Int. Conf. on Data Engineering, New Orleans, LA, 1996.
25.Wallace T., Wintz P.: ‘An Efficient Three-Dimensional Aircraft Recognition Algorithm Using Normalized Fourier Descriptors’, Computer Graphics and Image Processing, Vol. 13, 1980, pp. 99-126.

Citation

MLA

Berchtold, S., et al. “The X-tree: An Index Structure for High-Dimensional Data Permission to Copy Without Fee All or Part of This Material Is Granted Provided That the Copies Are Not Made or Distributed for Direct Commercial Advantage, the VLDB Copyright Notice and the Title of the Publication and Its Date Appear, and Notice Is Given That Copying Is by Permission of the Very Large Data Base Endowment. To Copy Otherwise, or to Republish, Requires a Fee And/or Special Permission from the Endowment.”. Readings in Multimedia Computing and Networking, Elsevier, 2002, pp. 451–62, https://doi.org/10.1016/B978-155860651-7/50124-8.

APA

Berchtold, S., Keim, D. A., & Kriegel, H.-P. (2002). The X-tree: An Index Structure for High-Dimensional Data Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment. In Readings in Multimedia Computing and Networking (pp. 451–462). Elsevier. https://doi.org/10.1016/B978-155860651-7/50124-8

Chicago

Berchtold, S., D. A. Keim, and H.-P. Kriegel. 2002. “The X-tree: An Index Structure for High-Dimensional Data Permission to Copy Without Fee All or Part of This Material Is Granted Provided That the Copies Are Not Made or Distributed for Direct Commercial Advantage, the VLDB Copyright Notice and the Title of the Publication and Its Date Appear, and Notice Is Given That Copying Is by Permission of the Very Large Data Base Endowment. To Copy Otherwise, or to Republish, Requires a Fee And/or Special Permission from the Endowment.”. In Readings in Multimedia Computing and Networking. Elsevier. https://doi.org/10.1016/B978-155860651-7/50124-8.

Harvard

Berchtold, S., Keim, D.A. and Kriegel, H.-P. (2002) “The X-tree: An Index Structure for High-Dimensional Data Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.”, Readings in Multimedia Computing and Networking. Elsevier, pp. 451–462. Available at: https://doi.org/10.1016/B978-155860651-7/50124-8.

Vancouver

1. Berchtold S, Keim DA, Kriegel H-P (2002) The X-tree: An Index Structure for High-Dimensional Data Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment. In: Readings in Multimedia Computing and Networking. Elsevier, pp 451–462

BibTeX

@inbook{Berchtold_2002, title={The X-tree: An Index Structure for High-Dimensional Data  Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.}, ISBN={9781558606517}, url={http://dx.doi.org/10.1016/B978-155860651-7/50124-8}, DOI={10.1016/b978-155860651-7/50124-8}, booktitle={Readings in Multimedia Computing and Networking}, publisher={Elsevier}, author={Berchtold, Stefan and Keim, Daniel A. and Kriegel, Hans-Peter}, year={2002}, pages={451–462} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — X-tree Hybrid Directory Structure and Supernodes

Knowl 2 — X-tree Directory Node Insertion Algorithm

Knowl 3 — X-tree Directory Node Split Algorithm

Knowl 4 — Existence and Determination of Overlap-Free Splits via Split History

Knowl 5 — Cost-Optimal Maximum Overlap Threshold for Directory Node Splitting

Knowl 6 — Geometric and Data-Weighted Overlap in Spatial Directory Nodes

Knowl 7 — Expected Storage Utilization of Supernodes

Knowl 8 — Directory Size in the Root-Supernode Case

Knowl 9 — Empirical Query and Insertion Performance of X-tree vs. R*-tree and TV-tree

References

Citation

BibTeX

Source Code

Access the Paper