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

By Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel. Very Large Data Bases Conference, 2001

1,607 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/774db16a3f25a73ceda9e6ab4d5a8b8f3c40605d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Signal Processing

Citations in the corpus

The Concentration of Fractional Distances (2007, background): “This has been described among others in [32], [33], [34], and [35] and was acknowledged by many others as the curse of dimensionality.”
PAC nearest neighbor queries: Approximate and controlled search in high-dimensional and metric spaces (2000, methodology): “To speed-up NN search, feature values, which often are high-dimensional (highD) vectors, can be indexed by means of either multi-dimensional trees (such as the R -tree [4], the SR-tree [18], and the X-tree [6]) or metrictrees (e.”
Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions (2005, background): “Although conventional range search (on a “precise” dataset) has been very well studied [1, 3], its solutions are not applicable to uncertain data, since they do not consider the probabilistic requirements [6].”
Image Retrieval from the World Wide Web: Issues, Techniques, and Systems (2004, methodology): “Existing multidimensional indexing techniques include the bucketing algorithm, k-d trees, priority k-d trees, quad-trees, K-D-B trees, hB trees, R-trees, R− trees, R∗ trees, and X-trees [Smeulders et al. 2000; Rui et al. 1999; Berchtold et al. 1996].”
Incremental Local Outlier Detection for Data Streams (2007, methodology): “, 17-20,42], as well as efficient indexing structures for inserting/deleting the records [25, 26] are used (where TkNN”
Efficient similarity search and classification via rank aggregation (2003, methodology): “This method is also database-friendly, in that it accesses data primarily in a pre-de.ned order without random accesses, and, unlike other methods for approximate nearest neighbors, requires almost no extra storage.”
Geometric Range Searching and Its Relatives (2007, background): “[47] de ne the X-tree, in which the interior nodes are allowed to be arbitrarily large; Lin et al.”
LOF: identifying density-based local outliers (2000, positive): “rialization step. In our experiments, we used a variant of the X-tree ([ 4 ]), leading to the complexity of O(n log n). Figure 10 shows performance experiments for different dimensional datasets and MinPtsUB=50.”
iDistance: An adaptive B+-tree based indexing method for nearest neighbor search (2005, methodology): “To reduce the effect of high dimensionality, use of larger fanouts [Berchtold et al. 1996; Sakurai et al. 2000], dimensionality reduction techniques [Chakrabarti and Mehrotra 2000; 1999], and filter-and-refine methods [Berchtold et al.”
An optimal algorithm for approximate nearest neighbor searching fixed dimensions (1998, background): “For example, see [Berchtold et al. 1997; Berchtold et al. 1996; Lin et al. 1994; Roussopoulos et al. 1995; White and Jain 1996].”
What Is the Nearest Neighbor in High Dimensional Spaces? (2000, background): “Many empirical studies have shown that traditional indexing methods fail in high dimensional spaces [5, 22, 4].”
Progressive skyline computation in database systems (2005, background): “investigate alternatives (e.g., X-trees [ BKK96 ], A-trees [SYUK00]) for high dimensional spaces, where”