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, sa.5, ss.828-840, 2012 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 48 Sayı: 5
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1016/j.ipm.2010.12.007
  • Dergi Adı: INFORMATION PROCESSING & MANAGEMENT
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus
  • Sayfa Sayıları: ss.828-840
  • Anahtar Kelimeler: Web search engines, Static caching, Query processing
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Ö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.