13977

13977

روشي براي بهبود زمان پاسخ پردازش پرس و جوهاي گرافي

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

نرم‌افزار

آذر ماه 1393

آذر ماه 1393

دكتر حسن نادري

كامپيوتر

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