A five-level static cache architecture for web search engines

► Static result caching for Web search engines. ► A five-level cache storing results, scores, lists, list intersections and documents. ► Greedy cost-based strategy to determine the cache contents. ► Experiments with a realistic setting and large query log. Caching is a crucial performance component...

Full description

Saved in:
Bibliographic Details
Published in:Information processing & management 2012-09, Vol.48 (5), p.828-840
Main Authors: Ozcan, Rifat, Sengor Altingovde, I., Barla Cambazoglu, B., Junqueira, Flavio P., Ulusoy, Özgür
Format: Article
Language:English
Subjects:
Architecture
Cache
Caching
Computer architecture
Decisions
Exact sciences and technology
Gain
Heuristic
Heuristics
Information and communication sciences
Information processing
Information processing and retrieval
Information retrieval. Man machine relationship
Information science. Documentation
Lists
Query processing
Research process. Evaluation
Sciences and techniques of general use
Search engines
Simulation
Static caching
Studies
Web search engines
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:► Static result caching for Web search engines. ► A five-level cache storing results, scores, lists, list intersections and documents. ► Greedy cost-based strategy to determine the cache contents. ► Experiments with a realistic setting and large query log. 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.
ISSN:0306-4573
1873-5371
DOI:10.1016/j.ipm.2010.12.007