Web-site-based partitioning techniques for efficient parallelization of the pagerank computation

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.