and Takenobu Tokunaga

Approximated algorithms for clustering large-scale document collection are proposed and evaluated under the context of cluster-based document retrieval (i.e., associative document search). These algorithms use a precise clustering algorithm as a subroutine to construct a stratified structure of cluster trees. An experiment showed that more than 100 times speedup in cpu time was gained at best. Through experiments of self retrieval and topic assignment, we confirmed sufficient search performance on cluster trees that are constructed by approximated algorithms. In particular, top down construction offered over 99% accuracy of self retrieval which is comparable performance to exhaustive search. Top down construction also offered promising performance in topic assignment, that is, better recall/precision than that obtained by exhaustive search. All of the results for cluster-based retrieval were obtained by simple and efficient binary tree search. 1 Introduction As the size of document re..