What Is the Nearest Neighbor in High Dimensional Spaces

Nearest neighbor search in high dimensional spaces is an interesting and important problem which is relevant for a wide varietyofnovel database applications. As recentresults show, however, the problem is a very difficult one, not only with regards to the performance issue but also to the quality issue. In this paper, we discuss the quality issue and identify a new generalized notion of nearest neighbor search as the relevant problem in high dimensional space. In contrast to previous approaches, our new notion of nearest neighbor search does not treat all dimensions equally but uses a quality criterion to select relevant dimensions (projections) with respect to the given query. As an example for a useful quality criterion, we rate howwell the data is clustered around the query point within the selected projection. We then propose an efficient and effectivealgorithm to solve the generalized nearest neighbor problem. Our experiments based on a number of real and synthetic data sets sho...