Abstract
Peer-to-Peer (P2P) systems with distinct advantages such as scalability, robustness and low cost have developed quickly in recent years. The resource search problem, that is to find out a peer having a desired resource, is a fundamental problem to be initially solved in most P2P applications. P2P systems can also be categorized under database systems. One of the most important problems of P2P database systems is the query processing algorithms. Even a rather small improvement over these algorithms can have a significant impact on the performance of a P2P database system. One of the most effective methods to reduce query processing cost is peer clustering. Hence, clustering peers with similar contents makes the queries directed to the appropriate cluster and thus to be efficiently answered. In this paper, we present a new peer clustering algorithm for P2P database systems that uses ant-based clustering algorithms. We have adjusted ant-based clustering algorithm to peer clustering problem. Performance evaluation of the algorithm shows its strength in clustering peers in P2P database systems to be of a higher quality and accuracy compared to the existing systems, to have a relatively short running time and to quickly converge to an optimum. Moreover, our algorithm achieves a high scalability to the increasing problem size
چکیده
سیستم های همتا به همتا که دارای مزایای خاصی اعم از مقیاس پذیری، صحت و هزینه ی پایین هستند، در سال های اخیر مورد توسعه و توجه زیادی قرار گفته اند. مسئله ی جستجوی منبع که هدف آن یافتن همتایی است که دارای منبع مد نظر باشد، یک مسئله ی اساسی است که باید در کاربرد های همتا به همتا یا p2p حل شود. سیستم های P2P میتوانند تحت سیستم های پایگاه داده دسته بندی شوند. یکی از مهم ترین مسائل مربوط به این سیستم ها، الگوریتم های پردازش پرس و جو در این سیستم ها میباشد. حتی بهبودی های کمی که بر روی این الگوریتم ها صورت گیرد میتواند تأثیر قابل ملاحظه ای بر روی کارائی این سیستم ها داشته باشد. یکی از کارآمد ترین متد ها برای کاهش هزینه ی پردازش پرس و جو، استفاده از روش خوشه بندی همتا میباشد.. از این رو خوشه بندی همتا ها با محتوایی مشابه باعث شده تا پرس و جو را در یک خوشه ی مناسبی قرار دهیم و از این رو به صورت کارآمد به آن پرس و جو پاسخ دهیم. در این مقاله، یک الگوریتم خوشه بندی همتای جدیدی را برای سیستم های پایگاه داده ی P2P ارائه خواهید داد که از الگوریتم های خوشه بندی مبتنی بر مورچه استفاده خواهد کرد. ما از این الگوریتم برای مسئله ی خوشه بندی همتا استفاده کرده ایم. ارزیابی کارائی این الگوریتم، میزان قوت آنرا در خوشه بندی همتتا ها در سیستم های پایگاه داده ی P2P نشان میدهد که میزان کیفیت و صحت بالایی در مقایسه با سیستم های فعلی دارد. علاوه بر این، الگوریتم ما به یک سطح مقیاس پذیری بالایی با افزایش اندازه ی مسئله ی دست یافته است.
واژگان کلیدی: سیستم های پایگاه داده ی همتا به همتا، پردازش پرس و جو، خوشه بندی، خوشه بندی مورچه ای
1-مقدمه
در سال های اخیر، استفاده از سیستم های همتا به همتا با رشد زیادی همراه بوده است. این سیستم ها، سیستم هایی توزیع شده بوده که شامل گره های بهم متصلی بوده که قادر به سازماندهی خود در توپولوژی های شبکه و با هدف اشتراک منابع هستند. همچنین این گره ها میتوانند خود را با خطا ها وقف داده و در عین حال کارائی و قابلیت اتصال را بدون نیاز به پشتیبانی از یک سرور متمرکز یا یک منبع معتبر حفظ کنند[4]. به منظور اینکه سیستم های مدیریت داده های توزیع شده را بتوان در دنیای همتا به همتا استفاده کرد، باید با مسائل مربوط به شبکه های غیر متمرکز، سیستم های پایگاه داده ی مستقل و عملکرد متقابل معنایی دست و پنجه نرم کند. به منظور طراحی این سیستم ها، مباحثی مانند کشف منبع، آماده سازی پرس و جو ، نگهداری فرا داده ، بروز رسانی انتشار و پردازش پرس و جو باید مد نظر قرار گیرد. پردازش پرس و جو را میتوان مبحثی مهم در این سیستم ها در نظر گرفت که دارای تأثیر زیادی بر روی کارائی سیستم میباشد. یکی از متد های مهم برای کاهش هزینه ی پردازش پرس و جو، خوشه بندی میباشد. بنابراین، با محتوایی مشابه که در یک خوشه قرار داده میشود، پرس و جو ها را میتوان بر روی خوشه های مناسبی مسیر یابی کرد.
تنها پژوهشی که در زمینه ی خوشه بندی همتا ها در سیستم های پایگاه داده ی P2P صورت گرفته است، GrouPeer[21] نام دارد. این پژوهش بر روی مسئله ی همتاهای غنی از نظر اطلاعات متمرکز بوده که ممکن است در آغاز کننده ی پرس و جو مخفی بمانند زیرا فرمول بندی مجدد پرس و جوه ها بر روی هر گره از مسیر گسترش دلیل این مسئله است. این روش رویه ای را پیشنهاد کرده که از گریز نوشتن های مجدد پشت سر هم بر روی هر همتا در مسیر انتشار پرس و جو حمایت میکند. این متد به همتا ها اچازه داده تا سایر همتا ها را با شِماهای مشاب بدست آوردند. زوجیت سازی همتاهای راه دور که پرس و جو ها و پاسخ ها را مبادله میسازند، در مورد شِمای سایر همتا ها و به وسیله ی ایجاد پرس و جو ها و ارزیابی پاسخ ها، اقدام به یادگیری میکنند . در GrouPeer، همتا ها تصمیم میگیرند که یک همسایه ی تک هاپ جدیدی را در خطی با میزان صحت پاسخ هایی که از همتاهای راه دور دریافت میکنند، اضافه کنند. این مورد با استفاده از تابعی اندازه گیری شده که تلاش کرده تشابه های معنایی را بین نسخه های مجدد نوشته شده از یک پرس و جو بدست آورد. به طور خاص، به وسیله ی رویه ی یادگیری، درخواست کننده ها، نگاشت های صحیح و زیادی را با همتا های راه دور، بر مبنای چیزی که آنها تصمیم میگیرند با همتاهایی که اطلاعات را ذخیره میکند انباشته شود، ارائه میدهند. در نتیجه، یک خوشه بندی معنایی از پوشش ایجاد شده که در آن، نوشتن مجدد پرس و جو و پاسخ های آن، میزان صحت بالایی در مقایسه با پوشش های غیر خوشه بندی شده دارد.
در این مقاله، ما یک الگوریتم خوشه بندی بندی را ارائه خواهیم داد که از روش ارائه شده در [17] الهام گرفته است و تطابق هایی را برای اتخاذ این الگوریتم جدید مبتنی بر مورچه، برای مسئله ی خوشه بندی همتا ها ارائه خواهیم داد. با توجه به دانشی که داریم، این الگوریتم اولین الگوریتمی بوده که از الگوریتم مبتنی بر مورچه برای خوشه بندی همتا ها استفاده میکند...