فایل اصلی 12 صفحه فایل ترجمه 16 صفحه به صورت ورد و پی دی اف
چکیده- الگوریتم های موجود کنکاو برابر برای مجموعه اقلام تکرار شونده فاقد مکانیسمی است که برابر سازی اتوماتیک، بارگذاری بالانس، توزیع داده و تحمل خطا روی دسته های بزرگ را ممکن سازد. به عنوان راه حلی برای این مشکل، ما یک الگوریتم کاوی مجموعه اقلام تکرار شونده مساوی موسوم به FiDoop را با استفاده از مدل برنامه نویسی مپ ردیوس طراحی کردیم. برای رسیدن به ذخیره فشرده و اجتناب از ساخت مبنای شرایطی ساخت، FiDoop درخت الترامتریک اقلام تکرار شونده را بیشتر از درخت FP متداول ترکیب می کند. در FiDoop، سه کار مپ ردیوس اجرا شده است تا وظایف کاوی تکمیل شود. در کار قاطع سوم مپ ردیوس، طراحان مستقلا مجموعه اقلام را تجزیه می کنند، تجزیه کننده عملیات ترکیبی را با ساخت درخت های الترامتریک کوچک و کنکاو واقعی این درخت ها به صورت جداگانه اجرا می کند. ما فی دوپ را روی دسته هادوپ درونی پیاده سازی کردیم. ما نشان دادیم که فیدوپ روی دسته به توزیع داده و ابعاد حساس است چون مجموعه اقلام با طول های مختلف تجزیه و هزینه های ساخت مختلفی دارند. برای بهبود عملکرد فیدوپ، ما یک معیار تعادل حجم کار را برای اندازه گیری تعادل بارگذاری در کل نودهای محاسباتی دسته را توسعه دادیم. ما فیدوپ-اچ دی یک بخش فرعی فیدوپ را توسعه دادیم تا عملکرد کاوی برای آنالیز داده بعد بالا را سرعت بخشیم. آزمایش های گسترده با استفاده از داده های طیفی سلستیال شرح می دهد که راه حل مطرح شده کارا و مقیاس پذیر است.
فهرست اصطلاحات- مجموعه اقلام تکرار شونده، درخت الترامتریک اقلام تکرار شونده، دسته هادوپ، تعادل بارگذاری، مپ ردیوس.
1. مقدمه
کنکاو مجموعه اقلام تکرار شونده (FIM) مشکل اصلی در ارتباط با قانون کاوی (ARM)، ترتیب کاوی و شبیه این است. سرعت بخشی به فرایندهای FIM حیاتی و ضروری است، چون مصرف FIM برای بخش مهمی از زمان کاوی به علت مصرف بالایش و شدت ورودی/خروجی حساب می شود. وقتی مجموعه داده در برنامه های داده های کاوی مدرن خیلی بزرگ می شود، توالی الگوریتم های FIM اجرا شده روی ماشین تکی از خرابی عملکرد آسیب می بیند. برای بررسی این مسئله، ما بررسی می کنیم چگونه FIM را با استفاده از مپ ردیوس، یک مدل برنامه نویسی پذیرفته شده برای پردازش مجموعه داده های کلان با بهره وری از برابری بین نودهای محاسباتی یک دسته را اجرا کنیم. ما نشان دادیم چگونه یک مجموعه داده بزرگ روی این دسته را برای تعادل بارگذاری در کل همه نودهای دسته را توزیع کنیم، که به موجب آن عملکرد برابر FIM بهینه سازی می شود.
الگوریتم های کاوی مجموعه اقلام تکرار شونده می تواند به دو گروه موسوم به طرح های Apriori و رشدFP تقسیم شوند. Apriori یک الگوریتم کلاسیک با استفاده از فرایندهای تولید-و-تست است که تعداد زیادی از مجموعه اقلام منتخب را تولید می کند؛ Apriori باید مکررا یک پایگاه داده کامل را اسکن کند. برای کاهش زمان مورد نیاز اسکن پایگاه داده، هان و همکاران رویکرد جدید موسوم به رشد FP را مطرح کردند، که از تولید مجموعه اقلام منتخب جلوگیری می کرد. اغلب الگوریتم های FIM موازی قبلا توسعه یافته روی الگوریتم Apriori ساخته شده اند. متاسفانه، در الگوریتم های FIM مساوی شبیه Apriori، هر پردازنده باید یک پایگاه داده چند زمانه را اسکن کند تا تعداد وسیعی از مجموعه اقلام منتخب با پردازنده های دیگر را مبادله کند. بنابراین، راه حل FIM برابر شبیه Apriori از مشکلات بالقوه همگام سازی سربار و I/Oزیاد رنج می برد، که آن را شدید می سازد تا این الگوریتم موازی را به نسبت ثابت افزایش دهد. مشکل مقیاس پذیری با اجرای مقداری از الگوریتم های FIM برابر شبیه رشدFP بررسی شده است. یک عیب بزرگ الگوریتم های برابر شبیه رشد FP ، هرچند در عدم امکان پذیری تاکید دارد تا درخت های FP حافظه را برای سازگاری با پایگاه داده مقیاس بزرگ بسازد. این مشکل بیشتر وقتی مشخص می شود که با پایگاه داده های انبوه و چند بعدی همراه است.
بیشتر از بررسی Apriori و رشد FP، ما درخت الترامتریک اقلام تکرار شونده در طرح تکنیک FI, مساوی مان را ترکیب کردیم. ما روی درخت FIU به دلیل چهار فایده برجسته اش تاکید می کنیم، که شامل کاهش سربار I/O، پیشنهاد یک روش طبیعی پارتیشن بندی مجموعه داده، ذخیره فشرده و گردش بازگشتی انحرافی می شود. خیلی مهم تر، الگوریتم های برابر موجود فاقد مکانیسمی است که برابرسازی اتوماتیک، تعادل بارگذاری، توزیع داده و تحمل اشتباه روی دسته های محاسباتی بزرگ را ممکن می سازد. برای حل مشکلات ذکر شده، ما یک الگوریتم برابر FIM موسوم به فی دوپ با استفاده از مدل برنامه نویسی هادوپ را طراحی کردیم ([14]-[17] را برای جزئیات مپ ردیوس ببینید.)
در مقایسه با الگوریتم درخت الترامتریک اقلام تکرار شونده موجود، فی دوپ خصوصیات مجزایی دارد. در فی دوپ، ترسیم کننده مستقلا و همزمان مجموعه اقلام را تجزیه می کند؛ کاهش دهنده عملیات ترکیبی را با استفاده ساخت درخت های الترامتریک کوچک بعلاوه کاوش این درخت های برابر اجرا می کند. ما فیدوپ را در دسته درونی هادوپ اجرا کردیم. ما مشاهده کردیم که پارتیشن بندی و توضیح داده مسئله مهمی در فیدوپ است، چون مجموعه اقلام با طول های مختلف تجزیه مختلفی و هزینه ساخت دارند. برای بهینه سازی عملکرد فیدوپ، ما یک روش پارتیشن بندی جدید داده را مطرح کردیم تا به خوبی بارگذاری محاسباتی در بین نودهای دسته را بالانس کند؛ ما فیدوپ-اچ دی ، یک گسترش فیدوپ، را برای براوردن نیازهای پردازنده داده های ابعاد بالا توسعه دادیم.
نقش اصلی این مقاله مانند زیر سازماندهی شده است.
1) ما یک تعمیر اساسی برای FIUT ساختیم (یعنی روش تکرار شوند درخت الترامتریک اقلام)، و مسایل عملکرد برابر سازی FIUT را بررسی کردیم.
2) ما روش کاوی مجموعه اقلام تکرار شونده برابر را با استفاده از مدل برنامه نویسی مپ ردیوس توسعه دادیم.
3) ما یک طرح توزیع داده را مطرح کردیم تا بارگذاری بین نودهای محاسباتی در یک دسته را بالانس کند.
4) ما بیشتر عملکرد فیدوپ را بهینه کردیم و زمان اجرای پردازش مجموعه داده ابعاد بالا را کاهش داده ایم.
5) ما آزمایشات وسیعی با استفاده از یک دامنه وسیع ترکیب مجموعه داده دنیای واقعی را اجرا کردیم، و نشان دادیم که فیدوپ کارا و مقیاس پذیر روی دسته های هادوپ است.
