Applying the branch and bound technique to document similarity search

This paper proposes a new mechanism for document similarity search, which uses the indexing structure called signature tables. The mechanism of signature tables is originally invented for similarity search of market basket data, and in this paper we apply it to document data. Since the characteristics of document data is definitely different from that of market basket data, the performance of similarity search is not satisfactory when the mechanism is naively applied to document data. In this paper, we describe the reason why the naive application decreases the efficiency, and propose some techniques for improving the performance. The results of simulation using real document data set show that the proposed mechanism implements good performance