joint work with
Usama Fayyad
Microsoft Research
and
Dan Geiger
Technion, Israel
Abstract:
We address the problem of performing nearest-neighbor queries efficiently over large high-dimensional databases. To avoid a full database scan, we construct a multi-dimensional index structure. It is well-accepted that traditional database indexing algorithms fail for high-dimensional data (say d > 10 or 20 depending on the scheme). Some arguments have advocated that nearest-neighbor queries do not even make sense for high-dimensional data. We show that these arguments are based on over-restrictive assumptions, and that in the general case it is meaningful and possible to build an effective index for such queries. Our approach, called DBIN, scales to high-dimensional databases by exploiting statistical properties of the data. The approach is based on statistically modeling the density of the data. DBIN uses the density model to derive a single index over the data table and requires physically re-writing data in a new table sorted by the newly created index (i.e. create a clustered-index). The indexing scheme produces a mapping between a query point (a data record) and an ordering on the clustered index values. Data is then scanned according to the index. We present theoretical and empirical justification for DBIN. The scheme supports a family of distance functions which includes the Euclidean distance.