| Many database applications, which include multimedia systems, data
mining and scientific simulations, deal with large amounts of persistent
data characterized by very high dimensionality. Unfortunately, other than
the fact that contemporary multi-dimensional access methods do not handle
well large sets of high-dimensional data, we know little about the underlying
causes of their inadequacy. In this seminar, we will discuss the problems
of traditional spatial structures that result in their inability to handle
high-dimensional data. Then we introduce two new structures that effectively
attack the limitations of the contemporary access methods in high-dimensional
spaces.
The first structure, called QSF-trees, is designed to accommodate extended
spatial objects in both low- and high-dimensional spaces. The analytical
and experimental evidence shows that QSF-trees outperform the traditional
SAMs, including two variants of R*-trees and object-transformation schemes.
As the number of dimensions grows, the improvements have a tendency to
increase. The other structure, called the high-dimensional KDB-tree, is
designed to accommodate points in high-dimensional spaces. The structure
is a general-purpose point access method that effectively attacks the limitations
of KDB-trees in high-dimensional spaces, while preserving their simplicity
and good performance characteristics in low-dimensional spaces. |