2001
@inproceedings{KaS2001,
vgclass = {refpap},
author = {Norio Katayama and Shin'ichi Satoh},
title = {Distinctiveness-Sensitive Nearest-Neighbor Search for
Efficient Similarity Retrieval of Multimedia Information},
booktitle = {Proceeding of the 17th International Conference on Data
Engineering (ICDE 2001)},
pages = {493--502},
month = {2--6~April},
year = {2001},
url = {http://csdl.computer.org/comp/proceedings/icde/2001/1001/00/10010493abs.htm},
url1 = {http://research.nii.ac.jp/~katayama/homepage/papers/icde2001.pdf},
abstract = {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.},
}