بهبود كارائي و دقت يافتن يال‌هاي پرتكرار در خلاصه سازي gMatrix از جريان گراف

Improving Efficiency of Finding Frequent Subgraphs in Graph Stream Using gMatrix Summarization

در سيستم‌هاي كاربردي، گراف‌ها با دامنه وسيعي از راس‌ها وجود دارند و يال‌ها به سرعت زيادي در قالب جريان گراف توليد مي‌شوند. يكي از مسائل موجود در جريان‌هاي گراف سنگين كه به صورت لحظه‌اي وارد مي‌شوند پيدا كردن زيرگراف‌هاي پرتكرار است. خلاصه‌هاي جريان مبتني بر طرح، مانند count-min، اطلاعات گره‌هاي پرتكرار را با دقت قابل قبولي نگهداري مي‌كنند ولي ساختار گراف اصلي را از دست مي‌دهند. از بين اين روش‌ها، gMatrix ساختاري مي‌باشد كه مشخصات گراف اصلي را نيز حفظ مي‌كند. اين روش از توابع درهم‌ساز مختلف، براي ذخيره‌ي خلاصه‌ي جريان گراف استفاده كرده و به كمك اين توابع و معكوس آنها، زيرگراف‌هاي پرتكرار را به‌دست مي‌آورد. به دليل داشتن حجم كمتر از جريان اصلي، gMatrix معمولا به پرس و جوها با دقت بالايي پاسخ نمي‌دهد. همچنين اين روش از مشكل مرتبه‌ي زمانيِ بالا در پاسخ به پرس‌ و جو‌‌ها هم رنج مي‌برد. در اين مقاله روش جديدي ارائه شده است كه به ازاي هزينه‌ي كمِ حافظه‌ي مصرفي، زمان پاسخگويي به پرس و جو زيرگراف پرتكرار را به صورت چشم‌گيري كاهش مي‌دهد. همچنين الگوريتم ارايه شده با افزايش استقلال بين توابع در هم سازي با استفاده از روش شباهت برداري كُساين، احتمال برخورد عناصر در هم سازي شده را كاهش مي‌دهد. نتايج آزمايشات تجربي كه به زبان C++ پياده‌سازي شده است و بر روي داده‌هاي شبكه اجتماعي فرندستر اجرا شده است، نشان مي‌دهد كه روش پيشنهادي براي يافتن زيرگراف‌هاي پرتكرار پيچيدگي زماني و دقت يافتن اين زير گراف‌ها را بهبود مي‌بخشد.

In many real-world frameworks, dealing with huge domains of nodes and online streaming edges are unavoidable. Transportation systems, IP networks and developed social medias are quintessential examples of such scenarios. One of the most important open problems while dealing with massive graph streams are finding frequent sub-graph. There are some approaches such as count-min for storing the frequent nodes, however performing these methods will result in inaccurate modelling of structures based on the main graph. Having said that, gMatrix is one of the recently developed approaches which can fairly save the important properties of the main graph. In this approach, different hash functions are utilized to store the basis of streams in the main graph. As a result, having the reverse of the hash functions will be extremely useful in calculation of the frequent subgraph. Though gMatrix mainly suffer from two problems. First, they are not really accurate due to high compression rate of the main graph and second, the complexity of returning a query is high. In this thesis, we have presented a new approach based on gMatrix which can reduce the amount of memory usage as well as returning the queries in less amount of time. The main contribution of the introduced approach is to reduce the dependency among the hash functions. This will result in less conflicts while creating the gMatrix later. In this study we have used Cosine Similarity in order to estimate the amount of dependency and similarity among hash functions. Our experimental results prove the higher performance in terms of algorithm and time complexity.