Web-site-based partitioning techniques for efficient parallelization of the pagerank computation
Sayfadeğeri hesaplamasının etkin olarak paralelleştirilmesi için ağ sitesi tabanlı bölümleme yöntemleri
- Tez No: 180631
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: PageRank, Parallel Sparse-Matrix Vector Multiplication, Graph and Hypergraph Partitioning
- Yıl: 2006
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
A˘g arama motorları, sorgu sonucunda gelen sayfaları sıralamak i¸cin birtakım sıralama y¨ontemleri uygular. SayfaDe˘geri, a˘g sayfalarını A˘g'ın ba˘g yapısına g¨ore sıraya koyan ¨onemli bir y¨ontemdir. SayfaDe˘geri hesaplamasının etkin olması ¨onemlidir, ¸c¨unk¨u A˘g'ın s¨urekli de˘gi¸sen do˘gası bu hesaplamanın sıklıkla tekrarlanmasını gerektirir. SayfaDe˘geri hesaplaması tekrarlayan seyrek matris-vekt¨or ¸carpımları i¸cerir. Matris-vekt¨or ¸carpımı, SayfaDe˘geri hesaplamasının anahtar i¸slemidir. C¸ arpılan matrisin ¸cok b¨uy¨uk olmasından dolayı SayfaDe˘geri genellikle paralel sistemlerde hesaplanır. Fakat bu ¸cok b¨uy¨uk matrisin d¨uzensiz yapısından dolayı SayfaDe˘geri hesaplamasının verimli bir ¸sekilde paralelle¸stirilmesi kolay biri¸s de˘gildir. C¸izge ve hiper¸cizge b¨ol¨umleme y¨ontemleri matris-vekt¨or ¸carpımlarını etkin olarak paralelle¸stirilmesinde sık¸ca kullanılan y¨ontemlerdir. Yakın zamanda matris-vekt¨or ¸carpımından kaynaklanan haberle¸sme y¨uk¨un¨u azaltarak hızlı paralel SayfaDe˘geri hesaplamak i¸cin hiper¸cizge b¨ol¨umleme tabanlı bir y¨ontem ¨one s¨ur¨ulm¨u¸st¨ur. Fakat sunulan y¨ontem y¨uksek ¨on i¸sleme zamanı gerektirir. Bu da y¨ontemi s¨urekli de˘gi¸sen A˘g i¸cin pratikte elveri¸ssiz kılar. Bu ¸calı¸smada, makul bir ¨on i¸slemeyle paralel SayfaDe˘geri hesaplamasının haberle¸sme y¨uk¨un¨u azaltacak A˘g sitesi tabanlı ¸cizge ve hiper¸cizge b¨ol¨umleme modelleri sunuyoruz. Sundu˘gumuz modeller tek boyutlu (satır sıralı ve s¨utun sıralı) ve iki boyutlu (ince taneli ve dama tahtası) b¨ol¨umleme modelleridir. Modeller sadece matris-vekt¨or ¸carpımını kapsamakla kalmayıp, b¨ut¨un dolaylı algoritmayı kapsar. Y¨ur¨ut¨ulen deneyler, sunulan modellerin, ¸su ana kadar yapılan ¸calı¸smalarla kıyaslandı˘gında, d¨u¸s¨uk bir ¨on i¸sleme zamanıyla beraber hızlı SayfaDe˘geri hesaplamasını ba¸sardı˘gını g¨oz ¨on¨une koyar. Anahtar s¨ozc¨ukler : SayfaDe˘geri, Paralel Seyrek Matris-Vekt¨or C¸ arpımı, C¸izge ve Hiper¸cizge B¨ol¨umleme.
Özet (Çeviri)
Web search engines use ranking techniques to order Web pages in query results. PageRank is an important technique, which orders Web pages according to the linkage structure of the Web. The efficiency of the PageRank computation is important since the constantly evolving nature of the Web requires this computation to be repeated many times. PageRank computation includes repeated iterative sparse matrix-vector multiplications. Due to the enormous size of the Web matrix to be multiplied, PageRank computations are usually carried out on parallel systems. However, efficiently parallelizing PageRank is not an easy task, because of the irregular sparsity pattern of the Web matrix. Graph and hypergraphpartitioning-based techniques are widely used for efficiently parallelizing matrixvector multiplications. Recently, a hypergraph-partitioning-based decomposition technique for fast parallel computation of PageRank is proposed. This technique aims to minimize the communication overhead of the parallel matrix-vector multiplication. However, the proposed technique has a high prepropocessing time, which makes the technique impractical. In this work, we propose 1D (rowwise and columnwise) and 2D (fine-grain and checkerboard) decomposition models using web-site-based graph and hypergraph-partitioning techniques. Proposed models minimize the communication overhead of the parallel PageRank computations with a reasonable preprocessing time. The models encapsulate not only the matrix-vector multiplication, but the overall iterative algorithm. Conducted experiments show that the proposed models achieve fast PageRank computation with low preprocessing time, compared with those in the literature.
Benzer Tezler
- Independent task assignment for heterogeneous systems
Heterojen sistemler için bağımsız iş atama
ERTUĞRUL KARTAL TABAK
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Time domain based web usage mining for web site improvement
Web site gelişimi için zamana bağımlı web kullanım motiflerinin çıkarılması
ALPAY ERDEM
Yüksek Lisans
İngilizce
2002
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ATTİLA GÜRSOY
YRD. DOÇ. DR. UĞUR DOĞRUSÖZ
- Metin madenciliği tabanlı bir web sitesi sınıflandırma aracı tasarımı
A web site classification tool design based on text mining
FİLİZ ERTEN
Yüksek Lisans
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMaltepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ŞENOL ZAFER ERDOĞAN
- Seçim sonuçlarını yayınlayan .net tabanlı bir web sitesinin tasarımı: 2002 Türkiye genel seçimi
Designing of a web site that is .net based and broad cast election results: 2002 Turkey general election results
UFUK YALÇIN
Yüksek Lisans
Türkçe
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi ÜniversitesiElektronik ve Bilgisayar Eğitimi Ana Bilim Dalı (disiplinlerarası)
YRD. DOÇ. DR. HALİM HALDUN GÖKTAŞ
- KTÜ BÖTEB için bir WEB tabanlı eğitim sitesi geliştirilmesi ve kullanılabilirliğinin incelenmesi
Development of a WEB based instructional site for KTÜ BÖTEB and investigation of its usability
SAKİNE ŞENSOY
Yüksek Lisans
Türkçe
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKaradeniz Teknik ÜniversitesiBilgisayar ve Öğretim Teknolojileri Eğitimi Ana Bilim Dalı
PROF.DR. ADNAN BAKİ