Brief Announcement: Graph Matching in Massive Datasets
Brief Announcement: Graph Matching in Massive Datasets
复制标题
简短公告：海量数据集中的图匹配
DOI：
10.1145/3087556.3087601
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Hadi Yami
中科院分区：
文献类型：
--
作者：
Soheil Behnezhad;Mahsa Derakhshan;Hossein Esfandiari;E. Tan;Hadi Yami
在本文中，我们考虑了大两部分图中的最大匹配问题。我们提出了一种新算法，该算法在新的边缘采样技术的一些迭代中找到了最大匹配。该算法可以在大数据设置（例如流式设置和MAPREDUCE设置）中实现，其中每个算法映射的每次迭代均分别通过流，或一个MapReduce Compul of Computation。我们证明，我们的算法为1/\ EPS回合中的最大匹配提供了1- \ eps的近似解决方案，从而改善了先前的工作，从而改善了通过/回合的数量。当我们在实际数据集上运行它时，我们的算法甚至可以更好地效果，并且在4到8发中找到了确切的最大匹配，同时仅采样总边缘的百分比1％。
In this paper we consider the maximum matching problem in large bipartite graphs. We present a new algorithm that finds the maximum matching in a few iterations of a novel edge sampling technique. This algorithm can be implemented in big data settings such as streaming setting and MapReduce setting, where each iteration of the algorithm maps to one pass over the stream, or one MapReduce round of computation, respectively. We prove that our algorithm provides a 1-\eps approximate solution to the maximum matching in 1/\eps rounds which improves the prior work in terms of the number of passes/rounds. Our algorithm works even better when we run it on real datasets and finds the exact maximum matching in 4 to 8 rounds while sampling only about %1 of the total edges.
参数化流：最大匹配和顶点覆盖
DOI：
10.1137/1.9781611973730.82
发表时间：
2015
期刊：
影响因子：
--
作者：
Rajesh Hemant Chitnis;Graham Cormode;Mohammad Taghi Hajiaghayi;Morteza Monemizadeh
通讯作者：
Morteza Monemizadeh
用于估计平面图及其他区域中的匹配大小的流算法
DOI：
10.1145/3230819
发表时间：
2015
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Hossein Esfandiari;Mohammad Taghi Hajiaghayi;Vahid Liaghat;Morteza Monemizadeh;Krzysztof Onak
通讯作者：
Krzysztof Onak
DOI：
10.1145/2755573.2755618
发表时间：
2015
期刊：
Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Rajesh Hemant Chitnis;Graham Cormode;Hossein Esfandiari;MohammadTaghi Hajiaghayi;Morteza Monemizadeh
通讯作者：
Morteza Monemizadeh