Tez No	İndirme	Tez Künye	Durumu
180672		Models and algorithms for parallel text retrieval / Paralel metin getirme için modeller ve algoritmalar Yazar:BERKANT BARLA CAMBAZOĞLU Danışman: PROF.DR. CEVDET AYKANAT Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2006 198 s.
üOZET˙ ˙ ˙şË™PARALEL METIN GETIRME ICIN˙MODELLER VE ALGORITMALARBerkant Barla CambazoğlugBilgisayar Mühendisliği, Yü ksek Lisansu g uTez Yüneticisi: Prof. Dr. Cevdet AykanatoOcak, 2006Son on yılda arama motorları hayatımızla bütü nleşik bir hale gelmişlerdir. Aramauu s smotorları teknolojisi şu anda paralel metin getirmeye dayanmaktadır. Bir par-salel metin getirme sistemi temel olarak uş bileşenden oluşmaktadır: tarayıcı,üc s sindeksleyici ve sorgu işleyici. Tarayıcı bileşeni Ağ'da bulunan sayfaları bulmayı,s s g˙getirmeyi ve yerel bir metin ambarında saklamayı amaşlar. Indeksleme bileşenic ssaklanmış olan dü zensiz metinleri sorgulanabilir bir yapıya dünüştü rü r ki bu yapıs u o us u uşoğu zaman bir ters dizindir. Sorgu işleme bileşeni ise indekslenmiş işerik uzerindecg s s sc üaramayı gerşekleştirir. Bu tezde, etkin Ağ tarama ve sorgu işleme işin modellerc s g s cve algoritmalar onerilmiştir. Paralel Ağ tarama işin, işlemciler arası iletişim mik-ü s g c s starını en aza indiren ve işlemcilerin sayfa indirme isteklerinin sayısını ve saklamasyü klerini dengeleyen karma bir model ünerilmiştir. Ek olarak, metin ve kelimeu o sbazlı ters dizin bülü mleme işin modeller onerilmiştir. Metin bülü mlemeye dayalıou c ü s oumodelimizde saklama yü kü dengelenirken sorgu işleme sırasında karşılaşılacakuu s ssdisk erişim miktarı en aza indirilmektedir. Kelime bülü mlemeye dayalı mod-s ouelimizde ise yine saklama yü kü dengelenirken toplam iletişim hacmi en azauu sindirilmektedir. Bunlara ek olarak, sıralamaya dayalı metin getirme sistem-leri işin şok sayıda sorgu işleme algoritması uygulanmış ve değerlendirilmiştir.cc s s g süOnerilen algoritmalar 48 düğumlü bir PC kü mesi uzerinde şalışmakta olan deney-ug ü u u ü cssel paralel metin getirme sistemimiz Skynet uzerinde denenmiştir. Tezde ayrıcaü sgride uyarlanmış SE4SEE arama motorumuzun tasarım ve uygulama detay-sları tartışılmıştır. Pratikteki katkılarımız arasından, SE4SEE işinde kullanılans s cHarbinger metin sınıflandırma sistemi ve onerilen modellerde kullanılmak uzereü ügeliştirilen K-PaToH hiperşizge bülü mleme aracı sunulmuştur.s c ou sAnahtar süzcükler : Arama motoru, paralel metin getirme, Ağ tarama, ters dizinou gbülü mleme, sorgu işleme, metin sınıflandırma, hiperşizge bülü mleme.ou s c ouv
ABSTRACTMODELS AND ALGORITHMS FORPARALLEL TEXT RETRIEVALBerkant Barla CambazoğlugPh.D. in Computer EngineeringSupervisor: Prof. Dr. Cevdet AykanatJanuary, 2006In the last decade, search engines became an integral part of our lives. The cur-rent state-of-the-art in search engine technology relies on parallel text retrieval.Basically, a parallel text retrieval system is composed of three components: acrawler, an indexer, and a query processor. The crawler component aims to lo-cate, fetch, and store the Web pages in a local document repository. The indexercomponent converts the stored, unstructured text into a queryable form, mostoften an inverted index. Finally, the query processing component performs thesearch over the indexed content. In this thesis, we present models and algo-rithms for efficient Web crawling and query processing. First, for parallel Webcrawling, we propose a hybrid model that aims to minimize the communicationoverhead among the processors while balancing the number of page download re-quests and storage loads of processors. Second, we propose models for document-and term-based inverted index partitioning. In the document-based partitioningmodel, the number of disk accesses incurred during query processing is minimizedwhile the posting storage is balanced. In the term-based partitioning model, thetotal amount of communication is minimized while, again, the posting storageis balanced. Finally, we develop and evaluate a large number of algorithms forquery processing in ranking-based text retrieval systems. We test the proposedalgorithms over our experimental parallel text retrieval system, Skynet, currentlyrunning on a 48-node PC cluster. In the thesis, we also discuss the design andimplementation details of another, somewhat untraditional, grid-enabled searchengine, SE4SEE. Among our practical work, we present the Harbinger text clas-sification system, used in SE4SEE for Web page classification, and the K-PaToHhypergraph partitioning toolkit, to be used in the proposed models.Keywords: Search engine, parallel text retrieval, Web crawling, inverted indexpartitioning, query processing, text classification, hypergraph partitioning.iv