Topical result caching in web search engines. Issue 3 (May 2020)

• Record Type: Journal Article
• Authors: Mele, Ida; Tonellotto, Nicola; Frieder, Ophir; Perego, Raffaele
• Is Part Of: Information processing & management. Volume 57:Issue 3(2020:May)
• Publication Date: 2020-05
• Subjects: Efficiency -- Caching -- Topic modeling; Information storage and retrieval systems -- Periodicals; Information science -- Periodicals; Systèmes d'information -- Périodiques; Sciences de l'information -- Périodiques; Information science; Information storage and retrieval systems; Periodicals; 658.4038
• DOI: 10.1016/j.ipm.2019.102193
• Languages: English
• ISSNs: 0306-4573

Abstract

Highlights: Queries belonging to different topics may have different temporal patterns. We propose Static-Topic-Dynamic cache to capture the query stream temporal localities. The Static-Topic-Dynamic cache outperforms the traditional Static-Dynamic Cache. Hit rate improves up to 3% without admission policy and 4. Abstract: Caching search results is employed in information retrieval systems to expedite query processing and reduce back-end server workload. Motivated by the observation that queries belonging to different topics have different temporal-locality patterns, we investigate a novel caching model called STD (Static-Topic-Dynamic cache), a refinement of the traditional SDC (Static-Dynamic Cache) that stores in a static cache the results of popular queries and manages the dynamic cache with a replacement policy for intercepting the temporal variations in the query stream. Our proposed caching scheme includes another layer for topic-based caching, where the entries are allocated to different topics (e.g., weather, education). The results of queries characterized by a topic are kept in the fraction of the cache dedicated to it. This permits to adapt the cache-space utilization to the temporal locality of the various topics and reduces cache misses due to those queries that are neither sufficiently popular to be in the static portion nor requested within short-time intervals to be in the dynamic portion. We simulate different configurations for STD using two real-world query streams. Experiments demonstrate that our approach outperforms SDC with an increase up to 3% in terms of hit rates, and up to 36% of gap reduction w.r.t. SDC from the theoretical optimal caching algorithm.