Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


thesis.pdf (375.2 KB)

ETD Abstract Container

Abstract Header

STREAMING HYPERGRAPH PARTITION FOR MASSIVE GRAPHS

Wang, Guan
http://rave.ohiolink.edu/etdc/view?acc_num=kent1385097649

Abstract Details

2013, MS, Kent State University, College of Arts and Sciences / Department of Computer Science.
In this thesis, a new streaming graph partition problem is studied: the hypergraph partition problem for massive graphs, where the goal is to partition the vertices so that the neighbors of each vertex span a minimal number of clusters. This problem arises in a list of real world applications including communication cost and I/O cost minimization in large scale graph processing and robustness maximization in massive social graph management. However, the existing hypergraph partition approaches can only work on small to moderate size graphs and to handle large graphs, only the random partition is available. In this study, novel approaches are introduced to perform streaming hypergraph partition for massive graphs, i.e., only one pass of the massive graph is needed to produce desired partition. Specifically, a novel unequal probability sampling approach for hypergraph-to-graph transformation is developped along with two techniques online sparsification and online compression for handling the streaming edge graph (produced from hypergraph-to-graph transformation). A detailed experimental evaluation demonstrates that this approach can provide fast streaming partition on massive graphs with tens of millions of vertices and edges.
Ruoming Jin, Dr. (Advisor)
Feodor Dragan, Dr. (Committee Chair)
Ye Zhao, Dr. (Committee Member)
41 p.
Computer Science
graph partition; hypergraph; sampling; sparsification

Recommended Citations

Citations

  • Wang, G. (2013). STREAMING HYPERGRAPH PARTITION FOR MASSIVE GRAPHS [Master's thesis, Kent State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=kent1385097649

    APA Style (7th edition)

  • Wang, Guan. STREAMING HYPERGRAPH PARTITION FOR MASSIVE GRAPHS. 2013. Kent State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=kent1385097649.

    MLA Style (8th edition)

  • Wang, Guan. "STREAMING HYPERGRAPH PARTITION FOR MASSIVE GRAPHS." Master's thesis, Kent State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=kent1385097649

    Chicago Manual of Style (17th edition)

kent1385097649
1,103
© 2013, all rights reserved.
This open access ETD is published by Kent State University and OhioLINK.