16733

16733

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

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

نرم افزار

بهمن 1395

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

كامپيوتر

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

1395/12/03

1/1/1900 12:00:00 AM

Nowadays, interest in searching for keywords to meet the needs of users in the massive amounts of data sources is growing strongly. Thus providing methods an​d algorithms that enable users to easily search efficiently their keywords regardless of complex syntax rules in data graphs is essential. In this case the focus keyword search is on to find subgraph structures including input keywords. Most of the works in keyword search over graphs find minimal connected trees contain all o​r part of the input keywords. Some recent research recommend finding subgraph instead of minimum trees which provide more informative answers. One of the latest researchs with finding r-cliques has improved efficiency an​d quality of previous methods based on subgraph. An r-clique is a set of content nodes that cover all the input keywords an​d the distance between each pair of nodes is less than o​r equal to r. Here we provide methods an​d algorithms by the idea of finding maximal cliques containing keywords based on Bron Kerbosch algorithm to increase performance in sequential an​d parallel processing modes rather than r-clique method. The r-clique method for finding approximate top-k answers tries to minimize the weight of edges between central candidate nodes to the other nodes. Thus, it is possible that the maximum distance between the nodes in obtained cliques are not less than o​r equal to r an​d they at most are 2r an​d in this case cliques on the overall weight increase. We provide a novel an​d efficient approach to achieve top-k approximate answers with a minimum weight of nodes in a row. In addition to maximizing the semantic relationship between keywords successive, approximation quality of the answers will enhance productivity as well because in the answers generated by our proposed method, r is the maximum distance between their nodes. So one of the advantages of the proposed methods is to increase the efficiency an​d quality of especially in sparse graphs an​d also mentioned the possibility of parallel processing. Keywords: Keyword search, Graph data, Maximal clique, Bron Kerbosch, Parallel