10729

10729

توسعه الگوريتمهاي كشف مجموعه اقلام مكرر به محيط هاي همتا به همتا بزرگ مقياس با نگرش جرياني بودن داده

دكتري

كامپيوتر - نرم‌افزار

آذر 1391

آذر 1391

دكترمحمدرضا كنگاوري

شبكه هاي همتا به همتا به عنوان سيستمهاي بزرگ مقياس جهت به اشتراك گذاري اطلاعات، به سرعت در حال پديدار شدن مي باشند. مصرف كنند گان با استفاده از شبكه هايي مثل Kazaa [1]، e-Mule [2] و BitTorrents [3] مي توانند به سهولت مقادير زيادي از اطلاعات را به اشتراك بگذارند. مثال هاي ديگر شامل سيستمهاي همتا به همتا براي ذخيره سازي شبكه ، ذخيره كردن وب و جستجو و شاخص گذاري سندهاي مرتبط مي باشد. اين محيط ها از لحاظ داده بسيار غني مي باشند و اگر اين داده مورد كاوش قرار گيرد منجر به توليد يك منبع ارزشمند اطلاعاتي خواهد شد. براي مثال، كاوش ذخيره وب كاربران منجر به توليد اطلاعات درباره الگوهاي جستجو مي شود كه باعث جستجوي كارآمد، استفاده كارآمد از منابع و مسير يابي پرس و جوها مي شود. بيشتر روشهاي آناليز داده در دسترس براي كاربردهاي متمركز طراحي مي شوند به صورتي كه كل داده در يك مكان واحد ذخيره مي شود. اين روش هاي متمركز در يك محيط توزيع شده و نامتمركز از قبيل شبكه هاي همتا به همتا به دليل هزينه بالاي متمركز سازي به خوبي كار نمي كنند. اين هزينه در يك حالت پويا، جايي كه داده موجود در هر گره و همبندي شبكه در تغيير است، افزايش بيشتري پيدا مي كند. زيرا هر تغييري بايد به گره مركزي گزارش داده شود. محيطهاي همتا به همتا براي حل اين مسئله به الگوريتمهاي داده كاوي توزيع شده نيازمند مي باشند كه اساساً مقياس پذير، نامتمركز، غير همزمان و هر زمان باشند. ما در اين رساله به توسعه الگوريتمهاي كشف مجموعه اقلام مكرر به سيستمهاي بزرگ مقياس همتا به همتا پرداخته ايم، جايي كه هر گره روي شبكه جريان پيوسته اي از تراكنش ها را در هر لحظه دريافت مي كند. روش پيشنهادي، روشي محلي است به اين معنا كه هر گره مي تواند فقط با استفاده از اطلاعات يك تعدادي از همسايگان مجاور به كشف مجموعه اقلام مكرر سراسري بپردازد. بنابراين بار ارتباطي مستقل از اندازه سيستم مي باشد كه منجر به مقياس پذيري بالاي روش پيشنهادي مي شود. روش پيشنهادي از دو بخش اصلي تشكيل شده است، در بخش اول به ارائه الگوريتم Max-FISM پرداخته ايم كه الگوريتمي جهت كشف مجموعه اقلام مكرر اخير از داده جرياني با استفاده از مدل پنجره اي مي باشد. اين الگوريتم از لحاظ مصرف حافظه و زمان اجرا، كه از نيازمنديهاي الگوريتمهاي ارائه شده براي داده هاي جرياني مي باشند، در مقايسه با الگوريتمهاي مشابه بسيار كارآمد است.در بخش دوم به ارائه الگوريتم P2P-FISM پرداخته ايم كه با استفاده از خروجي الگوريتم Max-FISM كه در هر گره موجود در شبكه اجرا مي شود به كشف مجموعه اقلام مكرر در سطح شبكه همتا به همتا بزرگ مقياس مي پردازد. روش پيشنهادي، دقيق، مقياس پذير و داراي قابليت هماهنگي با تغييرات موجود در داده هر گره و همبندي شبكه مي باشد. واژه‌هاي كليدي: سيستمهاي همتا به همتا، داده كاوي همتا به همتا، داده جرياني، كاوش مجموعه اقلام مكرر.