Journal of Information and Communication Technology
,
Issue45,Year,
Autumn_Winter
2021
در سیستمهای کاربردی، گرافها با دامنه وسیعی از راسها وجود دارند و یالها به سرعت زیادی در قالب جریان گراف تولید میشوند. یکی از مسائل موجود در جریانهای گراف سنگین که به صورت لحظهای وارد میشوند پیدا کردن زیرگرافهای پرتکرار است. خلاصههای جریان مبتنی بر طرح، مانند c More
در سیستمهای کاربردی، گرافها با دامنه وسیعی از راسها وجود دارند و یالها به سرعت زیادی در قالب جریان گراف تولید میشوند. یکی از مسائل موجود در جریانهای گراف سنگین که به صورت لحظهای وارد میشوند پیدا کردن زیرگرافهای پرتکرار است. خلاصههای جریان مبتنی بر طرح، مانند count-min، اطلاعات گرههای پرتکرار را با دقت قابل قبولی نگهداری میکنند ولی ساختار گراف اصلی را از دست میدهند. از بین این روشها، gMatrix ساختاری میباشد که مشخصات گراف اصلی را نیز حفظ میکند. این روش از توابع درهمساز مختلف، برای ذخیرهی خلاصهی جریان گراف استفاده کرده و به کمک این توابع و معکوس آنها، زیرگرافهای پرتکرار را بهدست میآورد. به دلیل داشتن حجم کمتر از جریان اصلی، gMatrix معمولا به پرس و جوها با دقت بالایی پاسخ نمیدهد. همچنین این روش از مشکل مرتبهی زمانیِ بالا در پاسخ به پرس و جوها هم رنج میبرد. در این مقاله روش جدیدی ارائه شده است که به ازای هزینهی کمِ حافظهی مصرفی، زمان پاسخگویی به پرس و جو زیرگراف پرتکرار را به صورت چشمگیری کاهش میدهد. همچنین الگوریتم ارایه شده با افزایش استقلال بین توابع در هم سازی با استفاده از روش شباهت برداری کُساین، احتمال برخورد عناصر در هم سازی شده را کاهش میدهد. نتایج آزمایشات تجربی که به زبان C++ پیادهسازی شده است و بر روی دادههای شبکه اجتماعی فرندستر اجرا شده است، نشان میدهد که روش پیشنهادی برای یافتن زیرگرافهای پرتکرار پیچیدگی زمانی و دقت یافتن این زیر گرافها را بهبود میبخشد.
Manuscript profile
Rimag
Rimag is an integrated platform to accomplish all scientific journal requirements such as submission, evaluation, reviewing, editing, DOI assignment and publishing in the web.