Norio Katayama and Shin'ichi Satoh,
Distinctiveness-Sensitive Nearest-Neighbor Search for
Efficient Similarity Retrieval of Multimedia Information,
In Proceeding of the 17th International Conference on Data
Engineering (ICDE 2001),
pp. 493-502, 2-6 April 2001.Nearest neighbor (NN) search in high dimensional feature space is widely used for similarity retrieval of multimedia information. However recent research results in the database literature reveal that a curious problem happens in high dimensional space. Since high dimensional space has a high degree of freedom, points could be scattered so that every distance between them might yield no significant difference. In this case, we can say that the NN is indistinctive because many points exist at the similar distance. To make matters worse, indistinctive NNs require more search cost because search completes only after choosing the NN from plenty of strong candidates. In order to circumvent the handful effect of indistinctive NNs, the paper presents a new NN search algorithm which determines the distinctiveness of the NN during search operation. This enables us not only to cut down search cost but also to distinguish distinctive NNs from indistinctive ones. These advantages are especially beneficial to interactive retrieval systems.