Mengdi Yu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Mengdi Yu has a total of 4 co-authors. Here are the top co-authors by number of shared publications:
- Chao Song
University of Electronic Science and Technology of China
1 shared publication - Jiqing Gu
Chengdu University of Information Technology, Chengdu, China
1 shared publication - Ming Liu
University of Electronic Science and Technology of China
1 shared publication - Xu Yang
Xi’an Jiaotong University
1 shared publication
Latest Publications
- Open Access
- 8 January 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 16 (4) , 1-43
Distributed Triangle Approximately Counting Algorithms in Simple Graph Stream
Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, the problem of counting global and local triangles in a graph stream has been widely studied, and numerous triangle counting steaming algorithms have emerged. To improve the throughput and scalability of streaming algorithms, many researches of distributed streaming algorithms on multiple machines are studied. In this article, we first propose a framework of distributed streaming algorithm based on the Master-Worker-Aggregator architecture. The two core parts of this framework are an edge distribution strategy, which plays a key role to affect the performance, including the communication overhead and workload balance, and aggregation method, which is critical to obtain the unbiased estimations of the global and local triangle counts in a graph stream. Then, we extend the state-of-the-art centralized algorithm TRIÈST into four distributed algorithms under our framework. Compared to their competitors, experimental results show that DVHT-i is excellent in accuracy and speed, performing better than the best existing distributed streaming algorithm. DEHT-b is the fastest algorithm and has the least communication overhead. What’s more, it almost achieves absolute workload balance.
- 8 January 2022
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 16 (4) , 1-43
Open AccessDistributed Triangle Approximately Counting Algorithms in Simple Graph Stream
Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, the problem of counting global and local triangles in a graph stream has been widely studied, and numerous triangle counting steaming algorithms have emerged. To improve the throughput and scalability of streaming algorithms, many researches of distributed streaming algorithms on multiple machines are studied. In this article, we first propose a framework of distributed streaming algorithm based on the Master-Worker-Aggregator architecture. The two core parts of this framework are an edge distribution strategy, which plays a key role to affect the performance, including the communication overhead and workload balance, and aggregation method, which is critical to obtain the unbiased estimations of the global and local triangle counts in a graph stream. Then, we extend the state-of-the-art centralized algorithm TRIÈST into four distributed algorithms under our framework. Compared to their competitors, experimental results show that DVHT-i is excellent in accuracy and speed, performing better than the best existing distributed streaming algorithm. DEHT-b is the fastest algorithm and has the least communication overhead. What’s more, it almost achieves absolute workload balance.