دانلود مقاله ترجمه شده پردازش گراف های بزرگ در ابر

چکیده

از آن جا که مطالعه ی گراف ها مانند گراف های وب و گراف های اجتماعی در حال محبوب شدن است، نیازهای بهره وری و انعطاف پذیری برنامه نویسی کارهای پردازش گراف های بزرگ، ابزارهای موجود را به چالش می کشد. ما یک موتور پردازش گراف های بزرگ به نام Surfer را معرفی می کنیم که برای اجرا در ابر طراحی شده است. Surfer دو عنصر پایه را فراهم می کند: نگاشت کاهش MapReduce و انتشار. MapReduce که توسط گوگل توسعه پیدا کرده است، جفت های کلید- مقدار مختلف را به صورت موازی پردازش می کند و انتشار یک الگوی محاسباتی تکراری است که اطلاعات موجود در لبه های منتهی به یک رأس را به همسایگانش در گراف منتقل می کند. این دو عنصر پایه در پردازش گراف مکمل یکدیگر هستند. MapReduce برای پردازش ساختمان داده های مسطح مانند کارهای مبتنی بر رأس مناسب است و انتشار برای کارهای مبتنی بر لبه در گراف های تقسیم بندی شده بهینه گشته است. برای بهبود بیشتر قابلیت برنامه ریزی پردازش گراف های بزرگ، Surfer از یک مجموعه ی کوچک از بلاک های سازنده  سطح بالا تشکیل شده که این دو عنصر پایه را به کار می برند. ممکن است توسعه دهندگان نیز بلاک های سازنده سفارشی بسازند. Surfer یک رابط کاربری گرافیکی فراهم می کند که توسعه دهندگان می توانند با استفاده از آن کارهای پردازش گراف های بزرگ را به صورت دیداری ایجاد کنند. Surfer یک کار را به یک برنامه ی اجرای ساخته شده از عملیات MapReduce و انتشار تبدیل می کند. سپس به طور خودکار بهینه سازی های متنوعی اعمال می کند تا بهره وری اجرای توزیع شده را بهبود بخشد. هم چنین Surfer یک ابزار تجسم برای نظارت کردن بر دینامیک اجرایی همراه با جزئیات از برنامه ی اجرا فراهم می کند تا موازنه ی بین MapReduce و انتشار را نشان دهد. ما سیستم خود را به دو شیوه شرح می دهیم: ابتدا با استفاده از دموی نرم افزار ویژگی های آسان برنامه نویسی سیستم را نشان می دهیم؛ سپس بهره وری سیستم را با استفاده از یک سری از اپلیکیشن ها در یک شبکه ی اجتماعی نشان می دهیم. ما در می یابیم که استفاده از Surfer ساده است و برای کارهای مبتنی بر گراف های بزرگ به شدت مفید است.

1-مقدمه

پردازش گراف های بزرگ برای اپلیکیشن های مختلفی مانند مطالعه ی شبکه های وب و شبکه های اجتماعی رایج شده است [6, 7, 11]. بیشتر کارهای پردازشی، کارهای دسته ای هستند که در آن ها به رئوس و لبه های گراف دسترسی پیدا می شود. نمونه هایی از آن PageRank [10]، گراف وب پیوند معکوس، two-hop friend list، تحلیل اثرات شبکه های اجتماعی [12] و سیستم های توصیف گر [11]. به خاطر تنوع نیازهای کاربر، گرایش به این وجود دارد که این کارها با کد تعریف شده توسط کاربر سفارشی شوند. ما یک موتور گراف های بزرگ به نام Surfer را توسعه داده ایم که به طور خودکار روی تعداد زیادی ماشین در ابر اجرا می شود و کاربران را قادر می سازد به طور موثر و راحت چنین کارهای پردازش گراف های بزرگ را توسعه دهند…