Partial document ranking by heuristic methods

In this paper, we study three methods for implementing the tf × idf ranking strategy with inverted files, where tf stands for term frequency and idf stands for inverse document frequency. The first one sorts the postings lists of the query terms by increasing length. It is the traditional sorting method used in the upperbound search algorithm. The second one sorts query terms based upon two parameters, namely the maximum tf of the postings list and the list length. The third one first requires each postings list to be sorted by decreasing t f value. It sorts disk pages, rather than postings lists, based upon three parameters, the maximum tf of the disk page, the length of the postings list and the number of document identifiers in the disk page. We show that the second and third methods are able to identify a large portion of top documents without using a large amount of disk page accesses. They outperform the first method by a large margin. The performance of these methods is demonstrated by experimental runs on four test collections made available with the SMART system.