Exploiting temporal query behavior for improving result cache accuracy in web search engines

Abstract

In Web Search Engines responding to the user queries in a timely fashion is an important requirement. One of the integral techniques to improve the response time of a search engine is caching. By storing different types of information in a fast access memory storage, caching achieves a higher availability and better response times for the search engine. Due to anonymous and global access pattern of the queries, search engines are often considered timeless frameworks. That is, search engine sites constantly respond to queries that are submitted all around the world at an almost constant pace throughout the day. During our studies, we evaluate this phenomenon and come to the conclusion that each of the data centers, which in cooperation form the general infrastructure of a general purpose search engine in fact realizes high levels of query temporality. In this work, we aim to apply and exploit the temporal behavior of the submitted queries to improve the cache accuracy by proposing a new caching architecture. To this end, we improved the state-of-the-art result caching framework Static-Dynamic Cache (SDC) and modified it in order to incorporate query temporality. Our experiments show that the proposed caching framework improves the hit rate of a result cache up to 3%, which is roughly 25% of the possible room for improvement.

Arama motorları için kullanıcı sorgularına hızlı ve zamanında cevap verebilmek önemli bir gereksinimdir. Cevap zamanını eniyilemek için yaygın olarak kullanılan temel tekniklerden biri cevap sayfalarının önbelleklenmesidir. Birçok farklı bilgiyi hafıza gibi hızlı erişim yeteneğine sahip bir yapıda saklayarak önbellekler arama motorlarına daha kabul edilebilir bir cevap zamanı elde etme olanağı sağlarlar. Kullanıcı sorgularının anonim ve küresel yapısından dolayı arama motorları yaygın olarak zamana bağlı olmayan yapılar olarak algılanmışlardır. Yani, ara motoru siteleri sürekli olarak kendilerine gönderilmiş olan dünyanın her yerinden gelen sorgulara gün boyu cevap vermektedirler. Araştırmalarımız sırasında, bu fenomeni inceledi ve veri merkezlerinin, yani bir arama motorunun altyapı taşlarının, yüksek seviyede sorgu zamansallığının etkisi altında kaldığını farkettik. Bu çalışmamızda amacımız sorgu zamansallığını kullanan yeni bir önbellek yapısı önermek ve bu şekilde önbellek başarısını artırmaktır. Bu amaçla en gelişkin teknoloji olarak kabul edilen Statik-Dinamik Önbellek (SDC) inceleyerek üzerine sorgu zamansallığını kullanan değişiklikler önerdik. Yapılan deneyler önerdiğimiz önbellek yapısının önbellek cevaplama oranını %3 kadar artırdığını göstermektedir ki bu yapılabilecek maksimum eniyilemenin neredeyse %25'ine denk gelmektedir.