Geri Dön

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

  1. Tez No: 180631
  2. Yazar: ALİ CEVAHİR
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: PageRank, Parallel Sparse-Matrix Vector Multiplication, Graph and Hypergraph Partitioning
  7. Yıl: 2006
  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 Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. Independent task assignment for heterogeneous systems

    Heterojen sistemler için bağımsız iş atama

    ERTUĞRUL KARTAL TABAK

    Doktora

    İngilizce

    İngilizce

    2013

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Bölümü

    PROF. DR. CEVDET AYKANAT

  2. 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

    Yüksek Lisans

    Türkçe

    Türkçe

    2017

    İşletmeBatman Üniversitesi

    İşletme Ana Bilim Dalı

    YRD. DOÇ. DR. ÖMER ÇOBAN

  3. 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

    Türkçe

    2007

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara Üniversitesi

    İletişim Bilimleri Ana Bilim Dalı

    DOÇ.DR. ÖZHAN TINGÖY

  4. WEB site evaluation

    WEB sitesi değerlendirme

    AHMET ŞAKİR GENÇ

    Yüksek Lisans

    İngilizce

    İngilizce

    2006

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilişim Sistemleri Ana Bilim Dalı

    DR. ALİ ARİFOĞLU

  5. 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

    Türkçe

    2011

    HemşirelikAkdeniz Üniversitesi

    Ruh Sağlığı ve Psikiyatri Hemşireliği Ana Bilim Dalı

    PROF. DR. KADRİYE BULDUKOĞLU

    YRD. DOÇ. NEŞE ZAYİM