کد مقاله : بازدید : 10614 صفحه: -

نوع مقاله: پژوهشی

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

محورهای موضوعی :

مسعود کاظمی ¹ , سید حسین خواسته ² , حمیدرضا رخصتی ³

1 - دانشجو دانشگاه صنعتی خواجه نصیرالدین طوسی
2 - دانشجو
3 - استادیار دانشگاه صنعتی خواجه نصیرالدین طوسی

تاریخ پذیرش : 1399/02/02 تاریخ انتشار : 1399/02/02

کلید واژه:

چکیده مقاله :

در سیستم‌های کاربردی، گراف‌ها با دامنه وسیعی از راس‌ها وجود دارند و یال‌ها به سرعت زیادی در قالب جریان گراف تولید می‌شوند. یکی از مسائل موجود در جریان‌های گراف سنگین که به صورت لحظه‌ای وارد می‌شوند پیدا کردن زیرگراف‌های پرتکرار است. خلاصه‌های جریان مبتنی بر طرح، مانند 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.

منابع و مأخذ:

متن کامل:

دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال دوازدهم، شماره‌هاي 45 و 46، پاییز و زمستان1399

صص: 95-114

$E:\E Drive\logo\iicta Logo0.JPG$

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

مسعود کاظمی* سیدحسین خواسته ** حمیدرضا رخصتی***

*دانشجوی کارشناسی ارشد، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی خواجه نصیرالدین طوسی

**استادیار، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی خواجه نصیرالدین طوسی

***کارشناسی ارشد هوش مصنوعی و رباتیکز، دانشکده مهندسی کامپیوتر، دانشگاه صنعتی خواجه نصیرالدین طوسی

تاریخ دریافت: 05/03/1399 تاریخ پذیرش: 26/09/1399

نوع مقاله: پژوهشی

چکیده

واژگان کلیدی: جریان گراف، خلاصه‌‌سازی مبتنی بر طرح، gMatrix، توابع درهم‌ساز، شباهت برداری کُساین

نویسنده مسئول: سید حسین خواسته khasteh@kntu.ac.ir

1. مقدمه

در علوم کامپیوتر، جریان داده¹ به یک دنباله از داده‌ها که با گذشت زمان در دسترس خواهند بود گفته می‌شود. می‌توان یک جریان را آیتم‌های موجود روی یک تسمه نقاله در نظر گرفت که به صورت تک تک پردازش می‌شوند و نه به صورت جمعی. پردازش جریان‌ها به صورت کاملا متفاوتی از پردازش داده‌ها به صورت دسته‌ای صورت می‌گیرد. از آنجایی که ممکن است جریان‌ها نامحدود باشند، توابع معمولی نمی‌توانند روی جریان‌ها به صورت کلی استفاده شوند. به صورت رسمی جریان‌ها را داده² نمی‌دانند چرا که داده محدود می‌باشد، حال آنکه جریان‌ها بالقوه نامحدود هستند و شبه‌داده³ نامیده می‌شوند. علاوه بر آن معمولا جریان‌ها حجیم هستند. به صورتی که نگهداری و ذخیره تمام اجزای آن امکان‌پذیر نمی‌باشد. حتی در صورت امکان ذخیره این حجم داده، به دلیل پویایی این داده‌ها و تغییر آن در هر ورود داده جدید در گذر زمان، عملا اجرای دوباره و دوباره یک عملیات بر روی کل داده‌هایی که تاکنون دریافت شده است امکان پذیر نمی‌باشد و بسیار کار پرهزینه‌ای می‌باشد. یکی از انواع جریان‌ها، جریان گراف⁴ می‌باشد. جریان گراف در قالب جریانی از رخدادهای صورت گرفته روی یک گراف تعریف می‌شود. در واقع جریان گراف به جای مجموعه‌ای ثابتی از رئوس و یال‌ها و مقادیر آنها، رخداد‌هایی در گذر زمان می‌دهد که اطلاعاتی در مورد راس‌ها و یال‌ها را ارائه می‌دهد. در نتیجه جریان گراف می‌تواند شامل یال‌های یک گراف که به صورت تدریجی وارد می‌شوند باشد. دامنه گسترده‌ای از داده‌ها مانند شبکه‌های حمل و نقل، شبکه‌های آی‌پی⁵ و شبکه‌های اجتماعی به این تقسیم بندی تعلق دارند.

بر روی گراف‌ها پرس و جو⁶های کاربردی مختلفی تعریف شده است که در حوزه‌های مختلف اطلاعاتی از ساختار کلی گراف و همچنین اطلاعات جزيی مربوط به گره یا یال مشخصی را می‌دهند. حال آنکه در جریان گراف به خاطر وجود محدودیت‌هایی که در حفظ و نگهداری جریان گراف و همچنین محدودیت‌هایی که در پردازش تمام ساختار یک گراف سنگین (که به صورت جریان وارد می‌شود) داریم، عملا بسیاری از پرس و جوهای موجود به شکل کنونی خود قابل استفاده نیستند. برای پردازش سریع جریان‌های گراف روش‌های زیادی در انواع مختلف از جمله پنجره لغزان⁷ و طرح گراف⁸ معرفی شده‌اند. روش‌های مبتنی بر طرح یک خلاصه از جریان گراف را نگهداری می‌کنند و به محض ورود یال‌های جدید در گذر زمان آن خلاصه را بروزرسانی می‌کنند. از جمله خلاصه‌های جریان مبتنی بر طرح می‌توان به count‑min اشاره کرد که می‌تواند اطلاعات تکرار گره‌ها با تکرار بالا را با دقت قابل قبولی نگهداری کنند. [1]اما این خلاصه مبتنی بر طرح ساختار گراف اصلی را از دست می‌دهد. مگر اینکه ما اطلاعات راس شروع و پایان هر یال را ذخیره کنیم که این کار بسیار هزینه بر و نشدنی می‌باشد. به عنوان مثال اکثر روش‌های موجود می‌توانند راس‌ها و یال‌های تکرار بالا را تشخیص دهند، اما آنها قادر به جواب پرس و جوهای پیچیده‌تر مانند پیدا کردن مسیرهایی که از یال‌های با تکرار بالا تشکیل شده است نخواهند بود. در طرف دیگر، خلاصه مبتنی برطرح gMatrix که یک طرح سه بعدی می‌باشد، جریان‌های گراف سنگین را در حالی که اطلاعاتی از رفتارهای ساختاری گراف مذکور نگهداری می‌کند، به صورت بلادرنگ خلاصه می‌کند. در نتیجه gMatrix قادر به پاسخگویی پرس‌ و جوهای ساختاری مهم از قبیل دسترسی پذیری از طریق یال‌های پرتکرار نیز خواهد بود. [2]

2. کارهای پیشین

2_1 روش طرح count-min

در الگوریتم count-min با استفاده از یک روش درهم سازی، فرکانس حدودی تعداد زیادی از آیتم‌های مجزا در یک جریان داده محاسبه می‌شوند. در این الگوریتم به تعداد عدد تابع درهم سازی که دو به دو مستقل می‌باشند استفاده می‌شود و هرکدام به یک عدد در بازه به صورت یکنواخت نگاشت می‌شود. که پایه لگاریتم طبیعی است. همچنین داده ساختار مورد نظر از یک آرایه دو بعدی با ابعاد تشکیل شده است. همان‌طور که در شکل 1) مشخص است، هر تابع درهم سازی با یکی از آرایه یک بعدی خانه‌ای مطابقت دارد.

شکل 1. طرح count-min برای جریان داده[1]

در یک جریان داده یک بعدی که عناصر آن دامنه‌های وسیعی دارند وقتی المنت جدیدی وارد می‌شود تمام تابع درهم سازی روی آن اجرا می‌شود تا به یک عدد در بازه نگاشت شوند. سپس مقادیر این خانه یکی اضافه می‌شوند. به جهت محاسبه تعداد یک آیتم، مجموعه خانه مطابق با آن که هر یک را تابع درهم سازی می‌دهند بازیابی شده و مقدار کمینه میان این خانه‌ها پیدا می‌شوند. اگر فرض کنیم تعداد واقعی این آیتم باشد، مقدار تخمین زده شده در کمترین حالت با برابر است. از آنجایی که شمارش غیر منفی مد نظر است و به دلیل امکان وجود تداخل در خانه‌های درهم سازی ممکن است تخمین زیاد انجام پذیرد. همچنین در یک جریان داده با داده ورودی، تخمین برآورده شده برای خانه در بیشترین مقدار با احتمال برابر با خواهد بود. به همین شکل در یک رخداد که آیتم‌ها فرکانس‌های مربوط به خود را دارند، باید تعداد هر آیتم را با فرکانس مربوطه آن افزایش داد. در این حالت را مجموع فرکانس‌های تمام آیتم‌ها تا این لحظه در نظر گرفته می‌شود.

2_2 روش gMatrix

در این مقاله فرض شده است که داده‌های گراف به صورت جریان داده‌ای یالی دریافت می‌شود. هر راس از مجموعه برداشته می‌شود و هر یال یک یال جهت دار است. جریان داده ورودی گراف مورد نظر شامل عضو‌هایی به صورت می‌باشد. اینجا نشان دهنده دریافت یال ‌‌t-ام جریان داده با تکرار می‌باشد. در بسیاری از کاربردها، مقدار به صورت طبیعی برابر یک است، ولی ما یک تکرار عمومی غیر از یک را برای کلیت بخشیدن به نتایج در نظر می‌گیریم. برای مثال در کاربردهای مخابراتی، عدد تکرار می‌تواند نشان دهنده تعداد ثانیه‌هایی باشد که شخص با شخص با شروع در زمان در حال مکالمه بوده است. یک یال می‌تواند چندین بار در یک جریان داده ظاهر شود. زمانی که یک پرس و جو را مطرح می‌کنیم، مثلا پیدا کردن تعداد تکرار یال ، به دنبال جمع تکرارهای یال تا کنون هستیم. درحالی که روش‌های طرح محور می‌توانند با کمی تغییر برای پرس و جوهای زمانی نیز استفاده شوند، آنها را در این قسمت بررسی نمی‌کنیم. همچنین توجه کنید که نتایج ما با فرض بر اینکه یال همیشه به صورت مرتب شده است به سادگی می‌توانند به گراف‌های غیر جهت دار تعمیم داده شوند.

پرس و جوهای تعریف شده در روش gMatrix، تکرار یال (محاسبه تکرار یک یال )، یال‌های پرتکرار (پیدا کردن همه یال‌هایی که تکرار آنها بیشتر از یک حد آستانه داده شده می‌باشد)، مجموع تکرار راس (محاسبه مجموع تکرار تمام یال‌های ورودی و خروجی برای یک راس )، راس‌های پر تکرار (پیدا کردن همه راس‌های که مجموع تکرار آنها (روی همه یال‌های ورودی و خروجی از آنها) از یک حد آستانه داده شده بیشتر می‌باشد.)، مجموع تکرار زیرگراف (محاسبه مجموع تکرار همه‌ی یال‌های یک زیرگراف که روی زیرمجموعه‌ای از راس‌های داده شده می‌باشد) و قابل دستیابی بودن( یافتن اینکه آیا یک راس مبدا⁹ به راس دیگری به عنوان مقصد¹⁰ از طریق یال‌های با تکرار بیشتر از آستانه داده شده قابل دسترسی می‌باشد و یا خیر).

در دو پرس و جوی اول فقط تکرار یال‌ها مطرح می‌باشد که با طرح‌ count-min هم قابل پاسخ گویی می‌باشند. به همین صورت پرس و جوی سوم و چهارم فقط به تکرار راس‌ها نیازمند می‌باشد که مجددا با یک طرح بر روی راس‌ها قابل پاسخ گویی می‌باشد. اما دو پرس و جوی آخر به دنبال یافتن رفتار ساختاری جریان گراف مورد نظر بر مبنای تکرار یال‌های آن می‌باشند. که این پرس و جو‌ها با استفاده از طرح‌های کنونی موجود قابل پاسخ گویی نیستند و باید اطلاعات شروع و پایان همه یال‌ها نیز ذخیره شود که بسیار سنگین می‌باشد. ساختار gMatrix طراحی شده یک ماترسی سه بعدی می‌باشد. به جای ارایه یک راه حل کاملا متفاوت، gMatrix بر پایه اصول ساختار count-min طراحی شده است.

2_3 ساختار gMatrix

gMatrix یک داده ساختار ۳ بعدی از گراف داده می‌باشد که دو بعد آن با راس‌های شروع و پایان مطابقت دارد. هر تابع درهم سازی یک نگاشت از مجموعه رئوس به یک عدد صحیح در بازه تعریف می‌کند. در نتیجه امین تابع درهم سازی با نمایش داده می‌شود و یال را به نگاشت می‌کند. در شکل 2) طرح این روش برای جریان گراف قابل مشاهده است، مانند الگوریتم count-min در اینجا نیز از تابع درهم سازی که دو به دو مستقل می‌باشند استفاده شده است. در نتیجه از تا می‌باشد. جدول درهم سازی در اینجا یک آرایه سه بعدی با خانه می‌باشد. هر خانه با مختصات آدرس دهی می‌شود که در آن و اندیس‌های رئوس نگاشت شده می‌باشند و اندیس تابع درهم سازی استفاده شده در نگاشت می‌باشد. مقدار خانه با مختصات یک عدد صحیح می‌باشد که با نمایش داده می‌شود و در آن فرکانس یال درهم سازی شده برای تابع درهم سازی ام ذخیره می‌شود.

شکل 2. طرح gMatrix برای جریان‌های گراف[2]

2_3_1 به‌روزرسانی خلاصه‌ی gMatrix

برای بروز رسانی gMatrix، کافی است در شروع تمام خانه‌ها را با ۰ مقدار دهی اولیه کنیم و برای هر یال ورودی با فرکانس یال درهم سازی شده متناظر را برای تمام مقادیر از تا محاسبه میکنیم و سپس فرکانس هر یک از این خانه را با مقدار افزایش دهیم. میزان فضای مورد استفاده در gMatrix از مرتبه می‌باشد و همچنین پیچیدگی زمانی برای بروزرسانی یک یال ورودی از جریان برابر با می‌باشد ]4, 3[.

2_3_2 تابع درهم ساز و عکس درهم سازی

به جهت کارا بودن gMatrix، باید توابع درهم ساز دو به دو مستقل باشند. به علاوه، به جهت، پردازش پرس و جو‌های یال‌های پرتکرار و همچنین پرس و جو‌های مبتنی بر ساختار که در قسمت‌های بالا ذکر شده اند، به محاسبه عکس نگاشت تابع درهم ساز نیاز است. اگر فرض کنیم تابع یک تابع در هم ساز می‌باشد، ما معکوس این تابع را با به صورت (1) تعریف می‌کنیم.

(1)

طول عکس نگاشت درهم سازی فقط باشد و از طریق تعمیم الگوریتم اقلیدس به صورت کارآیی با پیچیدگی زمانی محاسبه می‌شود.]5[

2_4 محاسبه پرس و جوی تکرار یال

برای محاسبه تکرار یک یال با استفاده از gMatrix، مقادیر برای مقدار مختلف محاسبه می‌شوند. کمینه این مقادیر به عنوان تخمین تکرار از یال در نظر گرفته می‌شود. این تخمین را با نماد نشان می‌دهیم. پیچیدگی زمانی مورد نیاز برای تخمین تکرار یک یال است که تعداد توابع درهم ساز می‌باشد ]7, 6[.

2_5 محاسبه پرس و جوی یال‌های پرتکرار

یال‌های پرتکرار تمام یال‌های با تکرار بیشتر از یکی آستانه مشخص شده توسط کاربر می‌باشند. از آنجایی که gMatrix یک طرح احتمالی است، نمی‌توان تمام یال‌های پرتکرار را به صورت قطعی پیدا کرد. در نتیجه، یک روش ارائه شده است که هیچ منفی کاذب¹¹‌ای را بازیابی نمی‌کند، اما یک یال ممکن است نمونه مثبت کاذب¹² باشد. متعاقبا احتمال مثبت کاذب بودن یک یال نیز محاسبه می‌شود. این روش دو گام دارد:

1. در گام اول، gMatrix اسکن می‌شود و تمام یال‌های درهم سازی شده که تکرار آنها از حد آستانه بیشتر است برای توابع درهم ساز مختلف پیدا می‌شوند.

2. در گام دوم، برای هر یال پر تکرار تحت تابع درهم ساز ، مجموعه تمام یال‌های گراف اصلی پر تکرار ممکن با استفاده از تکنیک عکس نگاشت درهم سازی پیدا شده که با () نمایش داده‌ می‌شود.

(2)

در نهایت، تصادم¹³ مجموعه یال‌های مختلف برای همه یال‌های پرتکرار را به ما می‌دهد. توجه داشته باشید که گام دوم پرهزینه ترین گام محاسباتی این روش می‌باشد. به همین منظور، تکنیک‌های بهینه سازی برای پرس و جو یال‌های پرتکرار نیز ارائه می‌شوند ]10, 9, 8[.

3. روش پیشنهادی

در این مقاله مشکلات روش gMatrix از دو جهت بهبود یافته است. در رویکرد اول سعی شده است تا زمان اجرای یافتن یال‌های پرتکرار کاهش یابد و در رویکرد دوم به استفاده از توابع درهم‌سازی مستقل سعی شده است تا نرخ مثبت کاذب در یافتن این یال‌ها بهبود یابد.

3_1 بهینه‌سازی زمان اجرا به کمک داده ساختار‌ها

الگوریتم موجود در روش gMatrix برای محاسبه‌ی اشتراک مجموعه‌ها از روش مناسبی استفاده نمی‌کند. برای سریع‌تر کردن مرحله یافتن اشتراک دو مجموعه از داده‌ ساختار درخت قرمز-سیاه استفاده می‌کنیم که با توجه به شناخته بودن این درخت از توضیح نحوه کارکرد آن خودداری می‌کنیم. در این قسمت مراحل استفاده از داده‌ساختار قرمز-سیاه و نحوه بهینه‌سازی پرس و جوی یال‌های پرتکرار به صورت زیر توضیح داده می‌شود. توجه داشته باشید که درخت قرمز-سیاه فقط مقادیر یکتا را نگهداری می‌کند.

1. دو درخت قرمز-سیاه IntersectedQ1 و IntersectedQ2 را تعریف کنید.

2. برای تابع درهم ساز اول، برای هر خانه ازgMatrix که مقدار آن از آستانه بیشتر است مراحل الف و ب را انجام دهید:

1. عکس نگاشت را بدست آورید و همه مقادیر را در IntersectedQ1 قرار دهید.

2. عکس نگاشت را بدست آورید و همه مقادیر را در IntersectedQ2 قرار دهید.

3. برای تابع درهم ساز ۲ تا w مراحل الف تا ث را انجام دهید:

1. دو درخت قرمز-سیاه Q1 و Q2 را تعریف کنید.

2. برای هر خانه ازgMatrix که مقدار آن از آستانه بیشتر است مراحل ۱ و ۲ را انجام دهید:

1. عکس نگاشت p را بدست آور و همه مقادیر را در Q1 قرار دهید.

2. عکس نگاشت q را بدست آور و همه مقادیر را در Q2 قرار دهید.

3. عناصری از IntersectedQ1 که در Q1 نیستند را حذف کنید.

4. عناصری از IntersectedQ2 که در Q2 نیستند را حذف کنید.

4. همه یال‌های ممکن از مجموعه گره‌های IntersectedQ1 به مجموعه گره‌های IntersectedQ2 را می‌سازیم.

5. حذف کردن منفی کاذب‌ها از یال‌های تولید شده و ارائه جواب نهایی

3_2 تحلیل پیچیدگی زمانی

پیچیدگی پیمایش کردن خلاصه gMatrix برابر می‌باشد. فرض می‌کنیم که k-مین تابع درهم ساز از gMatrix که در مجموع تعداد خانه با تعداد تکرار بیشتر یا مساوی آستانه دارد ]11[. آنگاه بر اساس طراحی ما برای مدولار بودن تابع‌های درهم ساز، هرکدام از این خانه‌ها به راس‌های مبدا و راس‌های مقصد مربوط می‌شوند که نیاز به زمان برای یافتن تمامی این مجموعه راس‌ها داریم. نهایتا، همانگونه که بحث شد اشتراک را روی مجموعه راس‌ها می‌گیریم. بنابراین در مجموع پیچیدگی زمانی پرس و جوی یال‌های پرتکرار برابر است با رابطه (3).

با توجه به مراحلی که در بخش قبل توضیح داده شد، برای هر تابع درهم‌ساز شماره ، تعداد خانه بررسی می‌شود که اگر فرض کنیم به تعداد خانه مقدار بیشتر از حد آستانه داشته باشند و از آنجایی که برای هر گره تعداد مقدار عکس نگاشت بدست می‌اید، در نتیجه در بیشترین حالت (همه مقادیر عکس نگاشت‌ها یکتا باشند) به تعداد مقدار در هر درخت قرار می‌گیرد که مرتبه زمانی قرار دادن هر مقدار در درخت خواهد بود. پس برای هر تابع درهم‌ساز مرتبه زمانی کلی می‌باشد.

همچنین برای توابع درهم‌ساز شماره ۲ تا w، علاوه بر این، یک بار روی درخت عکس نگاشت‌های تابع درهم‌ساز اول حرکت می‌کنیم و تمام مقادیر را در درخت تابع درهم‌ساز کنونی جستجو می‌کنیم که در مجموع مرتبه زمانی خواهد بود]12[. در نتیجه به صورت کلی مرتبه زمانی الگوریتم پیشنهادی در رابطه (4) آمده است. همانطور که در رابطه‌های (3) و (4) مشخص است پیچدگی زمانی الگوریتم از ضرب تعداد ضریب به جمع آنها تقلیل یافته است.

(4)

3_3 بهبود دقت پرس و جو به کمک توابع درهم‌ساز مستقل

وجود وابستگی بین توابع درهم‌ساز باعث می‌شود که در پاسخ به پرس و جو‌های مختلف، و در مرحله‌ی ابهام‌زدایی برای یافتن پاسخ پرس و جو، تصادم بسیار زیادی به وجود آید. این مشکل باعث می‌شود که دقت پاسخگویی به پرس و جوها در روش gMatirx کاهش یابد. برای مرتفع کردن این مشکل باید از توابع درهم‌سازی استفاده کرد که وابستگی کمتری به یکدیگر داشته باشند تا بتوانند روی جدول‌های درهم‌سازی مختلف تصادم کمتری ایجاد کنند. برای این منظور از روش بردارهای شباهت یا معیارهای فاصله بین توابع درهم‌ساز استفاده می‌شود. هرچقدر که میزان فاصله‌ی برداری بین توابع درهم‌ساز بیشتر باشد، باعث می‌شود که تصادم کمتری در ابهام‌زدایی توابع درهم‌ساز ایجاد شود ]14, 13[. در این پژوهش از روش‌های بردار فاصله‌ی کُساین، اطلاعات متقابل و فاصله‌ی اقلیدسی استفاده شده است. در بخش بعدی به روش کلی الگوریتم ارائه شده برای یافتن توابع درهم‌ساز مستقل پرداخته می‌شود و نحوه‌ی تبدیل مسئله به یک مسئله‌ در فضای برداری ارائه می‌شود.

3_3_1 شباهت توابع درهم ساز با معیار فاصله

تابع درهم سازی مانند را به صورت زیر تعریف می‌کنیم:

(5)

در رابطه (5) را ورودی تابع درهم سازی و را تابع در هم سازی -ام و را خروجی تابع در هم سازی -ام می‌نامیم. برای ارزیابی دو تابع درهم سازی و در اولین گام، برداری به طول دلخواه از اعداد طبیعی در فاصله‌ی در نظر می‌گیریم و خروجی تابع‌های درهم‌ساز را برای این بردار محاسبه کرده و بردارهای و می‌نامیم. با یافتن فاصله‌ برای دو بردار بدست آمده، میزان شباهت این دو تابع درهم سازی به صورت زیر محاسبه می‌شود:

(6)

در رابطه شماره‌ی (6) تابع محاسبه‌ی فاصله یعنی یکی از سه روش فاصله‌ی اقلیدسی، فاصله‌ی کُساین و یا اطلاعات متقابل است. رابطه‌های ریاضی هر یک از این معیارهای فاصله در بخش قبلی توضیح داده شد. در ادامه به بررسی نحوه‌ی استفاده از هر یک از معیار‌های فاصله‌ی برای محاسبه‌ی شباهت دو تابع درهم‌ساز یعنی مقدار عددی تابع پرداخته می‌شود.

3_3_2 شباهت با فاصله‌ی اقلیدسی

فاصله‌ی اقلیدسی به عنوان ساده‌ترین روش محاسبه‌ی فاصله یا شباهت در مسائل فضاهای برداری در نظر گرفته می‌شود. در این مسئله به سادگی می‌توان میزان شباهت دو تابع درهم‌ساز را به کمک فاصله‌ی دو بردار درهم‌سازی شده به کمک این دو تابع یعنی و به صورت رابطه (7) در نظر گرفت:

(7)

که در این رابطه، K همان طول بردار در نظر گرفته شده است و درایه‌ی k-ام از نمایش برداری خروجی درهم‌سازی شده‌ی درایه‌های بردار ابتدایی به کمک تابع درهم‌سازی i-ام یعنی است ]15[.

3_3_3 شباهت با اطلاعات متقابل

با توجه به تعریف اطلاعات متقابل در بخش قبلی، می‌توان شباهت دو بردار و را از طریق اطلاعات متقابل به دست‌ آورد.

(8)

که در () احتمال رخداد یک به صورت زیر تعریف می‌شود:

(9)

که تعداد رخدادهای مقدار در است. این احتمال به همین ترتیب برای هر ، تعریف می‌شود:

(10)

که در آن تعداد رخدادهای مقدار در است.

احتمال توام نیز به این ترتیب تعریف می‌شود که در این رابطه تعداد رخداد‌هایی به صورت است که عضوی از بردار و عضوی از بردار باشد ]16[.

(11)

3_3_4 شباهت با فاصله‌ی کُساین

با یافتن فاصله‌ی کُساین برای دو بردار بدست آمده، میزان شباهت این دو تابع در هم سازی به صورت زیر محاسبه می‌شود:

(12)

که در رابطه‌ی بالا نماد ضرب داخلی بین دو بردار و است که در بخش فاصله‌ی کٌساین تعریف شد. همچنین هم زاویه‌ی بین این دو بردار است. در نهایت معیار شباهت دو بردار و به کمک فاصله‌ی کساین یعنی به صورت زیر تعریف می‌شود ]18, 17[:

(13)

3_4 روش پیشنهادی برای تعیین توابع درهم‌ساز مستقل

برای صحبت با اطمینان بیشتر در مورد کاهش برخوردهای اتفاقی، می‌توان تعدادی مجموعه از توابع درهم‌ساز تعریف کرد که هر مجموعه شامل تابع درهم‌ساز مجزا است. این مجموعه را می‌نامیم که شامل مجموعه تابع درهم‌ساز است که هر مجموعه شامل تابع درهم‌ساز است. این مجموعه به عنوان ورودی الگوریتم به صورت تصادفی از اعداد اول موجود در رابطه‌های توابع درهم‌ساز تولید می‌شود.

(14)

سپس با استفاده از معیارهای فاصله‌ی تعریف شده، برای هر یک از مجموعه‌های موجود در فاصله‌ی بین دوبه دو‌ی توابع درهم‌ساز موجود در آن را به کمک روش رابطه (3-19) محاسبه کرده و میانگین این فاصله‌ها را به عنوان فاصله‌ی نهایی برای آن مجموعه یا میزان عدم وابستگی توابع درهم‌ساز آن مجموعه در نظر می‌گیریم. پس اگر فرض کنیم که مجموعه‌ی توابع درهم‌سازی کاندید -ام در مجموعه‌ی اصلی M به صورت رابطه (15) باشد:

(15)

معیار عدم وابستگی بین توابع درهم‌ساز موجود در مجموعه‌ی برابر با میانگین شباهت دوبه‌دوی توابع درهم‌ساز است و به صورت رابطه (16) تعریف می‌شود:

(16)

که در (16) تابع همان تابع محاسبه‌ی فاصله‌ی بین دو تابع درهم‌ساز است که در

(7)، () و () تعریف شد. همچنین تعداد توابع درهم‌ساز مجزای موجود در روش gMatrix است. در انتها با استفاده از مجموعه‌ی توابعی که کمترین وابستگی را نسبت به یکدیگر دارند می‌توانیم بهترین مجموعه‌ی توابع درهم‌ساز را برای gMatrix به صورت رابطه (17) انتخاب کنیم:

(17)

با این روش می‌توانیم با اطمینان بیشتری در مورد کاهش برخوردهای اتفاقی در توابع درهم‌سازی در هنگام ساخت gMatrix پیش رویم. در این راستا، الگوریتم ارائه شده برای یافتن توابع درهم‌ساز مستقل از یکدیگر دارای بخش‌های اصلی زیر است:

1. مجموعه‌ی شامل مجموعه‌ی تایی از توابع درهم سازی مجزا بساز

2. برای هر مجموعه از توابع درهم‌سازی ساخته ‌شده مثل که انجام بده:

أ. میزان عدم وابستگی توابع درهم‌ساز عضو را از (166) محاسبه کن.

3. بهترین مجموعه از را به کمک (17) به عنوان انتخاب کن.

4. از مجموعه‌ی توابع درهم‌ساز در ساخت نهایی gMatirx استفاده کن.

4. ارزیابی روش پیشنهادی

کلیه‌ي آزمایش‌هاي انجام شده در این بخش با کمک یک کامپیوتر شخصی با حافظه‌ي اصلی ۸ گیگابایت، پردازنده‌ي 2.7 GHz Intel Core i5، روی سیستم عامل مک، انجام شده‌اند. در این پژوهش الگوریتم‌ها توسط زبان برنامه‌نویسی C++ پیاده‌سازی شده‌اند که توضیح کلی روند پیاده‌سازی را در این قسمت خواهیم داشت. توجه داشته باشید که برای هر مرحله برنامه‌ای جداگانه نوشته شده است که شامل برنامه‌ای برای الحاق فرکانس به مجموعه داده فرندستر، برنامه‌ای برای ساخت خلاصه گراف gMatrix از روی جریان داده، برنامه‌ای برای ساخت پایگاه‌ داده‌ی کلی شامل همه اطلاعات مجموعه داده، سه برنامه برای تست و مقایسه سه پرس و جوی مختلف روی داده واقعی و خلاصه gMatrix، می‌باشند.

4_1 مجموعه‌های داده‌ی مورد آزمایش

در این پژوهش از مجموعه داده شبکه اجتماعی فرندستر¹⁴ که از سایت¹⁵ دانشگاه استنفورد موجود می‌باشد، به دو شکل متفاوت استفاده شده است و در ادامه به جزییات این دو شکل متفاوت داده خواهیم پرداخت. فرندستر یک شبکه بازی آنلاین است. قبل از راه اندازی مجدد به عنوان یک وب سایت بازی، فرندستر یک سایت شبکه اجتماعی بود که در آن کاربران می‌توانستند یال دوستی با هم تشکیل دهند. همچنین شبکه اجتماعی فرندستر به کاربران اجازه می‌داد گروه تشکیل دهند که اعضای دیگر نیز می‌توانستند به آن ملحق شوند. ما چنین گروه‌های تعریف شده توسط کاربر را به عنوان جوامع حقیقی می‌شناسیم. برای شبکه اجتماعی، ما زیرگراف القا شده از گره‌هایی که به حداقل یک اجتماع متعلق هستند یا به گره‌های دیگر که آنها متعلق به حداقل یک جامعه هستند را برمی‌داریم. این داده‌ها توسط پروژه بایگانی وب¹⁶ ارائه شده است، جایی که نمودار کامل موجود است. اطلاعات تکمیلی این مجموعه داده در جدول1) آورده شده است ]21, 20, 19[.

جدول1. اطلاعات و خصوصیات مجموعه داده فرندستر
تعداد گره‌ها	۶۵۶۰۸۳۶۶
تعداد یال‌ها	۱۸۰۶۰۶۷۱۳۵
تعداد گره‌ها در بزرگترین مولفه ضعیفا همبند¹⁷	۶۵۶۰۸۳۶۶
تعداد یال‌ها در بزرگترین مولفه ضعیفا همبند	۱۸۰۶۰۶۷۱۳۵
تعداد گره‌ها در بزرگترین مولفه قویا همبند¹⁸	۶۵۶۰۸۳۶۶
تعداد یال‌ها در بزرگترین مولفه قویا همبند	۱۸۰۶۰۶۷۱۳۵
ضریب خوشه‌بندی¹⁹ میانگین	۰.۱۶۲۳
تعداد مثلث‌ها	۴۱۷۳۷۲۴۱۴۲
کسر مثلث‌های بسته	۰.۰۰۵۸۵۹
قطر (طولانی‌ترین مسیر کوتاه²⁰)	۳۲
قطر موثر ۹۰-درصدی²¹	۵.۸

باید توجه داشت که این مجموعه داده بدون جهت می‌باشد و همچنین فاقد فرکانس برای هر یال می‌باشد. درواقع این مجموعه داده فقط شامل گره شروع و گره پایان هر یال می‌باشد. در نتیجه برای نسبت دادن فرکانس به این مجموعه داده از توزیع زیفان استفاده شده که استفاده از این توزیع در ادبیات جریان داده ]22, 1 [ به یک عمل استاندارد تبدیل شده است. همچنین در تولید فرکانس برای یال‌های مجموعه داده از دو ضریب انحراف²² مختلف و استفاده شده است.

شایان ذکر است که دلیل استفاده از مجموعه داده فرندستر با علم به عدم وجود فرکانس در این مجموعه این بوده است که با الحاق مصنوعی فرکانس به این مجموعه داده ما می‌توانیم نتایج خود را برای ضریب انحراف‌های مختلف تست و بررسی کنیم. از طرف دیگر، همانطور که در گزارش شده است، بیشتر مجموعه داده‌های واقعی ضریب انحراف مشترکی در بازه استفاده شده توسط ما را دارند. ]17, 16[در جدول ) ابعاد مجموعه داده استفاده شده نمایش داده شده است. که حجم جریان²³ نمایانگر حجم جریان گراف با تکرار یال‌ها می‌باشد.

جدول 2. ابعاد و خصوصیات مجموعه داده فرندستر

4_2 افزودن فرکانس به مجموعه داده

در ابتدای امر به جهت آماده‌سازی مجموعه داده فرندستر باید برای هر یال یک فرکانس با استفاده از توزیع زیفان تولید کنیم ]23[. به همین منظور برنامه‌ای نوشته شده است تا گره شروع و گره پایان هر یال را از روی فایل مجموعه داده فرندستر بخواند، سپس با استفاده از رابطه کلی توزیع زیفان که در رابطه (18) آورده شده است فرکانس مربوطه را محاسبه کند و به همراه گره شروع و گره پایان یال در یک فایل مجزا به عنوان خروجی چاپ نماید. اگر را تعداد عناصر در نظر بگیریم و همچنین را مرتبه هر عنصر و مقدار ضریب انحراف باشد، رابطه کلی توزیع زیفان به صورت زیر می‌باشد:

(18)

ما برای هر عنصر مقدار محاسبه شده از توزیع زیفان را در ضرب می‌کنیم و مقدار سقف نتیجه را به عنوان فرکانس آن عنصر در نظر می‌گیریم. بدین صورت از آنجایی که جمع همه مقادیر تولید شده توسط توزیع زیفان برابر با مقدار ۱ خواهند بود، جمع تمام فرکانس‌های عناصر تولید شده توسط ما نیز خواهد بود. توجه داشته باشید که مرتبه عناصر به جهت سادگی، طبق ترتیب ورودی آنها در نظر گرفته شده است. همچنین با توجه به مراحل بالا، دو مجموعه داده مختلف از روی مجموعه داده فرندستر به ازای ضرایب انحراف و ساخته شد.

4_3 انتخاب بهترین بردار شباهت

قبل از انجام عملیات خلاصه‌سازی جریان به کمک روش gMatrix باید یک مجموعه تابع درهم‌ساز مناسب انتخاب گردد ]24[. در این مرحله با انتخاب یک بردار شباهت از روش‌های مطرح‌شده‌ی فاصله‌ی اقلیدسی، شباهت کُساین و اطلاعات متقابل یک روش انتخاب می‌شود و بعد از انجام الگوریتم پیشنهادی مجموعه‌ی توابع درهم‌ساز مناسب مشخص می‌گردد. سپس به کمک این مجموعه مراحل بعدی انجام می‌شود که همان ساخت خلاصه‌ی گراف و پاسخ به پرس و جو‌ها و ارزیابی دقت پاسخ‌گویی است. برای انتخاب از بین سه معیار فاصله‌ی معرفی شده، بعد از انجام چندین اجرا و مقایسه‌ی نتایج، بهترین روش به عنوان معیار معرفی می‌گردد. برای ساخت بردار شباهت در همه‌ی آزمایش‌ها متغیر در نظر گرفته شده است.

4_4 ارزیابی عملکرد روش پیشنهادی

برای ارزیابی یک سیستم خلاصه‌ سازی جریان گراف در مراجع تعدادی پرس و جو تعریف می‌شود. برای ارزیابی عملکرد روش gMatrix، تعداد 6 پرس و جو‌ی مختلف تعریف شده است. [2] از این 6 پرس و جو، دو پرس و جوی یافتن فرکانس یک یال و یافتن یال‌های پرتکرار به عنوان پایه‌ای برای سایر پرس و جوها استفاده شده است. بنابراین علاوه بر پرس و جوی‌ اصلی مورد تاکید در این پژوهش(یافتن زیرگراف‌های پر تکرار) برای ارزیابی عملکرد روش پیشنهادی این دو پرس و جو هم در نظر گرفته شده است.

برای ارزیابی دو آزمایش مستقل در نظر گرفته شده ‌است. همان‌طور که در بخش ساخت داده گفته شد، در این دو آزمایش متغیر ضریب انحراف توزیع زیفان متفاوت است. همچنین سایر متغیرهای ثابت در این دو آزمایش در

جدول) آمده است. به علت اینکه طول جدول درهم‌سازی در gMatrix برابر با h=1000 است، طول بردار سنجش شباهت توابع درهم‌ساز هم برابر با این مقدار قرار می‌گیرد. زیرا خروجی توابع درهم‌ساز در بازه‌ی قرار دارد بنابراین انتخاب می‌تواند باعث پوشش بیشتر فضای مسئله گردد.

جدول3. مقدار متغیرهای مشترک در آزمایش‌ها

حجم جریان

بیشترین فرکانس یال

فرکانس تجمعی جریان

یال‌ها

گره‌ها

۸۰ گیگابایت

۱.۸ میلیارد

۶۶ میلیون

4_4_1_1 پرس و جوی یافتن فرکانس یک یال

برای این پرس و جو یک برنامه نوشته شده است که ابتدا خلاصه gMatrix، عدد اول و توابع درهم‌ ساز را که روی فایل ذخیره شده‌اند می‌خواند و بازسازی می‌کند. سپس ۱۰۰۰۰ یال پرتکرار گراف اصلی را پیدا می‌کند و تعداد ۱۰۰ یال از آنها را به صورت تصادفی انتخاب و فرکانس تخمینی آنها را محاسبه می‌کند. در ادامه با پیدا کردن فرکانس واقعی همین یال‌ها از پایگاه‌ داده ساخته شده، واریانس خطای gMatrix را در برآورد کردن فرکانس این یال‌ها را طبق (19) محاسبه می‌کند. در این رابطه‌ تعداد نمونه‌ها یا برابر تعداد 100 یال، میانگین فرکانس‌ها و فرکانس بدست آمده توسط هر روش است. مقدار خطای این واریانس برای دو آزمایش مطرح‌شده و به کمک هر یک از معیار‌های فاصله‌ی مطرح شده، در

جدول ) آمده است.

(19)

جدول 4. واریانس خطای یافتن فرکانس یک یال

بُرد تابع درهم‌ساز	تعداد توابع‌ درهم‌ساز	تعداد مجموعه توابع درهم‌ساز	طول بردار سنجش شباهت توابع درهم‌ساز	ضریب انحراف توزیع زیفان
					نماد
1000	10	1000	H	1.0	آزمایش 1
1000	10	1000	H	1.4	آزمایش 2

آزمایش 2	آزمایش 1	روش
860	1295	فاصله‌ی اقلیدسی
863	1286	اطلاعات مشترک
860	1287	شباهت کُساین
855	1290	gMatrix

لازم به ذکر است که برای یافتن فرکانس تخمینی هر یال، همه یال‌های درهم ساز مربوطه در هر w تابع درهم ساز را بدست می‌آوریم و بین مقادیر ذخیره شده در این خانه‌ها کوچکترین مقدار را انتخاب می‌کنیم که نزدیک‌ترین مقدار به مقدار واقعی یال در بین آنها می‌باشد. همچنین از آنجایی که در همه روش‌ها یک الگوریتم یکسان استفاده شده است و صرفا خلاصه ساخته شده متفاوت می‌باشد، در نتیجه از لحاظ مرتبه زمانی همه یکسان هستند و نیازی به مقایسه نمی‌باشد ]25[.

4_4_1_2 مقایسه و ارزیابی نتایج

همانطور که در

جدول ) نمایش داده شده است، واریانس خطا در هر آزمایش، فارغ از نحوه انتخاب توابع درهم‌ساز، مقادیر یکسانی دارد. با توجه به اینکه در نحوه ذخیره‌سازی فرکانس یال‌ها در gMatrix و همچنین پرس و جوی آن تغییری ایجاد نشده است، این انتظار را داشتیم که جواب این پرس و جو برای همه روش‌های انتخاب تابع درهم ساز روی یک مجموعه داده یکسان، جوابی مشابه و با دقت یکسانی به دست بدهد.

از نظر ریاضی علت این است که gMatrix برای یافتن فرکانس یک یال، مقدار درون w جدول درهم‌ساز را بررسی می‌کند و از بین آنها کمترین مقدار را به عنوان فرکانس یال درخواست شده در نظر می‌گیرد. با این تعریف انتخاب توابع درهم‌ساز مستقل یا وابسته تغییر در نتایج این پرس و جو نخواهد داشت. در نهایت از بین مقادیر درون w جدول درهم‌ساز در نهایت مقدار یکی از جدول‌ها به عنوان فرکانس یال انتخاب می‌شود. که این مقدار به مقدار خانه‌های جدول‌های دیگر ارتباطی ندارد. به همین علت در این پرس و جو با هر مجموعه‌ی توابع درهم‌ساز ورودی دقت نهایی یافتن فرکانس یک یال تغییر چندانی نخواهد کرد. همچنین از نظر زمان پاسخ‌گویی به این پرس و جو هم به علت عدم تغییر در الگوریتم یافتن خانه‌ی موجود در تابع درهم‌ساز، تغییری بین روش gMatrix و روش پیشنهادی این پژوهش وجود ندارد و زمان پاسخ‌گویی به این پرس و جو در هر دو روش دقیقا به یک اندازه است.

4_4_2_1 پرس و جوی یافتن یال‌های پر تکرار

برای این پرس و جو نیز یک برنامه نوشته شده است که با توجه به فرکانس تجمعی همه یال‌های جریان گراف که می‌باشد، پرس و جو را اجرا می‌کند. برای ارزیابی دقت این پرس‌ و جو از کسر یک ده هزارم از فرکانس تجمعی یعنی می‌باشد، به عنوان در نظر گرفته می‌شود. سپس با این مقدار تمام یال‌های پر تکرار یال‌ها را با استفاده از خلاصه gMatrix محاسبه می‌شود و در نهایت با بررسی فرکانس هر کدام از پایگاه‌ داده‌ی کلی، مقدار نرخ مثبت کاذب در جواب این پرس و جو را به عنوان پارامتر اصلی ارزیابی دقت در نظر گرفته می‌شود. همچنین زمان پاسخ‌گویی به پرس و جوها به همراه حافظه‌ی مصرفی روش پیشنهادی در مقایسه با روش gMatrix به عنوان پارامترهای دیگری برای ارزیابی کارآیی محاسبه‌ می‌شود. اما با توجه به اثبات مرتبه‌ی زمانی برای روش ارائه شده برای ارزیابی کارآیی از نظر مرتبه‌ی زمانی، باید از معیار‌های مختلف برای آستانه‌ی استفاده کرد زیرا مرتبه‌ی زمانی به این معیار وابستگی دارد. برای این پرس و جو دو جدول (5) و (6) در ادامه آمده است که به ترتیب نمایانگر دقت الگوریتم (نرخ مثبت کاذب) و دیگری نمایانگر زمان اجرای هر کدام از روش‌ها می‌باشد که به تفکیک هر روش و آزمایش برای مجموعه داده به نمایش گذاشته شده‌اند.

4_4_2_2 نرخ مثبت کاذب

آزمایش‌هایی برای یافتن یال‌های پرتکرار که تکرار بالاتر از یک آستانه مشخصی داشتند انجام داده ایم. مقدار این آستانه تکرار را با درصدی از تکرار جریان بیان می‌کنیم، زیرا خطای تخمین تکرار یک یال نسبت به جمع تکرار جریان حساس می‌باشد. gMatrix تضمین می‎‌کند که مجموعه یال‌های گزارش شده مجموعه‌ای شامل یال‌های واقعی می‌باشد. نرخ مثبت کاذب را برای پرس و جوهای یال‌های پرتکرار به این صورت بیان می‌شود:

نرخ مثبت کاذب = تعداد یال‌هایی که به اشتباه به عنوان یال‌های پرتکرار گزارش شده‌اند تقسیم بر تعداد درست یال‌های پرتکرار، طبق ():

(20)

گرچه، این نرخ مثبت کاذب کاهش داده شده به قیمت حافظه و زمان اجرای بالاتر به دست آمده است. این پرس و جو را یکبار با استفاده از الگوریتم پیشین یافتن یال‌های پر تکرار و روی gMatrix ساخته شده بدون بهبود توابع درهم‌ساز اجرا و نتایج را یادداشت کردیم. بار دیگر از الگوریتم پیشنهادی بهبود یافته برای یافتن یال‌های پر تکرار و روی gMatrix ساخته شده به همراه بهبود یافته توابع درهم‌ساز استفاده کردیم و مجددا نتایج را یادداشت کردیم. مقایسه این دو آزمایش با روش gMatirx از نظر مقدار نرخ مثبت کاذب (دقت) در

جدول 2) آورده شده است.

جدول 2. نرخ مثبت کاذب در یافتن یال‌های پرتکرار برای هر آزمایش با آستانه‌ی

4_4_2_3 مقایسه و تحلیل نرخ مثبت کاذب

در

جدول 2) که نمایانگر نرخ مثبت کاذب می‌باشد، دیده می‌شود که در هر دو آزمایش (دو مجموعه داده متفاوت) میزان نرخ مثبت کاذب در روش شباهت کساین از روش gMatrix کمتر شده است. بدین ترتیب در آزمایش اول به میزان ۴۱ درصد و در آزمایش دوم به میزان ۷۵ درصد افزایش یافته است. همچنین روش فاصله‌ی اقلیدسی نمی‌تواند بهبود خاصی در نتایج ایجاد کند و حتی نتایج آن از خود gMatrix هم بدتر است. در مورد روش اطلاعات مشترک هم نتایج به دست آمده به رغم داشتن برتری جزئی نسبت به روش gMatirx به این روش بسیار نزدیک هستند. علت این است که روش اطلاعات مشترک برای این مسئله در یافتن احتمال رخداد یک واقعه ضعیف عمل می‌کند. زیرا اطلاعات کافی برای یافتن میزان احتمال یک رخداد مثل را در دست نداریم. در نهایت از بین این سه بردار فاصله بهترین نتایج را روش فاصله‌ی کساین ارائه می‌دهد. دلیل برتری فاصله‌ی کُساین نسبت به سایر روش‌ها این است که این فاصله سعی می‌کند بردارها را از نظر زاویه‌ی بین آنها شباهت‌ سنجی کند و به مقادیر هر یک از ابعاد یک بردار وابسته نیست ]26[.

در این پژوهش، نشان دادیم که استفاده از فاصله‌ی کُساین بر روی توابع درهم سازی برای یافتن میزان شباهت و سازگاری آن‌ها از کارایی بالایی برخوردار می‌باشد، زیرا:

· در توابع درهم سازی مورد استفاده در این مطالعه، بزرگی مقدار عدد خروجی تابع درهم سازی در هنگامی که این اعداد بزرگتر از حد بالایی مانند باشند، از اهمیت یکسانی برخوردار می‌باشند. به طور مثال، و دو خروجی از تابع درهم سازی 1 و 2 می‌باشند. با فرض اینکه و و ، در گام‌های بعدی الگوریتم ارائه شده بر پایه ی توابع درهم سازی، اهمیت و یکسان در نظر گرفته خواهد شد (و نه برابر). حال می‌توان به اصلی ترین ویژگی فاصله ی کُساین اشاره نمود. اهمیت زاویه‌ی ساخته شده در بردارها و نه اندازه ی آن‌ها. از این ویژگی می‌توان به عنوان اثباتی برای کارایی فاصله ی کُساین در مساله‌‎ی ارائه شده یاد کرد.

· پیچیدگی زمانی مناسب فاصله ی کُساین با توجه به محدودیت‌های زمانی تعریف شده در مساله

· ارایه ی نتایج قابل قبول در مقایسه با دیگر روش‌های یافتن فاصله در هنگام کار با بردار‌های تنک.

4_4_3_1 زمان پاسخ به پرس و جو

در

جدول ) برای هر یک از روش‌ها میانگین زمان پاسخ به پرس و جو‌های یافتن یال‌های پرتکرار نمایش داده می‌شود. در جدول قابل مشاهده است زمان پاسخ‌گویی به پرس و جو ارتباطی به معیار فاصله‌ی شباهت استفاده شده در الگوریتم ندارد اما به علت بهینه‌ُسازی استفاده شده به کمک داده ساختار درخت قرمز-سیاه این زمان در روش‌ پیشنهادی پژوهش نسبت به روش gMatrix بسیار کمتر است. این نتایج با توجه به بحث مرتبه‌ی زمانی مطرح شده قابل پیش بینی هستند و محاسبات را تایید می‌کند.

جدول 6. زمان پاسخ به پرس و جوی یال‌های پرتکرار برای هر آزمایش بر حسب ثانیه

آزمایش 2:	آزمایش 1:	آزمایش/ روش
0.009	0.013	فاصله اقلیدسی
0.003	0.011	اطلاعات مشترک
0.001	0.007	شباهت کساین
0.004	0.012	gMatrix

4_4_3_2 مقایسه و تحلیل زمان پاسخ به پرس و جو

روش ‌پیشنهادی همان‌طور که در جداول نتایج مشاهده می‌گردد روش پیشنهادی به کمک داده ساختار درخت قرمز-سیاه زمان پاسخ به پرس و جوها نسبت به روش gMatrix بهبود یافته است. به علت مشابه نبودن شرایط اجرای آزمایش با سیستم اجرای آزمایشات در این پژوهش، همه‌ی آزمایشات مقایسه‌ی مرتبه‌ی زمانی و زمان پاسخ‌گویی به پرس و جوها، برای روش gMatrix هم روی سیستم مشابه این پژوهش انجام شده است. [2]بنابراین زمان اجرای گزارش شده برای روش gMatrix، برای اجرا آن روی محیط شبیه‌سازی مشابه با روش پیشنهادی و با شرایط جریان گراف کاملا مشابه است.

با توجه به اثبات مرتبه‌ی زمانی روش پیشنهادی در بخش ‏0 انتظار می‌رود که این بهبود تقریبا یک حالت لگاریتمی باشد. زیرا مرتبه‌ی زمانی اصلی روش gMatrix برابر است با ضرب ضرایب اما در روش پیشنهادی ما این مرتبه برابر با جمع ضرایب است. بهبود نمایی در زمان پاسخ به پرس و جو یافتن یال‌های پرتکرار از مقایسه‌ی نتایج گرفته شده در

جدول ) قابل مشاهده است.

جدول7. تعداد یال‌های پرتکرار با ضریب انحراف برای مقدار آستانه‌ی مختلف

						مقدار آستانه
						آزمایش/روش
4	1	30	31	391	794	بهینه‌سازی به کمک داده ساختار درخت قرمز-سیاه
28	9	549	612	7071	10562	gMatrix

در

جدول ) مربوط به نتایج زمان اجرای پرس و جو ها، زمان پاسخ به پرس و جو برای مقادیر تعیین شده برای در توزیع زیفان، با بالا رفتن ضریب انحراف، تعداد یال‌ها با فرکانس بالا کمتر می‌شود اما فرکانس خود این یال‌ها بسیار بیشتر خواهد بود. اما با صریب انحراف کمتر، تعداد یال‌های پرتکرار بیشتری خواهیم داشت. تعداد این یال‌ها برای مقدار آستانه‌ی و برای مقدار ضریب انحراف توزیع زیفان در جدول) آمده است.

توجیه اینکه زمان پاسخ به پرس و جو‌ی یافتن یال‌های پرتکرار در هر دو روش برای مقدار آستانه‌ی فرکانس برای مقدار ضریب انحراف از مقدار ضریب انحراف بیشتر است همین امر است. زیرا همان‌طور که شکل ) نشان می‌دهد، وقتی ضریب انحراف بیشتر باشد یال‌های پرتکرار کم ولی وزن‌های خیلی بالا دارند. اما وقتی ضریب انحراف کمتر باشد تعداد یال‌های پرتکرار بیشتر است اما یال‌ها وزن‌های بسیار بالایی ندارند.

شکل 3. احتمال فرکانس یال‌ها برای ضریب انحراف‌های مختلف در توزیع زیفان

به عبارت دیگر وقتی ضریب انحراف کمتر باشد توزیع زیفان میزان وزن یال‌ کلی را در بین تعداد زیادتری از یال‌ها توزیع می‌کند. به همین علت وقتی فرکانس برابر با است، برای ضریب انحراف تعداد یال‌های پرتکرار کمتری داریم. اما وقتی ضریب انحراف باشد تعداد یال‌های پرتکرار برای فرکانس بیشتر است. در نهایت هنگامی میزان فرکانس به فرکانس تجمعی جریان گراف در توزیع زیفان یعنی نزدیک‌تر می‌شود، یعنی و یا ، تعداد یال‌های پرتکرار برای ضریب انحراف کمتر یعنی کمتر می‌شود. اما برای ضریب انحراف بیشتر یعنی به علت بالابودن وزن‌ یال‌های ایجاد شده، تعداد یال‌های پرتکرار در این حالت بیشتر خواهد بود.

5. نتیجه گیری و راهکارهای آتی

هدف از این پژوهش بهبود کارائی یافتن یال‌های پرتکرار در مسئله‌ی جریان گراف بود. برای حل این مسئله یک روش مبتنی بر توابع در هم‌ ساز به نام gMatrix مطرح شده است که دارای مشکلاتی از جمله پیچیدگی زمانی بالا و دقت پایین در پاسخ به پرس و جو‌های مطرح در مسئله‌ی جریان گراف است. با بررسی دقیق مراحل و الگوریتم‌های ارائه شده در روش gMatrix، دلایل این دو مشکل و راه حل‌های آنها به شرح زیر می‌باشد:

1- روش gMatrix برای یافتن یال‌های پرتکرار دارای یک مرحله‌ی ابهام زدایی است که در این مرحله معکوس مقدار توابع درهم ساز برای یک نمایه از هر تابع در نظر گرفته می‌شود و در انتها این معکوس‌ها با یکدیگر اشتراک داده می‌شوند تا یال‌های نهایی پرتکرار بدست آیند. برای بخش اشتراک گیری بین معکوس نمایه‌های توابع در هم ساز، خود روش gMatrix راه‌حلی با مرتبه‌ی زمانی خطی ارائه کرده است. و این مرتبه‌ی زمانی به علت زیاد بودن تعداد نمایه‌های معکوس شده، می‌تواند باعث کندی فرایند پاسخ به پرس و جو‌ها شود.

2- راه حل ارائه شده برای حل این مشکل استفاده از داده‌ساختارها برای کاهش مرتبه‌ی زمانی مرحله‌ی ابهام زدایی در روش gMatrix برای پاسخ به پرس و جو‌های زیر گراف‌های پر تکرار و یال‌های پرتکرار، بود. در این پژوهش از داده ساختار درخت قرمز-سیاه برای یافتن اشتراک بین نمایه‌های معکوس شده با مرتبه‌ی زمانی لگاریتمی استفاده شد.

3- نتایج آزمایش‌های تجربی روی داده‌ها مسئله‌ی جریان گراف بهبود زمان پاسخ به پرس و جوها‌ی مطرح شده را از حالت خطی به حالت لگاریتمی نشان می‌دهد. اما در ازای این کاهش مرتبه‌ی زمانی، به علت استفاد از داده‌ ساختار ها، مرتبه‌ی حافظه‎ی مورد استفاده در روش پشنهادی دو برابر روش gMatrix شده است.

4- مشکل دوم روش gMatrix دقت پایین در پاسخ به پرس و جوی یافتن زیرگراف‌های پر تکرار و یال‌های پرتکرار است. با بررسی دقیق‌تر روش gMatrix دریافت می‌شود که در حین یافتن معکوس نمایه‌های توابع درهم‌سازی هرچه توابع درهم‌ساز مستقل تر از یکدیگر باشند باعث می‌شود که تفاوت الگوی استفاده از تمام خانه‌های جدول درهم‌ساز بیشتر شود و برعکس هرچه توابع وابسته تر باشند احتمال اینکه تابع‌های درهم‌ساز از یک الگوی مشابه برای نگاشت راس‌ها به خانه‌های خود استفاده کنند بیشتر است و این مسئله باعث کاهش دقت روش gMatrix شده است. زیرا این روش برای بهبود روش طرح count-min به جای w جدول درهم سازی یک بعدی، w جدول درهم‌سازی دو بعدی را به طور همزمان استفاده می‌کند.

5- برای حل مشکل توابع درهم ‌ساز وابسته در روش gMatrix از روشی استفاده شد تا بتوان شباهت دو تابع درهم‌ساز را به‌دست آورد. برای این منظور با نگاشت فضای مسئله به یک فضای برداری، برای محاسبه‌ی عدم شباهت دو تابع درهم‌ ساز، از معیارهای فاصله‌ی اقلیدسی، اطلاعات مشترک و شباهت کساین استفاده شد. با استفاده از این معیارهای فاصله می‌توان با در نظرگرفتن خروجی هر یک از توابع درهم ساز در یک فضای برداری میزان وابستگی الگوی آنها را بدست آورد و توابع درهم سازی با وابستگی کمتر را به عنوان ورودی روش gMatrix استفاده کرد.

6- نتایج آزمایش‌های تجربی روی داده‌ی مسئله نشان می‌دهند که استفاده از معیارهای فاصله‌ و شباهت مطرح شده می‌تواند باعث افزایش دقت یا کاهش نرخ مثبت کاذب در پاسخ به پرس و جوهای زیر گراف‌های پر تکرار و یال‌های پرتکرار شود. همچنین نتایج نشان می‌دهد که از بین سه روش مطرح شده برای سنجش وابستگی تابع‌های درهم‌ساز روش شباهت کساین بهترین نتایج را در بر دارد. زیرا ماهیت آن طوری است که به جای توجه به خود مولفه‌ی‌ها بردار مثل روش اطلاعات مشترک و یا توجه به اندازه‌ی بردارها مثل روش فاصله‌ی اقلیدسی، به زاویه‌ی بین دو بردار توجه دارد.

7- از منظر میزان بهبود نتایج بدست آمده، روش پیشنهادی به کمک داده ساختار درخت قرمز-سیاه زمان پاسخ به پرس و جوها نسبت به روش gMatrix بسیار بهبود یافته است، بیش از 10 برابر، البته باید این نکته ذکر شود که پیاده سازی gMatrix توسط خود ما انجام شده است. در مورد نرخ مثبت کاذب نیز، میزان نرخ مثبت کاذب در روش شباهت کساین(بهترین جواب در بین روشهای پیشنهادی) از روش gMatrix کمتر شده است. بدین ترتیب در آزمایش اول به میزان ۴۱ درصد و در آزمایش دوم به میزان ۷۵ درصد بهبود بدست آمده است

5_1 کارهای آتی

برای کارهای آتی و مرتفع کردن مشکلات این پژوهش راه‌حل‌هایی مدنظر است از جمله:

· استفاده از داده‌ساختارهای دیگر که از نظر مرتبه‌ی زمانی مشابه با درخت قرمز-سیاه عمل کنند اما از نظر مرتبه‌ی حافظه‎ی مورد نیاز نسبت به درخت قرمز-سیاه حافظه‌ی کمتری را نیاز داشته باشند. مثلا روش‌های پوشش بیتی²⁴، یا روش‌های مجموعه‌ها مجزا²⁵

· استفاده از معیارهای فاصله‌ یا شباهت بردار دیگری مثل جاکارد²⁶ ، همینگ²⁷ و ...

· استفاده از توابع درهم‌ساز جدول بندی ترکیبی²⁸[27]، زیرا در این جدول‌ها گستردگی پخش نقاط در تابع درهم‌ ساز بیشتر است. اما برای یافتن معکوس چنین توابعی باید چاره‌ای اندیشیده شود.

مراجع

[1] G. Cormode and S. Muthukrishnan, "An Improved Data-Stream Summary: The Count-min Sketch and its Applications", J. of Algorithms, 55(1), 2005.

[2] Khan, Arijit, and Charu Aggarwal. "Query-friendly compression of graph streams", Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. IEEE Press, 2016.

[3] M.R.Henzinger, P.Raghavan, and S.Rajagopalan, "Computing on data streams", External memory algorithms, pages 107–118, 1999.

[4] J.Feigenbaum, S.Kannan, A.McGregor, S.Suri, and J.Zhang, "On graph problems in a semi-streaming model", Theoretical Computer Science, 348(2-3):207–216, 2005.

[5] A. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, M. Strauss, "Fast, small-space algorithms for approximate histogram maintenance", in: Proceedings of the 34th ACM Symposium on Theory of Computing, pp. 389–398, 2002.

[6] B.Bolloba ́s. "Extremal Graph Theory", AcademicPress, New York, 1978.

[7] S.Baswana, "Streaming algorithm for graph spanners single pass and constant processing time per edge", Inf. Process. Lett, 106(3):110–114, 2008.

[8] M. Elkin. "Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners", ACM Transactions on Algorithms, 7(2):20, 2011.

[9] M. Elkin and J. Zhang, "Efficient algorithms for constructing -spanners in the distributed and streaming models", Distributed Computing, 18(5):375–385, 2006.

[10] R.Tarjan, "Data Structures and Network Algorithms", SIAM, Philadelphia, 1983.

[11] A.A.Benczu ́rand D.R.Karger, "Approximating s-t minimum cuts in time", In ACM Symposium on Theory of Computing, pages 47–55, 1996.

[12] D.A.Spielmanand S.-H.Teng, "Spectral sparsificationof graphs", SIAM J. Comput., 40(4):981–1025, 2011.

[13] J.D.Batson, D.A.Spielman, and N.Srivastava, "Twice-ramanujan sparsifiers", SIAM J. Comput., 41(6):1704–1721, 2012.

[14] K.J.Ahnand S.Guha, "Graph sparsificationin the semi-streaming model", In International Colloquium on Automata, Languages and Programming, pages 328–338, 2009.

[15] J.A.Kelnerand A.Levin. "Spectral sparsification in the semi-streaming setting", Theory Comput. Syst., 53(2):243–262, 2013.

[16] N. Manerikar and T. Palpanas, "Frequent Items in Streaming Data: An Experimental Evaluation of the State-of-the-art", Data Knowl. Eng., 68(4):415–430, 2009.

[17] P. Roy, A. Khan, and G. Alonso, "Augmented Sketch: Faster and More Accurate Stream Processing", In SIGMOD, 2016.

[18] L.S.Buriol, G.Frahling, S.Leonardi, A. Marchetti-Spaccamela, and C. Sohler, "Counting triangles in data streams", In ACM Symposium on Principles of Database Systems, pages 253–262, 2006.

[19] A.Pavan, K.Tangwongsan, S.Tirthapura, and K.-L.Wu. "Counting and sampling triangles from a graph stream", In International Conference on Very Large Data Bases, 2013.

[20] K. J. Ahn, S. Guha, and A. McGregor, "Graph sketches: sparsification, spanners, and subgraphs", In ACM Symposium on Principles of Database Systems, pages 5–14, 2012.

[21] H.Jowhari, M.Saglam, and G.Tardos, "Tight bounds for lp samplers, finding duplicates in streams, and related problems", In ACM Symposium on Principles of Database Systems, pages 49–58, 2011.

[22] R.Paghand C.E.Tsourakakis, "Colorful triangle counting and a map-reduce implementation", Inf. Process. Lett., 112(7):277–281, 2012.

[23] L.Becchetti, P.Boldi, C.Castillo, and A.Gionis, "Efficient algorithms for large-scale local triangle counting", TKDD, 4(3), 2010.

[24] H.Jowhari and M.Ghodsi, "New streaming algorithms for counting triangles in graphs", In COCOON, pages 710–716, 2005.

[25] D.M.Kane, K.Mehlhorn, T.Sauerwald, and H.Sun, "Counting arbitrary subgraphs in data streams", In International Colloquium on Automata, Languages and Programming, pages 598–609, 2012.

[26] M.Manjunath, K.Mehlhorn, K.Panagiotou, and H.Sun, "Approximate counting of cycles in streams" In European Symposium on Algorithms, pages 677–688, 2011.

[27] Dahlgaard, Søren, Mathias Knudsen, and Mikkel Thorup, "Practical Hash Functions for Similarity Estimation and Dimensionality Reduction", Advances in Neural Information Processing Systems, 2017.

[1] Data Stream

[2] Data

[3] Codata

[4] Graph Stream

[5] IP

[6] Query

[7] Sliding Window

[8] Graph Sketch

[9] Source

[10] Destination

[11] False Negative

[12] False Positive

[13] Collision

[14] Friendster

[15] Snap.standford.edu

[16] Web Archive Project

[17] Weakly connected component (WCC)

[18] Strongly connected component (SCC)

[19] Clustering

[20] Longest shortest path

[21] 90-percentile

[22] Skew

[23] Stream Size

[24] Bit Mask

[25] Disjoint Set

[26] Jaccard Similarity

[27] Hamming Distance

[28] Mixed Tabulation Hash Functions

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

Abstract

Keywords: Graph Stream, Sketch Based Summarization, gMatrix, Hash Functions, Cosine Similarity

رایمگ

سامانه رایمگ تمامی فرآیندهای دریافت، ارزیابی و داوری، ویراستاری، صفحه‌آرایی و انتشار الکترونیکی نشریات علمی را به انجام می‌رساند

پیوندهای سایت

مراکز مرتبط

پشتیبانی

صفحات رسمی

						مقدار آستانه
						ضریب انحراف توزیع زیفان
11	4	61	45	4375	86316	تعداد یال‌های پرتکرار

اشتراک گذاری

آدرس مقاله

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

رایمگ

پیوندهای سایت

مراکز مرتبط

پشتیبانی

صفحات رسمی