10862

10862

تشخيص تغيير در گراف هاي جرياني بزرگ با تعيين مكان بروز تغييرات

كارشناسي ارشد

كامپيوتر - هوش مصنوعي

شهريور 1391

شهريور 1391

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

امروزه داده¬ها سريعتر از زمان پردازش و كاوش آنها در اختيار ما قرار مي¬گيرند. براي اينكه اين داده¬ها را از دست ندهيم بايد از تكنيك¬هاي سنتي داده كاوي به سيستم¬هايي روي آوريم كه قادر به پردازش داده¬هاي پيوسته، داراي حجم بالا و نامحدود باشد. نمونه¬اي از اين نوع سيستم¬ها جريان¬هاي گراف مي¬باشند. مي¬دانيم كه مي¬توان بسياري از داده¬هاي حال حاضر را به صورت گراف نشان دهيم، از جمله اين داده¬ها مي¬توان به ساختار شبكه اينترنت، كاربران شبكه¬هاي اجتماعي، شبكه ارتباطات نامه¬هاي الكترونيكي و ... اشاره كرد. اكثر روش¬هايي كه تاكنون در اين زمينه ارائه شده است قادرند كه فقط روي داده¬هاي استاتيك كار كنند يعني فرض مي¬كنند كه ساختار گراف به گونه¬اي است كه مي¬توان كل آنرا درون حافظه و به راحتي نگه داشت و در مقابل داده¬هايي كه در طول زمان وارد مي¬شوند و يا اندازه گراف آنها بسيار بزرگ هستند دچار مشكل مي¬شوند يا عملكرد ضعيفي دارند. در اين پروژه يك ايده جديد براي پردازش گراف¬هاي جرياني بزرگ ارائه شده است كه در آن علاوه بر تشخيص بهينه مكان تغييرات در گراف¬هاي جرياني بزرگ بدون نياز به ذخيره كل گراف روي حافظه، محليت تغييرات نيز تعيين مي¬شود. همچنين يك ساختمان داده جديد به نام ToLaMiS معرفي شده است كه با كارايي بسيار بالايي از آن مي¬توان براي تشخيص عناصر پر تكرار در جرياني از داده¬ها استفاده كرد. با توجه به دانش ما اين اولين روشي است كه از اين ساختمان داده براي تشخيص تغييرات در گراف استفاده مي¬كند و همچنين اولين روشي است كه مي¬تواند به خوبي مكان تغييرات را نيز دنبال كند. واژه‌هاي كليدي: جريان¬هاي گراف، كاوش گراف، ساختمان داده نقشه، تشخيص تغيير، يافتن الگوهاي پر تكرار