A five-level static cache architecture for web search engines

Creative Commons License

Ozcan R., Altingovde İ. S., Barla Cambazoglu B., Junqueira F. P., Ulusoy O.

INFORMATION PROCESSING & MANAGEMENT, vol.48, no.5, pp.828-840, 2012 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 48 Issue: 5
  • Publication Date: 2012
  • Doi Number: 10.1016/j.ipm.2010.12.007
  • Journal Name: INFORMATION PROCESSING & MANAGEMENT
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Page Numbers: pp.828-840
  • Keywords: Web search engines, Static caching, Query processing
  • Middle East Technical University Affiliated: Yes

Abstract

Caching is a crucial performance component of large-scale web search engines, as it greatly helps reducing average query response times and query processing workloads on backend search clusters. In this paper, we describe a multi-level static cache architecture that stores five different item types: query results, precomputed scores, posting lists, precomputed intersections of posting lists, and documents. Moreover, we propose a greedy heuristic to prioritize items for caching, based on gains computed by using items' past access frequencies, estimated computational costs, and storage overheads. This heuristic takes into account the inter-dependency between individual items when making its caching decisions, i.e., after a particular item is cached, gains of all items that are affected by this decision are updated. Our simulations under realistic assumptions reveal that the proposed heuristic performs better than dividing the entire cache space among particular item types at fixed proportions. (C) 2010 Elsevier Ltd. All rights reserved.