Implementations of partial document ranking using inverted files

摘要

Most commercial text retrieval systems employ inverted files to improve retrieval speed. This paper concerns with the implementations of document ranking based on inverted files. Three heuristic methods for implementing the tf × idf weighting strategy, where tf stands for term frequency and idf stands for inverse document frequency, are studied. The basic idea of the heuristic methods is to process the query terms in an order so that as many top documents as possible can be identified without processing all of the query terms. The first heuristic was proposed by Smeaton and van Rijsbergen and it serves as the basis for comparison with the other two heuristic methods proposed in this paper. These three heuristics are evaluated and compared by experimental runs based on the number of disk accesses required for partial document ranking, in which the returned documents contain some, but not necessarily all, of the requested number of top documents. The results show that the proposed heuristic methods perform better than the method proposed by Smeaton and van Rijsbergen in terms of retrieval accuracy, which is used to indicate the percentage of top documents obtained after a number of disk accesses. For total document ranking, in which all of the requested number of top documents are guaranteed to be returned, no optimization techniques studied so far can lead to substantial performance gain. To realize the advantage of the proposed heuristics, two methods for estimating the retrieval accuracy are studied. Their accuracies and processing costs are compared. All the experimental runs are based on four test collections made available with the SMART system.