Geri Dön

Caching techniques for large scale web search engines

Büyük ölçekli arama motorlarında önbellekleme teknikleri

  1. Tez No: 287393
  2. Yazar: RIFAT ÖZCAN
  3. Danışmanlar: PROF. DR. ÖZGÜR ULUSOY
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Mühendislik Bilimleri, Computer Engineering and Computer Science and Control, Engineering Sciences
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2011
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Bölümü
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 156

Özet

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.

Özet (Çeviri)

Large scale search engines have to cope with increasing volume of web content and increasing number of query requests each day. Caching of query results is one of the crucial methods that can increase the throughput of the system. In this thesis, we propose a variety of methods to increase the efficiency of caching for search engines.We first provide cost-aware policies for both static and dynamic query result caches. We show that queries have significantly varying costs and processing cost of a query is not proportional to its frequency. Based on this observation, we develop caching policies that take the query cost into consideration in addition to frequency, while deciding which items to cache. Second, we propose a query intent aware caching scheme such that navigational queries are identified and cached differently from other queries. Query results are cached and presented in terms of pages, which typically includes 10 results each. In navigational queries, the aim is to reach a particular web site which would be typically listed at the top ranks by the search engine, if found. We argue that caching and presenting the results of navigational queries in this 10-per-page manner is not cost effective and thus we propose alternative result presentation models and investigate the effect of these models on caching performance. Third, we propose a cluster based storage model for query results in a static cache. Queries with common result documents are clustered using single link clustering algorithm. We provide a compact storage model for those clusters by exploiting the overlap in query results. Finally, a five-level static cache that consists of all cacheable data items (query results, part of index, and document contents) in a search engine setting is presented. A greedy method is developed to determine which items to cache. This method prioritizes items for caching based on gains computed using items' past frequency, estimated costs, and storage overheads. This approach also considers the inter-dependency between items such that caching of an item may affect the gain of items that are not cached yet.We experimentally evaluate all our methods using a real query log and document collections. We provide comparisons to corresponding baseline methods in the literature and we present improvements in terms of throughput, number of cache misses, and storage overhead of query results.

Benzer Tezler

  1. Deprem etkisindeki yapılarda aktif ve pasif kontrol sistemlerinin uygulanması

    Başlık çevirisi yok

    BARIŞ SARI

    Yüksek Lisans

    Türkçe

    Türkçe

    1998

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. A. NECMETTİN GÜNDÜZ

  2. Terkos gölüne gelen aylık debinin çeşitli metotlarla tahmini

    Montly inflow prediction for Terkos lake by various methods

    HALİL İBRAHİM TÜRKOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2013

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    İnşaat Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MEHMET ÖZGER

  3. Fen okuryazarlığına yönelik koçluk döngüsünün, öğretmenlerin teknolojik pedagojik alan bilgisi ve öğrencilerin fen okuryazarlığına yönelik tutumları ile akademik başarılarına etkisi

    The effect of coaching cycle for science literacy on teachers' technological pedagogical content knowledge, temporary attitudes towards science literacy and academic achievement

    MELAHAT ÇELİK

    Doktora

    Türkçe

    Türkçe

    2024

    Eğitim ve ÖğretimAkdeniz Üniversitesi

    Matematik ve Fen Bilimleri Eğitimi Ana Bilim Dalı

    DOÇ. DR. MUSTAFA DOĞRU

  4. Makina halılarının yapısal özellikleri ile mekanik etkiler karşısındaki davranış özellikleri üzerine bir araştırma

    The physics of woven carpets

    ÖMER BERK BERKALP

    Yüksek Lisans

    Türkçe

    Türkçe

    1997

    Tekstil ve Tekstil Mühendisliğiİstanbul Teknik Üniversitesi

    Tekstil Mühendisliği Ana Bilim Dalı

    DOÇ. DR. EMEL ÖNDER

  5. Futbol antrenörlerinin toparlanma bilgi düzeylerinin incelenmesi

    Examination of the recovery knowledge levels of soccer coaches

    ORHAN ÖZKAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2021

    SporSakarya Uygulamalı Bilimler Üniversitesi

    Antrenörlük Eğitimi Ana Bilim Dalı

    DOÇ. DR. MURAT ÇİLLİ