بهبود کارائی و دقت یافتن یال‌های پرتکرار در خلاصه سازی gMatrix از جریان گراف
الموضوعات :
مسعود کاظمی
1
,
سید حسین خواسته
2
,
حمیدرضا رخصتی
3
1 - دانشجو دانشگاه صنعتی خواجه نصیرالدین طوسی
2 - دانشجو
3 - استادیار دانشگاه صنعتی خواجه نصیرالدین طوسی
الکلمات المفتاحية: جریان گراف, خلاصه‌‌سازی مبتنی بر طرح, gMatrix, توابع درهم‌ساز, شباهت برداری کُساین,
ملخص المقالة :
در سیستم‌های کاربردی، گراف‌ها با دامنه وسیعی از راس‌ها وجود دارند و یال‌ها به سرعت زیادی در قالب جریان گراف تولید می‌شوند. یکی از مسائل موجود در جریان‌های گراف سنگین که به صورت لحظه‌ای وارد می‌شوند پیدا کردن زیرگراف‌های پرتکرار است. خلاصه‌های جریان مبتنی بر طرح، مانند count-min، اطلاعات گره‌های پرتکرار را با دقت قابل قبولی نگهداری می‌کنند ولی ساختار گراف اصلی را از دست می‌دهند. از بین این روش‌ها، gMatrix ساختاری می‌باشد که مشخصات گراف اصلی را نیز حفظ می‌کند. این روش از توابع درهم‌ساز مختلف، برای ذخیره‌ی خلاصه‌ی جریان گراف استفاده کرده و به کمک این توابع و معکوس آنها، زیرگراف‌های پرتکرار را به‌دست می‌آورد. به دلیل داشتن حجم کمتر از جریان اصلی، gMatrix معمولا به پرس و جوها با دقت بالایی پاسخ نمی‌دهد. همچنین این روش از مشکل مرتبه‌ی زمانیِ بالا در پاسخ به پرس و جوها هم رنج می‌برد. در این مقاله روش جدیدی ارائه شده است که به ازای هزینه‌ی کمِ حافظه‌ی مصرفی، زمان پاسخگویی به پرس و جو زیرگراف پرتکرار را به صورت چشم‌گیری کاهش می‌دهد. همچنین الگوریتم ارایه شده با افزایش استقلال بین توابع در هم سازی با استفاده از روش شباهت برداری کُساین، احتمال برخورد عناصر در هم سازی شده را کاهش می‌دهد. نتایج آزمایشات تجربی که به زبان C++ پیاده‌سازی شده است و بر روی داده‌های شبکه اجتماعی فرندستر اجرا شده است، نشان می‌دهد که روش پیشنهادی برای یافتن زیرگراف‌های پرتکرار پیچیدگی زمانی و دقت یافتن این زیر گراف‌ها را بهبود می‌بخشد.
[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 (1 +ϵ,β)-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 O(n2) 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.
