کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10358606 868555 2013 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A map-reduce lagrangian heuristic for multidimensional assignment problems with decomposable costs
ترجمه فارسی عنوان
یک نقشه کاهش اکتشافی لاگرانژ برای مشکلات تکلیف چند بعدی با هزینه های قابل تجزیه
کلمات کلیدی
ارتباط داده ها، مشکل تکلیف چند بعدی، اوجوری لاگرانژی، نقشه کاهش چارچوب،
ترجمه چکیده
اتصال داده ها مشکل شناسایی زمانی است که منابع داده های چندگانه همان موجودیت را مشاهده کرده اند. مسأله مرکزی برای این تلاش، مسئله تخصیص چند بعدی است که اغلب برای تشکیل مشکلات مرتبط با داده ها استفاده می شود. ماهیت مشکلات ارتباطات داده ها، روش های راه حل برای مسئله انتساب چند بعدی را سریعا به نتیجه می رساند و بر روی مجموعه داده های بزرگ کار می کند. سهم این کار این است که یک اکتشاف مبتنی بر آرامش لاگرانژی برای مسئله تخصیص چند بعدی با هزینه های تقسیم شده توصیف کند که عمدتا در یک چارچوب کاهش نقشه اجرا می شود و به راحتی در میان خوشه ای از کامپیوترها توزیع می شود. توزیع اجازه می دهد تا اکتشافی برای پاسخ دادن به زمان اجرا و نیازهای داده های بزرگ مرتبط با داده ها. الگوریتم توسعه یافته بر روی یک مجموعه داده های سنتی مورد آزمایش قرار گرفته و برای رسیدن به یک فاصله مطلوب از 0.00008٪ تا 0.6٪ برای مشکلات متراکم (بدون فیلتر کردن) با داشتن 10،000 مشاهدات نشان داده شده است. توزیع الگوریتم نشان می دهد کاهش قابل توجهی در زمان اجرا در 30،000 مشکل مشاهده برای یک خوشه محاسباتی 8 گره با 96 پردازنده بیش از یک گره تک با 12 پردازنده.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نرم افزارهای علوم کامپیوتر
پیش نمایش مقاله
یک نقشه کاهش اکتشافی لاگرانژ برای مشکلات تکلیف چند بعدی با هزینه های قابل تجزیه
چکیده انگلیسی
Data association is the problem of identifying when multiple data sources have observed the same entity. Central to this effort is the multidimensional assignment problem, which is often used to formulate data association problems. The nature of data association problems dictate that solution methods for the multidimensional assignment problem must return results promptly, and work on large data sets. The contribution of this work is to describe a Lagrangian relaxation based heuristic for the multi-dimensional assignment problem with decomposable costs that can be largely implemented in a map-reduce framework and thus easily distributed across a cluster of computers. Distribution allows the heuristic to address run time and large data requirements of data association. The developed algorithm is tested on a synthesized dataset, and shown to achieve an optimality gap ranging from 0.00008% to 0.6% for dense (no filtering) problems having 10,000 observation. Distribution of the algorithm was found to offer a significant reduction in run time on 30,000 observation problems for an 8 node computing cluster with 96 processors over a single node with 12 processors.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Parallel Computing - Volume 39, Issue 11, November 2013, Pages 653-668
نویسندگان
, ,