استخراج زیرگرافهای تکرارشونده با توزیع متوازن بار درنگاشت-کاهش مبتنی بر واحد پردازش گرافیکی

با گسترش روز افزون دادهها، چالشهای بنیادینی برای به دست آوردن اطلاعات از مجموعه عظیمی از دادهها ظهورپیدا کرده است. استخراج زیرگرافهای تکرارشونده یکی از مسایل مهم در کاوش مجموعه بزرگی از گرافها است. این موضوعدر زمینههای کاربردی زیادی نظیر: انفورماتیک پزشکی، شبکههای اجتماعی و ترکیبات شیمیایی و غیره دارای اهمیت زیادی نیز میباشد. هادوپ یک رویکرد بسیار قابل قبول برای مدیریت حجم عظیمی از دادهها است و همچنین برای تسریعمحاسبات، استفاده از امکانات موازیسازی GPU بسیار مناسب است. با مجتمع سازی GPU درون هادوپ میتوان از مزایایهر دو به صورت همزمان استفاده نمود. در این مقاله، با در نظر گرفتن یک روش بخشبندی بر اساس تراکم گرافها به کمک الگوریتم WFD و با استفاده از هادوپ تکراری مبتنی بر GPU ، روش نوینی به نام CH-FSM برای استخراج زیرگرافهایتکرارشونده در مقیاس بزرگ ارایه میگردد. از نظر برگرداندن تمامی زیرگرافهای تکرارشونده برای حداقل درجه پشتیبانی مشخصشده، CH-FSM یک روش کامل میباشد. نتایج آزمایشهای جامع انجام گرفته بر روی مجموعههای داده واقعی ومصنوعی نشان میدهد که روش CH-FSM به تسریع 1/5 برابری در مقابل آخرین روش ارایه شده برای استخراج کامل زیرگرافهای تکرارشونده مبتنی بر نگاشت-کاهش دست یافته است

Keywords:

نگاشت-کاهش , استخراج زیرگرافهای تکرارشونده , هادوپ , کودا , واحد پردازش گرافیکی , توزیع متوازن