Abstract
We propose a similarity search method for finding similar objects in a large-scale database. The search method is
based on a graph index, where each vertex corresponds to a object and two vertices are connected by an edge
when they satisfy a certain similarity condition. The graph index shows small-world behavior, that is, vertices can
be reached from every other vertex by a small number of steps. Hence, searching the graph results in quick
termination of the search process. Furthermore, since the graph index is constructed based on similarity between
two objects, the search method is versatile and can be applied to wide variety of media such as text, images and
audio. When applied to complex objects that are more than two media combined, such as picture books which
consists of text and illustration, users can search from various viewpoints; users can find picture picture books
that are not only similar in content but also similar in style of illustration.
Takashi Hattori, Learning and Intelligent Systems Research Group, Innovative Communication Laboratory
Email: