دانلود رایگان ترجمه مقاله به کارگیری الگوریتم انرژی پیوند اصلاح شده در پایگاه های داده توزیع شده (ساینس دایرکت – الزویر 2015)

مبتدی (مناسب برای درک مفهوم کلی مطلب) 

2. روش ها
تخصیص و تکه تکه شدن مشکلاتی مرتبط به یکدیگر هستند که حل آنها به طور همزمان دشوار می باشد ولی منجر به عملکرد بهتر در نرم افزار ها خواهد شد . برای بهترین دانش ما ، BEA به طور همزمان بر روی تخصیص و تکه تکه شدن اعمال نمی شود . زیرا در پارتیشن بندی عمودی ویژگی هایی که معمولا با هم دیده می شوند معمولا در یک قطعه قرار می گیرند ، و اندازه گیری دقیق آنها با یکدیگر ضروری می باشد .BEA از وابستگی ویژگی ها برای ایجاد خوشه هایی از ویژگی ها استفاده می کند که بیشتر شبیه هم هستند . آن را با استفاده از ویژگی (AU) و دسترسی به کوئری (QA) ماتریس ویژگی های وابستگی (AFF) و در نهایت خوشه های ماتریس وابستگی (CA) به وسیله در موقعیت قرار دادن و مجددا در موقعیت قرار دادن ستون ها و سطر هایی از ویژگی ها صورت می پذیرد . اندازه گیری وابستگی ها بسیار ساده است . اندازه گیری این وابستگی ارائه شده در BEA اصولا بر اساس دسترسی همزمان به ویژگی مبتنی برAi و ویژگی Aj از رابطه R(A1,A2,…,An) با کوئری qk برای هر کوئری در Q=(q1,q2,…,qn) است . به عبارت دیگر ، دو ویژگی زمانی شبیه به هم در نظر گرفته می شوند که اگر با یک کوئری بتوان هر دوی آنها را دید . این موضوع را با AU به وسیله Aij=1 و Aik=1 به طور همزمان برای ویژگی j و k که به وسیله کوئری i دیده شده است می باشد و با در نظر گیری تمایلات ویژگی های Ai و Aj به عنوان aff(Ai,Aj) صورت می پذیرد ، تعداد تکرار دسترسی به کوئری K بر سایت I را به شکل Freq1(qk) نشان می دهیم ، و دسترسی به اجرای کوئری K بر سایت I را به شکل acc1(qk) نشان می دهیم ، معادله برای این وابستگی به شکل زیر ارائه شده است :

پس از تولید AFF با استفاده از اندازه گیری وابستگی توصیف شده ، خوشه هایی از ویژگی ها با استفاده از تابع تقسیم ایجاد می شود. Split(AFF) ماتریس AFF را به عنوان ورودی می گیرد ، و ستون ها و سطر های آن را تغییر می دهد و سپس ماتریس CA را تولید می کند. جایگشت سپس در راهی صورت می گیرد که سبب به حداکثر رسیدن اندازه گیری های جهانی زیر شود.

مقدار دهی اولیه: یکی از ستون های ماتریس وابستگی AFF را در داخل ماتریس CA تنظیم می کند و قرار می دهد.
تکرار: هر کدام از n-i ستون های باقی مانده را که در آنها i شماره ستون هایی است که در حال حاضر در CA قرار گرفته اند را بر می دارد و سپس سعی می کند آن را در باقی مانده i+1 موقعیت ها در CA قرار دهد . انتخاب محل قرار گیری سبب می شود که بیشترین سهم اندازه گیری وابستگی جهانی که در بالا توضیح داده شد به وقوع بپیوندد . این قضیه را انقدر ادامه می دهیم که دیگر هیچ ستونی برای قرار دادن باقی نمانده باشد .
از آنجایی که نتیجه خوشه بندی BEA مرز تقسیم شده بین دو مجموعه از ویژگی ها است ، BEA برای پایگاه داده های بزرگ به خوبی عمل نمی کند . بنابراین ، ما نیاز به یک روش بهتر برای شناسایی نامزدهای پارتیشن بندی داریم . همانطور که ما متوجه شدیم شباهت های دو ویژگی زمانی است که آنها به طور همزمان در یک کوئری رخ می دهند ، عدم وجود همزمانی آنها در یک کوئری سبب می شود که ما اینگونه برداشت کنیم که وزن اندازه گیری شده برای شباهت های آنها هم یکسان باشد . علاوه بر این ، وقوع جداگانه هر یک از این ویژگی ها را می توان به عنوان یک اقدام وزنی از عدم تشابه در نظر گرفت . n00,n11,n01 را به عنوان تعداد غیبت های همزمان ویژگی ها در نظر بگیرد ، که نشان دهنده ویژگی ها هستند ، و وقوع هر کدام از این ویژگی ها برای هر کوئری در ماتریس استفاده از وابستگی نیز به همین ترتیب خواهد بود . به طور مشابهی Sij نیز اندازه گیری می شود که توسط ژو و وونشگ در [20] صورت گرفته است که در آن n11 و n00 نشان دهنده ذره هایی برای تشابه و n10 و n01 نشان دهنده عدم تشابه است.

این اندازه گیری به محاسبه تطبیق بین دو جسم به طور مستقیم می پردازد . جفت های غیر مشابه بر اساس سهم خودشان به شباهت مورد وزن کشی قرار می گیرند . اگر یکی از این تطابق را مشابه با w1 در نظر بگیریم برابر با یک می شود . در خوشه به معنی محدود [24] ضریب را برابر با 2 در نظر می گیریم . گاور [11] w1 را برابر با ½ پیشنهاد می دهند . این گونه می توان جمع بندی کرد که ، انتخاب یک مقدار مناسب برای وزن w1 بستگی به روش و همچنین ساختار و تعریف خود پایگاه داده دارد .
به هر یک از این کوئری ها می توان در زمان های مختلف و از نقاط مختلفی دسترسی داشت . تکرار دسترسی به کوئری در هر سایت در ماتریس دسترسی به کوئری (QA) تعریف شده است . ورودی QAij نشان دهنده تعداد دفعاتی است که در آن کوئری i در سایت j قابل دسترس است . از سوی دیگر هزینه های ارتباطی بین سایت هایی از یک پایگاه داده توزیع شده نقشی کلیدی در عملکرد یک پایگاه داده توزیع شده را ایفا می کند . ماتریس فاصله (DM) یک ماتریس مربعی نا متقارن است که نشان دهنده هزینه های است که باید با استفاده از روش تعریف شده توسط بنتلی و دیتمن [25] به حداقل برسد . ضرب DM در QA یک ماتریس جدید را تولید می کند که در آن هزینه های ارتباطی بین سایت ها و دسترسی به کوئری در هر ککانی به طور همزمان در نظر گرفته می شود و هم آن را تحت تاثیر قرار می دهد و از آنجایی که DM یک ماتریس فاصله به حداقل رسیده است پس ماتریس نتیجه شده ماتریس حداقل دسترسی به کوئری (MQA) است .

هزینه کلی ذخیره سازی (TSC) برای هر ویژگی در هر سایت بستگی به هزینه ذخیره سازی برای هر آیتم و نهایت تعداد سایت دارد.

در جایی که ویژگی هایی که دارای حداقل هزینه ذخیره سازی برای هر سایت هستند به همان سایت تخصیص داده می شوند . معادله 9 نیز بر روی ویژگی های باقی مانده و سایت هایی که دارای حداقل هزینه برای تخصیص به مقدار این ویژگی ها است اعمال می شود.

3 . الگوریتم
الگوریتم 1 با هزینه ارتباطی بین شبکه سایت ها ، ماتریس QA ، ماتریس AU ، و ویژگی هایی که به عنوان ورودی به حساب می آیند کار می کند و درختی از ویژگی های خوشه شده به همراه تخصیص آنها به سایت ها را تولید می کند. این الگوریتم به شکل سلسله مراتبی کار می کند و به تدریج یک درخت خوشه ای ایجاد می کند . در هر بار تکرار آن دو مجموعه از ویژگی ها تولید می شود . مجموعه ای بزرگتر از ویژگی های مشابه که ما آن را به عنوان تکرار خوشه ورودی (IIC) می نامیم به عنوان ورودی برای تکرار بعدی مورد استفاده قرار می گیرد . سایر مجموعه های کوچک را با نام خوشه های برگ می شناسیم (LC) زیرا جداسازی شده است و به عنوان گره های برگ در درخت قرار می گیرند . در مرحله اول DM به وسیله ماتریس بهینه سازی هزینه های ارتباطاتی با استفاده از کار وایتن و همکارانش [25] صورت می پذیرد . سپس MQA به وسیله ضربت QA در ماتریس DM تولید می شود . قدم بعدی مقدار دهی اولیه IIC به وسیله ماتریس AU است . این الگوریتم با تکرار الگوریتم BEA اصلاح شده ادامه پیدا می کند ، که بعدا توضیح داده خواهد شد ، تا زمانی که ویژگی هایی که در IIC شمارش می شود برابر با 3 باشد . از آنجایی که هر تکرار دارای بیشترین شباهت باشد در یک گروه IIC قرار می گیرد ، ما فرض می کنیم پس از این تعداد تکرار ، IIC نتیجه شده شامل بیشترین ویژگی های مشابه از تمامی موارد است به همین دلیل نیازی نیست که از این بیشتر برویم . سپس ، هزینه ذخیره سازی برای هر ویژگی در هر سایت مورد محاسبه قرار می گیرد و در نهایت بر اساس این هزینه ها ، هر خوشه از ویژگی ها به مناسب ترین سایت تخصیص پیدا می کند. آخرین IIC به تمامی سایت ها تخصیص پیدا کرده است.
الگوریتم BEA تغییر داده شده در حقیقت وابستگی اندازه گیری شده را در BEA اصلی تغییر می دهد . همانطور که پیش از این اشاره شد BEA به سادگی با استفاده از وقوع همزمان ویژگی ها ماتریس AFF را ایجاد می کند . در BEA اصلاح شده که در اینجا ارائه شده است ، سایر احتمالات نیز در نظر گرفته می شود . Sij را از کار ژو و ووشج [20] می گیریم تا بتوانیم غیبت های نصفه را نیز در نظر بگیریم ، و n00 ، n01 و n10 را با وابستگی جدیدی که به وسیله Sij اندازه گیری شده است را با استفاده از رابطه زیر مورد محاسبه قرار می دهیم:

وزن w1 وw2 بین 0 و 1 است زیرا n00 ، n01 و n10 دارای اثر مثبت کمتری بر روی شباهت در مقایسه با n11 هستند. علاوه بر این ، اینگونه می توان استنباط کرد که w1 باید بزرگتر از w2 باشد . روش محاسبه مقدار هر کدام از این وزن ها بستگی به ساختار و تعریف جدول و روابط آنها در پایگاه داده ها دارد . اندازه گیری گوور و لجندر[11] و راجرز و تانیموتو [22] دارای برخی از روش ها برای محاسبه مقدار وزن هستند . هر کدام از این وزن ها با در نظر گیری ساختار ها و تعاریف پایگاه داده و کوئری های آن مورد محاسبه قرار می گیرد . ساختار پایگاه داده ها به ما برخی از اطلاعات در مورد روابط بین ویژگی های مختلف را می دهد . بنابراین ، با در نظر گیری کوئری ها ، مقادیر اولیه وزن ها استنباط می شود و پس از تولید نتایج اولیه ، مقادیر وزن ها به مقدار کمی تغییر پیدا می کند به طوری که نتایج نشان دهنده روابط واقعی مورد انتظار بین ویژگی ها با توجه به ساختار پایگاه داده ها است .