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, cilt.48, ss.828-840, 2012 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 48 Konu: 5
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1016/j.ipm.2010.12.007
  • Dergi Adı: INFORMATION PROCESSING & MANAGEMENT
  • Sayfa Sayıları: ss.828-840

Özet

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.