[صفحه اصلی ]   [ English ]  
بخش‌های اصلی
درباره دانشکده::
مدیریت دانشکده::
اعضای هیات علمی ::
معرفی افراد::
امور آموزش::
امور پژوهشی::
آموزش الکترونیکی::
پردیس شماره 2::
اخبار و رویدادها::
فضاهای آموزشی و تحقیقاتی ::
تسهیلات پایگاه::
::
ورود به سایت دروس

AWT IMAGE

نام کاربری
کلمه عبور

AWT IMAGE
رمز ورود را فراموش کرده‌اید؟

..
دفاعیه کارشناسی ارشد

دفاعیه کارشناسی ارشد

..
جستجو در پایگاه

جستجوی پیشرفته
..
دریافت اطلاعات پایگاه
نشانی پست الکترونیک خود را برای دریافت اطلاعات و اخبار پایگاه، در کادر زیر وارد کنید.
..
:: مرتضی علیپور لنگوری ::
 | تاریخ ارسال: ۱۳۹۴/۱۲/۱۷ | 

AWT IMAGE

آقای مرتضی علی‌پور لنگوری دانشجوی کارشناسی ارشد آقای دکتر حسن نادری روز دوشنبه  94/12/17 ساعت 10:00 در اتاق سمینار واقع در طبقه سوم دانشکده کامپیوتر از پروژه کارشناسی ارشد خود تحت عنوان "روشی جدید برای بخش‌بندی گراف‌های حجیم" دفاع نمود.

چکیده

امروزه شبکه‌های بزرگ با حجم بسیار زیاد داده‌ها نقش بسیار اساسی در جامعه و زندگی ما دارند. پردازش این حجم وسیع داده‌ها نیازمند منابع بسیار زیاد و گران می‌باشد. از این رو نیازمند ساختمان داده مناسب برای پردازش اطلاعات هستیم. یکی از این ساختمان داده‌ها گراف است. گراف یک مدل تاثیرگذار در نمایش روابط بین موجودیت­ها است. برای نمونه نشان دادن ارتباطات شبکه­ای، روابط اجتماعی، پیوند بین وب­ها، کانال­های حمل و نقل بین مکان­ها، طراحی VLSI و ترکیب‌گذاری ژنوم از گراف استفاده می­شود. در دهه اخیر ما شاهد رشد قابل توجه­ای در توانایی ذخیره­سازی و ضبط حجم بالایی از اطلاعات برخط بودیم. این اطلاعات باعث بوجود آمدن گراف­هایی در جهان واقعی شده است که تعداد رأس و یال آنها به میلیون و یا حتی بیلیون می­رسد. به دلیل حجم زیاد اطلاعات، پردازش گراف به صورت متمرکز امکان‌پذیر نخواهد بود. لذا نیازمند توزیع گراف در سطح شبکه و توزیع پردازش خواهیم بود. اگر برای پردازش گراف نیاز به انتقال حجم زیادی از داده‌ها داشته باشیم، پردازش هزینه‌بر خواهد بود. بدون بخش‌بندی گراف، ارتباطات یک عامل محدود‌کننده مهم در مقیاس‌پذیری سیستم خواهد بود. بنابراین بخش‌بندی گراف باید به گونه‌ای اعمال شود که سربار ارتباطات بین سیستم‌ها کمینه باشد. همچنین سیستم‌های متفاوتی برای پردازش گراف به صورت توزیع‌شده ارائه شده‌اند. اکثر این سیستم‌ها، مانند Giraph، GPS و... از مدل پردازشی Pregel استفاده می‌کنند که در این مدل از دید سطح گره برای پردازش گراف استفاده شده است. اما این مدل دارای کاستی‌هایی در پردازش انواع گراف بوده است. به همین دلیل سیستم‌های پردازش بلوکی گراف ارائه شده‌اند. از جمله مهم‌ترین این سیستم‌ها ExPregel و Blogel است. این سیستم‌ها دارای ویژگی‌های خاصی هستند که با توجه به آن‌ها فاکتورهای مختلفی در بخش‌بندی آن‌ها تأثیرگذار است. در این پژوهش سعی شده است با معرفی این ویژگی‌ها و مشخص کردن فاکتورهای تأثیرگذار، یک روش بخش‌بندی برای سیستم‌های پردازش بلوکی گراف ارائه شود.

واژه‌های کلیدی: گراف، بخش­بندی،پردازش بلوکی، گراف ایستا، قطر، قطر گراف ایستا، قطر گراف پویا

Abstract

Graph is an effective model to represent the relation between entities. Graphs are used to represent and model network communications, social network, web links, and road network, etc. In the recent decade, the ability to store the large volume of informathin has been increased. In order to represent and model this large volume of information, we need very large graphs which might have millions or even billions of vertices and edges. Therefore acquiring knowledge about these large graphs has become a challenge. A standard aprooch to gain knowledge about these graphs is to process them in a distributed manner. Therefore, various distributed graph processing systems have been introduced such as Giraph, GPS, ExPregel and Blogel which they are mainly based on Pregel. One of the main factors that can influence the performance of these systems is how to partition graphs in them.

Proper graph partitioning in graph processing systems can help increase the computation speed, reduce network load, and increase parallelism. Graph processing systems have various measures for partitioning based on their model developing an effective partitioning method based on the measure of a graph processing system can play a crucial role in the performance of the system. In this proposal, we propose a partitioning method for a particular group of graph processing system. In this proposal, we focus on block-centric graph processing system such as ExPregel and Blogel. We first maintain theirs main properties and then consider the factors which influence the partitioning of these systems. We propose a distributed method for partitioning of these systems. The main goal of the proposed method is to reduce the diameter of high level graph of partitioned graph. We then evaluate our method on ExPregel as a representative of block-centric graph processing systems with large-scale graphs. The evaluation shows that our method is the best partitioner for the block-centric graph processing systems.

.


مرتضی علی‌پور لنگوری

   رشته مهندسی کامپیوتر – نرم‌افزار

استاد راهنما: دکتر حسن نادری

استاد داور داخلی: دکتر محمدرضا کنگاوری

استاد داور خارجی: دکتر محمود نشاطی

  تاریخ دفاع: دوشنبه 17 اسفند ماه 94

  زمان:ساعت 10:00

 

  مکان: دانشکده مهندسی کامپیوتر- طبقه سوم- اتاق سمینار

 از اساتید بزرگوار، دانشجویان گرامی و دیگر متخصصان و علاقه مندان به موضوع دفاعیه دعوت
می شود با حضور خود موجبات غنای علمی و ارتقای کیفی را فراهم سازند.

 

  دانشکده مهندسی کامپیوتر مدیریت تحصیلات تکمیلی

 

 

 

 

 

 

دفعات مشاهده: 1339 بار   |   دفعات چاپ: 262 بار   |   دفعات ارسال به دیگران: 0 بار   |   0 نظر
سایر مطالب این بخش سایر مطالب این بخش نسخه قابل چاپ نسخه قابل چاپ ارسال به دوستان ارسال به دوستان
School of Computer Engineering
Persian site map - English site map - Created in 0.137 seconds with 967 queries by yektaweb 3433