Metric Indexing to Improve Distance Joins

Database applications using large vector data are often supported by spatial index structures to locate spatially related objects. An important query class deals with finding related object pairs under a distance function. %, i.e. those %spatially close to a given point. , like nearest neighbors. In this paper we demonstrate that a light-weight indexing structure, based on the metric properties derived from the distance function, is often sufficient to support this important class. It is of particular importance as a temporary search accelerator while processing complex queries. Moreover, it can be used to speed up point and region queries for low selectivities and, presumably, highly-skewed spaces.