کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6856652 1437967 2018 38 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parallel algorithms for flexible pattern matching on big graphs
ترجمه فارسی عنوان
الگوریتم های موازی برای تطبیق الگوی انعطاف پذیر در نمودارهای بزرگ
کلمات کلیدی
پرس و جو نمودار شبیه سازی گراف، الگوریتم های توزیع شده، شبیه سازی قوی،
ترجمه چکیده
شبیه سازی قوی یک روش تقریبی از لحاظ پیشرفته در تطبیق الگوی گراف است. این طرح همیشه نتایج با کیفیت بالا را در مقایسه با طرح های دیگر پیدا می کند. با این حال، به عنوان وب و شبکه های اجتماعی به طور فزاینده ای در زندگی انسان استفاده می شود، مقیاس داده ها بسیار بزرگ است. در نتیجه، چنین نمودارهای بزرگی اغلب در محیط توزیع شده ذخیره می شوند تا بتوانند به طور موثر مدیریت شوند. متاسفانه، الگوریتم توزیع فعلی برای شبیه سازی قوی کارآمد نیست و نمی تواند به برنامه های واقعی اعمال شود. در این مقاله، ما الگوریتم های موثر موثر برای شبیه سازی قوی در تنظیم توزیع پیشنهاد می کنیم. این سهم شامل موارد زیر است: (1) ما محاسبه شبیه سازی قوی را برای محاسبه مجموعه ای نسبی از نتایج جزئی برای هر پارتیشن الگوی مناسب برای سیستم توزیع تبدیل می کنیم. (2) ما یک روش برای کاهش حمل و نقل داده ها و پیچیدگی زمان محاسبات محلی در محیط توزیع را توسعه می دهیم. (3) محاسبه توزیع شده شبیه سازی قوی را به الگوریتم توزیع مجدد آفلاین و یک الگوریتم تطبیق آنلاین تقسیم می کنیم. انتقال عمده داده ها در الگوریتم آفلاین دخالت دارد، در حالی که الگوریتم آنلاین بسیار موازی و بسیار کارآمدتر از الگوریتم های فعلی است. (4) با آزمایش بر روی داده های واقعی و مصنوعی، ما کارایی الگوریتم های توزیع شده ما و اثربخشی طرح ما را بدون نتایج متوسط ​​می سنجیم.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش مقاله
الگوریتم های موازی برای تطبیق الگوی انعطاف پذیر در نمودارهای بزرگ
چکیده انگلیسی
Strong simulation is a state-of-the-art approximate scheme in graph pattern matching. This scheme always finds high-quality results compared to other schemes. However, as the Web and social networks are increasingly used in human lives, the scale of the data grows extremely large. As a result, such big graphs are often stored in the distributed environment, in order to be managed efficiently. Unfortunately, current distributed algorithm for strong simulation is not efficient and cannot be applied to real applications. In this paper, we propose efficient parallel algorithms for strong simulation in the distributed setting. The contribution includes (1) We convert the calculation of strong simulation to calculating a relative small set of partial results for each partition of pattern suitable for distributed system. (2) We develop a method to reduce data shipment and time complexity of local computation in the distributed setting. (3) We split the distributed calculation of strong simulation into an offline redistribution algorithm and an online matching algorithm. The major data shipment is involved in the offline algorithm, while the online algorithm is highly parallel and much more efficient than current algorithms. (4) By experiments on both real and synthetic data, we verify the efficiency of our distributed algorithms and the effectiveness of our scheme without large intermediate results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volumes 436–437, April 2018, Pages 418-440
نویسندگان
, , , ,