Caching Scores for Faster Query Processing with Dynamic Pruning in Search Engines

Yafay E., Altıngövde İ. S.

28th ACM International Conference on Information and Knowledge Management (CIKM), Beijing, China, 3 - 07 November 2019, pp.2457-2460 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume:
  • Doi Number: 10.1145/3357384.3358154
  • City: Beijing
  • Country: China
  • Page Numbers: pp.2457-2460
  • Middle East Technical University Affiliated: Yes

Abstract

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.