کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6873305 1440633 2018 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Partitioning big graph with respect to arbitrary proportions in a streaming manner
ترجمه فارسی عنوان
تقسیم بندی نمودار بزرگ با توجه به نسبت های دلخواه به شیوه جریان
کلمات کلیدی
تقسیم بندی نمودار، نسبت های دلخواه، طرح اندازه گیری، جریان اکتشافی، متریک،
ترجمه چکیده
استفاده از یک گره محاسباتی یک محصول برای پارتیشن کردن نمودار بزرگ بسیار دشوار است. این کار در حال بررسی چگونگی پراکندگی یک نمودار بزرگ با توجه به نسبت های دلخواه به شیوه جریان است. برای رعایت الزامات مختلف سناریوهای پارتیشن بندی گراف، ابتدا 3 طرح اندازه گیری برای اندازه گیری تعداد رأس گراف، بار کاری گراف و زمان پردازش گراف به کار برده می شود. این طرحها پایه و پیش نیاز برای پارتیشن بندی بزرگ است. با توجه به دشواری در کسب اطلاعات کامل گراف بزرگ، پس از آن 8 جریان اکتشافی جریان را برای پارتیشن بندی یک نمودار بزرگ در طی فرآیند بارگیری داده های خود از دیسک های خارجی به حافظه طراحی می کنیم. هر یک از این اکتشافات تصمیم می گیرد که هر رأس را در جریان بر اساس اطلاعات محاسبه شده توسط یکی از 3 طرح فوق قرار دهد. در نهایت، ما عملکرد و انعطاف پذیری اکتشافات ما را در پارتیشن بندی مجموعه داده های گراف و داده های واقعی مصنوعی بر روی یک خوشه متوسط ​​می بینیم. ویژگی های نسبت های دلخواه رویکرد ما این است که طیف وسیعی از برنامه ها را داشته باشد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
تقسیم بندی نمودار بزرگ با توجه به نسبت های دلخواه به شیوه جریان
چکیده انگلیسی
Using a single commodity computational node to partition big graph is very difficult. This work studies how to partition a big graph with respect to arbitrary proportions in a streaming manner. To meet diverse requirements of big graph partitioning scenarios, we first devise 3 measurement schemes for measuring the graph vertex count, graph workload, and graph processing time, respectively. These schemes are the bases and prerequisites for big graph partitioning. Due to the difficulty in acquiring full big graph information, we then design 8 streaming heuristics to partitioning a big graph during the process of loading its data from external disks into memory. Each of these heuristics decides where to assign every vertex in the stream based on the information calculated by one of the above 3 schemes. At last, we demonstrate the performance and flexibility of our heuristics in partitioning real and synthetic graph datasets on a medium-sized cluster. The characteristics of arbitrary proportions of our approach makes it have a wide range of applications.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Future Generation Computer Systems - Volume 80, March 2018, Pages 1-11
نویسندگان
, , , ,