راه كاري جهت جستجوي كلمه كليدي در داده هاي گرافي با استفاده از زيرگراف هاي با قطر r

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

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

189122

دانشگاه علم و صنعت ايران

نرم افزار

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