High-Dimensional Indexing

In many application domains we have to deal with high-dimensional data sets. When searching high-dimensional data spaces, the so-called curse of dimensionality leads to a deterioration of the performance of classic indexing structures. We analyse typical effects present in high-dimensional data spaces, propose an advanced index structure for HD data, and present an accurate cost model for estimating access costs and optimizing indices when searching HD indices.

• Cost Model
  
  In HD indexing, traditional cost models must be extended to take into account effects occurring in HD data spaces, in order to produce accurate estimations for access probabilities.
  

  

• Index Structurex
  
  Indexing high-dimensional data with classical space partitioning structures like R/R*-Trees leads to high overlap and diminishes the advantages of using hierarchical partitions.
  
  
  
• Optimizing Query Processing
  
  Accurate cost models are needed for tuning the index in order to speed up the search process.