東華大學圖書館 |

Triangle Counting on Large Graphs.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Triangle Counting on Large Graphs./
作者:	Hu, Yang.
面頁冊數:	1 online resource (124 pages)
附註:	Source: Dissertations Abstracts International, Volume: 84-06, Section: B.
Contained By:	Dissertations Abstracts International84-06B.
標題:	Computer engineering. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30240908click for full text (PQDT)
ISBN:	9798358484535

Triangle Counting on Large Graphs.
Hu, Yang.

Triangle Counting on Large Graphs. - 1 online resource (124 pages)

Source: Dissertations Abstracts International, Volume: 84-06, Section: B.

Thesis (Ph.D.)--The George Washington University, 2023.

Includes bibliographical references

Triangle counting is a fundamental graph algorithm. It is also used in a wide range of applications such as thematic structures, link recommendation, social network analysis, spam detection, and e-commerce. In addition, it is used as a building block in other graph related problems, such as graph isomorphism (subgraph matching), k-truss, and clustering coefficient. Various triangle counting algorithms are studied for decades. However, the conventional algorithms are designed for sequential execution and have difficulties to scale to high volume of parallelism device such as GPUs or distributed systems. Since the worst case time complexity of this algorithm is high, it takes a long time to execute for big graphs. Also, as graph size increases, external execution takes a large amount of disk I/O operations which as a result is slow. Existing solutions face several drawbacks of suboptimal I/O complexity, limited parallelism, and low scalability.My dissertation research strives to provide high performance solutions of fast triangle counting on big graphs. We identify the most emerging needs for fast triangle counting on large graphs which are two folds. First, scalable parallel triangle counting algorithm designed for GPUs and distributed systems is a key for fast processing on large graphs. Second, external memory algorithm to minimize disk I/Os for the graphs larger than memory size is also important for many large datasets. As a consequence, my dissertation research aims to solve the challenges described above.My first project TriCore is a new GPU based high-performance and scalable triangle counting system that consists of three main techniques. First, we designed a binary search based counting algorithm that tremendously increases both thread parallelism and memory performance. Second, TriCore exploits a 2-D partition method to distribute the CSR representation across multiple GPUs, combined with a new streaming buffer to load the edge list from outside of GPUs. Third, we developed a dynamic workload management technique to balance the workload across multiple GPUs. Our evaluation demonstrates TriCore is 22 times faster than the state-of-the-art parallel triangle counting projects. In addition, TriCore can not only process big graphs that are significant larger than the memory size of one GPU but also achieve 24 times speedup when scaling to 32 GPUs.My second project, TriP, is a set of graph partitioning algorithms for external-memory based triangle counting. Exploring 1-D vertical and 2-D partitioning approaches, we have designed novel, practical algorithms to deliver high parallelism and optimal I/O complexity while satisfying the memory bound. Our experiments shows that TriP is able to achieve 15.8 times speedup over the state-of-the-art sequential implementation, and 6.7 times over state-of-the-art parallel implementation, benefited from 1.3 times lower I/O scaling rate and over 6 times average improvement in computation time.My third project TriX is a scalable triangle counting framework, which is comprised of a 2-D graph partition strategy and a binary search based intersection algorithm designed for GPUs. The DARPA Graph Challenge seeks a scalable solution for triangle counting on big graphs. The 2-D partition provides balanced work division among multiple GPUs. On the other hand, binary search based intersection achieves fine-grained parallelism on GPUs via intra-warp scheduling and coalesced memory access. TriX is able to scale to a large number of GPUs, and count triangles on billion-node graph (2 billion node, 64 billion edges) within 35 minutes, achieving over 16 million traverse edges per second (TEPS).In conclusion, my research has focused on triangle counting algorithms on large graphs. I design a GPU-based triangle counting algorithm for efficient parallel computation, an external memory algorithm to enable large graphs to be processed with good I/O complexity, and combine these two algorithms to develop a highly scalable and distributed solution. My future work will focus on related graph algorithms and hardware-software co-design to develop high performance solutions in Artificial Intelligence fields.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2023

Mode of access: World Wide Web

ISBN: 9798358484535Subjects--Topical Terms:

621879
Computer engineering.
Subjects--Index Terms:

Triangle countingIndex Terms--Genre/Form:

542853
Electronic books.

Triangle Counting on Large Graphs.
LDR:05430nmm a2200349K 4500 001 2354357
005 20230403071228.5
006 m o d
007 cr mn ---uuuuu
008 241011s2023 xx obm 000 0 eng d
020 $a 9798358484535
035 $a (MiAaPQ)AAI30240908
035 $a AAI30240908
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Hu, Yang. $3 2203917
245 1 0 $a Triangle Counting on Large Graphs.
264 0 $c 2023
300 $a 1 online resource (124 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 84-06, Section: B.
500 $a Advisor: Huang, Howie.
502 $a Thesis (Ph.D.)--The George Washington University, 2023.
504 $a Includes bibliographical references
520 $a Triangle counting is a fundamental graph algorithm. It is also used in a wide range of applications such as thematic structures, link recommendation, social network analysis, spam detection, and e-commerce. In addition, it is used as a building block in other graph related problems, such as graph isomorphism (subgraph matching), k-truss, and clustering coefficient. Various triangle counting algorithms are studied for decades. However, the conventional algorithms are designed for sequential execution and have difficulties to scale to high volume of parallelism device such as GPUs or distributed systems. Since the worst case time complexity of this algorithm is high, it takes a long time to execute for big graphs. Also, as graph size increases, external execution takes a large amount of disk I/O operations which as a result is slow. Existing solutions face several drawbacks of suboptimal I/O complexity, limited parallelism, and low scalability.My dissertation research strives to provide high performance solutions of fast triangle counting on big graphs. We identify the most emerging needs for fast triangle counting on large graphs which are two folds. First, scalable parallel triangle counting algorithm designed for GPUs and distributed systems is a key for fast processing on large graphs. Second, external memory algorithm to minimize disk I/Os for the graphs larger than memory size is also important for many large datasets. As a consequence, my dissertation research aims to solve the challenges described above.My first project TriCore is a new GPU based high-performance and scalable triangle counting system that consists of three main techniques. First, we designed a binary search based counting algorithm that tremendously increases both thread parallelism and memory performance. Second, TriCore exploits a 2-D partition method to distribute the CSR representation across multiple GPUs, combined with a new streaming buffer to load the edge list from outside of GPUs. Third, we developed a dynamic workload management technique to balance the workload across multiple GPUs. Our evaluation demonstrates TriCore is 22 times faster than the state-of-the-art parallel triangle counting projects. In addition, TriCore can not only process big graphs that are significant larger than the memory size of one GPU but also achieve 24 times speedup when scaling to 32 GPUs.My second project, TriP, is a set of graph partitioning algorithms for external-memory based triangle counting. Exploring 1-D vertical and 2-D partitioning approaches, we have designed novel, practical algorithms to deliver high parallelism and optimal I/O complexity while satisfying the memory bound. Our experiments shows that TriP is able to achieve 15.8 times speedup over the state-of-the-art sequential implementation, and 6.7 times over state-of-the-art parallel implementation, benefited from 1.3 times lower I/O scaling rate and over 6 times average improvement in computation time.My third project TriX is a scalable triangle counting framework, which is comprised of a 2-D graph partition strategy and a binary search based intersection algorithm designed for GPUs. The DARPA Graph Challenge seeks a scalable solution for triangle counting on big graphs. The 2-D partition provides balanced work division among multiple GPUs. On the other hand, binary search based intersection achieves fine-grained parallelism on GPUs via intra-warp scheduling and coalesced memory access. TriX is able to scale to a large number of GPUs, and count triangles on billion-node graph (2 billion node, 64 billion edges) within 35 minutes, achieving over 16 million traverse edges per second (TEPS).In conclusion, my research has focused on triangle counting algorithms on large graphs. I design a GPU-based triangle counting algorithm for efficient parallel computation, an external memory algorithm to enable large graphs to be processed with good I/O complexity, and combine these two algorithms to develop a highly scalable and distributed solution. My future work will focus on related graph algorithms and hardware-software co-design to develop high performance solutions in Artificial Intelligence fields.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2023
538 $a Mode of access: World Wide Web
650 4 $a Computer engineering. $3 621879
653 $a Triangle counting
653 $a Graph algorithm
653 $a Subgraph matching
655 7 $a Electronic books. $2 lcsh $3 542853
690 $a 0464
710 2 $a ProQuest Information and Learning Co. $3 783688
710 2 $a The George Washington University. $b Computer Engineering. $3 1678827
773 0 $t Dissertations Abstracts International $g 84-06B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30240908 $z click for full text (PQDT)