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ı: 90
Ö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
- Bölgesel kalkınma ajanslarının kurumsal kimlik bileşenlerinin incelenmesine yönelik bir araştırma
A research on examining regional development agencies' corporate identity components
AYŞE GÜL SAVAŞKAN
- Grafik kullanıcı arayüzlerinde metaforların kültürlerarası kavranışı (Fransa ve Türkiye'de bir e-öğrenim sitesi üzerinden karşılaştırmalı bir çalışma)
The cross-cultural understanding of the metaphors in the graphical user interfaces (a comparative study in France and Turkey on an e-learning site)
KEREM RIZVANOĞLU
Doktora
Türkçe
2007
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesiİletişim Bilimleri Ana Bilim Dalı
DOÇ.DR. ÖZHAN TINGÖY
- WEB site evaluation
WEB sitesi değerlendirme
AHMET ŞAKİR GENÇ
Yüksek Lisans
İngilizce
2006
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilişim Sistemleri Ana Bilim Dalı
DR. ALİ ARİFOĞLU
- Hemşireler için web tabanlı iletişim eğitimi programının hazırlanması ve kullanımının değerlendirilmesi
Preparation the web based communication program for nurses and evaluation usage of this program
ESRA USLU
Yüksek Lisans
Türkçe
2011
HemşirelikAkdeniz ÜniversitesiRuh Sağlığı ve Psikiyatri Hemşireliği Ana Bilim Dalı
PROF. DR. KADRİYE BULDUKOĞLU
YRD. DOÇ. NEŞE ZAYİM