دانلود مقاله بهینه سازی پرس و جو با تطبیق الگوی توزیعی

چکیده:
الگوریتم های حریصانه برای عملیات تطبیق الگوی گراف اغلب زمانی که داده های گراف را بتوان در حافظه بر روی تک ماشین نگه داری کرد کافی می باشد. با این حال، چون مجموعه داده های گراف به طور فزاینده ای توسعه می یابند و نیاز مند فضای ذخیره ای اضافی و پارتیشن بندی در دسته ای از ماشین ها می باشند، فنون بهینه سازی پرس و جوی پیشرفته تر برای اجتناب از انفجار در تاخیر پرس و جو اهمیت حیاتی دارد.در این مقاله، ما اقدام به معرفی روش های بهینه سازی پرس و جو برای تطبیق الگوی گراف توزیع یافته می کنیم. این فنون شامل، 1- الگوریتم بهینه سازی مبتنی بر برنامه نویسی دینامیک سبک سیستم R، که هر دو برنامه های خطی و نقطه ای را در نظر می گیرد، 2- الگوریتم مبتنی بر تشخیص چرخه که اهرمی برای چرخه ها جهت کاهش اندازه مجموعه های نهایی می باشد و 3- روش استفاده مجدد از محاسبه یا رایانش است که انتقال اطلاعات و اجرای پرس و جوی زائد را در شبکه حذف می کند. نتایج آزمایشی نشان می دهد که این الگوریتم ها می توانند موجب بهبود زیادی در عملکرد پرس و جو شوند.

1-مقدمه
مدل داده های گراف، یک شیوه بسیار محبوب برای زمینه های مختلف محسوب می شود. از دلایل این محبوبیت می توان به موارد زیر اشاره کرد:1- برای خلاصه سازی داده های پراکنده و یا نیمه ساختاری به مدل های داده های راس-لبه-راس نسبت به مدل های داده های سنتی ساده تر است 2- برخی از مجموعه داده های محبوب( نظیر شبکه های تویتر، فیسبوک و لینکدین) در مورد استفاده از پارادایم گراف منطق و استدلال طبیعی دارند و 3- عملیات گراف نظیر محاسبات با کوتاه ترین مسیر،، تطبیق الگوی زیر گراف و پیج رنک به آسانی نسبت به مدل داده های گراف بیان می شوند.

بسیاری از مجموعه داده های گراف آن قدر بزرگ هستند که مدیریت آن ها بر روی یک ماشین سخت بوده و از این روی دسته ای از ماشین ها برای پردازش، ذخیره، مدیریت و تحلیل داده های گراف به کار برده می شوند. برای مثال، از سال 2012، گراف کاربر فیسبوک دارای 900 میلیون راس( درجه متوسط راس، 130 است) می باشد(1). در جامعه وب معنایی، جنبش داده های اپن لینکینگ، 6 میلیون تریپل را ( یک تریپل، برابر باست با یک لبه در یک گراف) از 300 مجموعه داده به هم پیوسته جمع اوری کرده است. از آن جا که بسیاری از الگوریتم های گراف در اصل با این فرض طراحی شده اند که گراف کامل را می توان در مموری بر روی یک ماشین ذخیره سازی کرد، معماری های توزیع یافته فوق نیاز به بازبینی این الکوریتم ها در زمینه توزیعی می باشند زیرا ملاحظاتی نظیر نهفتگی شبکه و بازدهی می تواند مانع از اجرای متعارف این الگوریتم ها شود.

تطبیق الگوی زیر گراف یک عملیات بسیار مهم می باشد که باید برای ذخایر گراف توزیعی باز بینی شود. عملیات تطبیق زیر گراف در عملیات داده کاوی شبکه اجتماعی( شمارش مثلث ها برای اندازه گیری اثر اجتماعی مراسم ها)، پرس و جو هایSPARQL در گراف داده های لینک شده و الگوریتم های یادگیری ماشین که موجب راه اندازی موتور ها برای سرگرمی و ابزار های تجارت الکترونیکی به شدت استفاده می شود.

مقاله حاضر به طور صریحی از روش های برنامه نویسی دینامیک سبک سیستم r استفاده می کند تا تطبیق الگوی زیر گراف توزیعی را بهینه سازی کند. با این حال، پی برده شد که این الگوریتم های متعارف باید به سه طریق اصلاح شوند تا عملکرد خوبی برای داده های گراف داشته باشند.

• اگرچه سایرین خاطر نشان کرده اند که حتی در زمینه های نسبی متعارف، مسئله سیستم R از درختان منجر به راهبرد بهینه سازی نیمه بهینه می شود، در نظر گرفتن برنامه های نقطه ای برای پرس و جو های تطبیق الگوی گراف توزیعی از اهمیت زیادی برای کاهش ترافیک شبکه و اندازه خروجی های میانی برخوردار است. بحی اکتشافی که برای آن ها طرح های نقطه ای در نظر گرفته می شوند باید اهرم خصوصیات گراف باشد.

• چرخه ها به طور مکرر در الگوهای پرس و جو در مدل گراف نسبت به داده های نشان داده شده در مدل های دیگر ظاهر می شوند. آن ها را می توان طوری اهرم بندی کرد که موجب بهبود عملکرد پرس و جو شده و به طور صریح طی تولید برنامه در نظر گرفته شوند.

• به طور کلی، تطبیق الگوی توزیعی زیر گراف با یافتن مولفه هایی از زیر گراف و اتصال این مولفه ها به هم انجام می شود. با این حال وقتی که الگوهای گراس خالص مورد جست و جو باشند، مجموعه های میانی حاصله، اندازه شان بزرگ تر می شود.