Widely used dynamic pruning algorithms (such as MaxScore, WAND and BMW) keep track of the k-th highest score (i.e., heap threshold) among the documents that are scored so far, to avoid scoring the documents that cannot get into the top-k result list. Obviously, the faster the heap threshold converges to its final value, the larger will be the number of skipped documents and hence, the efficiency gains of the pruning algorithms. In this paper, we tailor approaches that reorder the documents in the inverted index based on their access counts and ranks for previous queries. By storing such frequently retrieved documents at front of the postings lists, we aim to compute the heap threshold earlier during the query processing. Our approach yields substantial speedups (up to 1.33x) for all three dynamic pruning algorithms and outperforms two strong baselines that have been employed for document reordering in the literature.

We propose to use a score cache, which stores the score of the k-th result of a query, to accelerate top-k query processing with dynamic pruning methods (i.e., WAND and BMW). We introduce heuristics that, for a new query, generate its subsets and probe the score cache to obtain a lower-bound on its score threshold. Our experiments show up to 8.6% savings in mean processing time for the queries that are not seen before, i.e., cannot benefit from a result cache.