Caching techniques for large scale web search engines

Büyük ölçekli arama motorları artan ağ içeriği ve artan günlük sorgu sayısı ile mücadele etmek zorundadırlar. Sorgu cevaplarının önbelleklenmesi ise sistemin belli bir zamanda sorgu cevaplama sayısını arttırabileceği kritik yöntemlerden birisidir. Bu tezde, arama motorlarında önbelleklemenin verimliliğini arttırıcı çeşitli yöntemler önerilmektedir.İlk olarak, statik ve dinamik sorgu cevabı önbellekleri için maliyet bazlı önbellekleme yöntemleri geliştirilmiştir. Sorguların ciddi oranda farklı maliyetlerinin olduğu ve bu maliyet ile frekans arasında doğru orantı olmadığı gözlemlenmiştir. Bu nedenle önbelleğe hangi öğelerin alınacağına karar verilirken frekansa ek olarak sorgu maliyetini de göz önüne alan yöntemler tasarlanmıştır. İkinci olarak, navigasyonel sorguların tanımlanarak diğer sorgulardan farklı olarak önbelleklendiği bir sorgu tipi bazlı önbellekleme yöntemi geliştirilmiştir. Sorgu cevapları genellikle her biri 10 cevap içeren sonuç sayfaları olarak sunulmakta ve önbellekte saklanmaktadır. Navigasyonel sorgularda amaç belirli bir ağ sayfasına ulaşmaktır ve bu sayfa arama motoru tarafından bulunursa yüksek sıralarda listelenmektedir. Bu sorgu tipi için cevapların bir sayfada 10 cevap olacak şekilde sunulup önbellekte saklanmasının maliyet etkinliği olmayan bir yöntem olduğu gösterilmiş ve alternatif cevap sunum modelleri önerilerek bunların önbellekleme üzerindeki etkisi araştırılmıştır. Üçüncü olarak, statik önbellekte sorgu cevapları için kümeleme bazlı bir saklama yöntemi önerilmiştir. Ortak cevap belgesi olan sorgular tek bağlantı yöntemi ile kümelenmiştir. Oluşan kümelerdeki sorgu cevaplarındaki örtüşmeden yararlanan kompakt bir saklama modeli sunulmuştur. Son olarak, bir arama motoru ortamında önbelleklenebilecek tüm veri öğelerini (sorgu cevapları, endeks parçası ve belge içeriği) içerisinde barındıran beş-seviyeli bir statik önbellek önerilmiştir. öğelerin hangi sırayla önbelleğe alınacağını belirlemek için bir açgözlü algoritma geliştirilmiştir. Bu yöntem önbelleğe alınmada öğeleri geçmiş frekans değerleri, öngörülen maliyet ve önbellekte kaplayacağı alan açısından önceliklendirmektedir. Ayrıca öğeler arasındaki bağımlılık göz önüne alınarak bir öğenin önbelleğe alınmasından sonra henüz önbelleğe alınmamış bağımlı öğelerin kazanç değerleri değiştirilmektedir.Önerilen bütün yöntemler gerçek sorgu kütüğü ve belge kolleksiyonu kullanan deneylerle test edilmiştir. Literatürde karşılık gelen referans yöntemler ile karşılaştırmalar sunulmuş ve üretilen iş, sorgu ıskalama sayısı ve sorgu cevaplarının kapladığı alan bazında gelişmeler elde edilmiştir.