Abstract

As the study of graphs, such as web and social graphs, becomes increasingly popular, the requirements of efficiency and programming flexibility of large graph processing tasks challenge existing tools. We propose to demonstrate Surfer, a large graph processing engine designed to execute in the cloud. Surfer provides two basic primitives for programmers - MapReduce and propagation. MapReduce, originally developed by Google, processes different key-value pairs in parallel, and propagation is an iterative computational pattern that transfers information along the edges from a vertex to its neighbors in the graph. These two primitives are complementary in graph processing. MapReduce is suitable for processing flat data structures, such as vertex-oriented tasks, and propagation is optimized for edge-oriented tasks on partitioned graphs.To further improve the programmability of large graph processing, Surfer consists of a small set of high level building blocks that use these two primitives. Developers may also construct custom building blocks. Surfer further provides a GUI (Graphical User Interface) using which developers can visually create large graph processing tasks. Surfer transforms a task into an execution plan composed of MapReduce and propagation operations. It then automatically applies various optimizations to improve the efficiency of distributed execution. Surfer also provides a visualization tool to monitor the detailed execution dynamics of the execution plan to show the interesting tradeoffs between MapReduce and propagation. We demonstrate our system in two ways: first, we demo the ease-of-programming features of the system; second, we show the efficiency of the system with a series of applications on a social network. We find that Surfer is simple to use and is highly efficient for large graph-based tasks

چکیده

از آن جا که مطالعه ی گراف ها مانند گراف های وب و گراف های اجتماعی در حال محبوب شدن است، نیازهای بهره وری و انعطاف پذیری برنامه نویسی کارهای پردازش گراف های بزرگ، ابزارهای موجود را به چالش می کشد. ما یک موتور پردازش گراف های بزرگ به نام 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 را توسعه داده ایم که به طور خودکار روی تعداد زیادی ماشین در ابر اجرا می شود و کاربران را قادر می سازد به طور موثر و راحت چنین کارهای پردازش گراف های بزرگ را توسعه دهند…