Mendeley
TY  _  JOUR
ID  -  A-10-2264-1
TI  -  بهبود کارائی و دقت یافتن یال‌های پرتکرار در خلاصه سازی gMatrix از جریان گراف
JO  -  فصلنامه فناوری اطلاعات و ارتباطات ایران
JA  -  ES
LA  -  fa
SN  -  2717-0411
AU  -  کاظمی مسعود 
AU  -  خواسته سید حسین
AU  -  رخصتی حمیدرضا 
AD  -  دانشجو دانشگاه صنعتی خواجه نصیرالدین طوسی 
AD  -  
AD  -  استادیار دانشگاه صنعتی خواجه نصیرالدین طوسی
Y1  -  2020
PY  -  2020
VL  -  45
IS  -  12
SP  -  95
EP  -  114
KW  -  جریان گراف
KW  -   خلاصه‌‌سازی مبتنی بر طرح
KW  -   gMatrix
KW  -   توابع درهم‌ساز
KW  -   شباهت برداری کُساین
DO  -  
N2  -  در سیستم‌های کاربردی، گراف‌ها با دامنه وسیعی از راس‌ها وجود دارند و یال‌ها به سرعت زیادی در قالب جریان گراف تولید می‌شوند. یکی از مسائل موجود در جریان‌های گراف سنگین که به صورت لحظه‌ای وارد می‌شوند پیدا کردن زیرگراف‌های پرتکرار است. خلاصه‌های جریان مبتنی بر طرح، مانند count-min، اطلاعات گره‌های پرتکرار را با دقت قابل قبولی نگهداری می‌کنند ولی ساختار گراف اصلی را از دست می‌دهند. از بین این روش‌ها،   gMatrix ساختاری می‌باشد که مشخصات گراف اصلی را نیز حفظ می‌کند. این روش از توابع درهم‌ساز مختلف، برای ذخیره‌ی خلاصه‌ی جریان گراف استفاده کرده و به کمک این توابع و معکوس آنها، زیرگراف‌های پرتکرار را به‌دست می‌آورد. به دلیل داشتن حجم کمتر از جریان اصلی، gMatrix معمولا به پرس و جوها با دقت بالایی پاسخ نمی‌دهد. همچنین این روش از مشکل مرتبه‌ی زمانیِ بالا در پاسخ به پرس‌ و جو‌‌ها هم رنج می‌برد. در این مقاله روش جدیدی ارائه شده است که به ازای هزینه‌ی کمِ حافظه‌ی مصرفی، زمان پاسخگویی به پرس و جو زیرگراف پرتکرار را به صورت چشم‌گیری کاهش می‌دهد. همچنین الگوریتم ارایه شده با افزایش استقلال بین توابع در هم سازی با استفاده از روش شباهت برداری کُساین، احتمال برخورد عناصر در هم سازی شده را کاهش می‌دهد. نتایج آزمایشات تجربی که به زبان C++ پیاده‌سازی شده است و بر روی داده‌های شبکه اجتماعی فرندستر اجرا شده است، نشان می‌دهد که روش پیشنهادی برای یافتن زیرگراف‌های پرتکرار پیچیدگی زمانی و دقت یافتن این زیر گراف‌ها را بهبود می‌بخشد. 
UR  - rimag.ir/fa/Article/14720
L1  - rimag.ir/fa/Article/Download/14720
ER  -  
