More Web Proxy on the site http://driver.im/

research-article

Efficient data partitioning model for heterogeneous graphs in the cloud

Authors:

Ling LiuAuthors Info & Claims

SC '13: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis

Article No.: 46, Pages 1 - 12

https://doi.org/10.1145/2503210.2503302

Published: 17 November 2013 Publication History

Abstract

As the size and variety of information networks continue to grow in many scientific and engineering domains, we witness a growing demand for efficient processing of large heterogeneous graphs using a cluster of compute nodes in the Cloud. One open issue is how to effectively partition a large graph to process complex graph operations efficiently. In this paper, we present VB-Partitioner -- a distributed data partitioning model and algorithms for efficient processing of graph operations over large-scale graphs in the Cloud. Our VB-Partitioner has three salient features. First, it introduces vertex blocks (VBs) and extended vertex blocks (EVBs) as the building blocks for semantic partitioning of large graphs. Second, VB-Partitioner utilizes vertex block grouping algorithms to place those vertex blocks that have high correlation in graph structure into the same partition. Third, VB-Partitioner employs a VB-partition guided query partitioning model to speed up the parallel processing of graph pattern queries by reducing the amount of inter-partition query processing. We conduct extensive experiments on several real-world graphs with millions of vertices and billions of edges. Our results show that VB-Partitioner significantly outperforms the popular random block-based data partitioner in terms of query latency and scalability over large-scale graphs.

References

[1]

About FacetedDBLP. http://dblp.l3s.de/dblp++.php.

[2]

BTC 2012 Dataset. http://km.aifb.kit.edu/projects/btc-2012/.

[3]

Chaco: Software for Partitioning Graphs. http://www.sandia.gov/bahendr/chaco.html.

[4]

DBpedia 3.8 Downloads. http://wiki.dbpedia.org/Downloads38.

[5]

METIS. http://www.cs.umn.edu/~metis.

[6]

K. Andreev and H. Räcke. Balanced graph partitioning. In Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, SPAA '04, pages 120--124, New York, NY, USA, 2004. ACM.

Digital Library

[7]

P. Barceló, L. Libkin, and J. L. Reutter. Querying graph patterns. In Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, PODS '11, pages 199--210, New York, NY, USA, 2011. ACM.

Digital Library

[8]

C. Franke, S. Morin, A. Chebotko, J. Abraham, and P. Brazier. Distributed Semantic Web Data Management in HBase and MySQL Cluster. In Proceedings of the 2011 IEEE 4th International Conference on Cloud Computing, CLOUD '11, pages 105--112, Washington, DC, USA, 2011. IEEE Computer Society.

Digital Library

[9]

B. Hendrickson and R. Leland. A multilevel algorithm for partitioning graphs. In Proceedings of the 1995 ACM/IEEE conference on Supercomputing, Supercomputing '95, New York, NY, USA, 1995. ACM.

Digital Library

[10]

J. Huang, D. J. Abadi, and K. Ren. Scalable SPARQL querying of large RDF graphs. Proceedings of the VLDB Endowment, 4(11):1123--1134, 2011.

Digital Library

[11]

M. Husain, J. McGlothlin, M. M. Masud, L. Khan, and B. M. Thuraisingham. Heuristics-Based Query Processing for Large RDF Graphs Using Cloud Computing. IEEE Trans. on Knowl. and Data Eng., 23(9):1312--1327, Sept. 2011.

Digital Library

[12]

G. Karypis and V. Kumar. Analysis of multilevel graph partitioning. In Proceedings of the 1995 ACM/IEEE conference on Supercomputing, Supercomputing '95, New York, NY, USA, 1995. ACM.

Digital Library

[13]

G. Karypis and V. Kumar. Parallel multilevel k-way partitioning scheme for irregular graphs. In Proceedings of the 1996 ACM/IEEE conference on Supercomputing, Supercomputing '96, Washington, DC, USA, 1996. IEEE Computer Society.

Digital Library

[14]

G. Karypis and V. Kumar. Multilevel algorithms for multi-constraint graph partitioning. In Proceedings of the 1998 ACM/IEEE conference on Supercomputing, Supercomputing '98, pages 1--13, Washington, DC, USA, 1998. IEEE Computer Society.

Digital Library

[15]

A. Kyrola, G. Blelloch, and C. Guestrin. GraphChi: large-scale graph computation on just a PC. In Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation, OSDI'12, pages 31--46, Berkeley, CA, USA, 2012. USENIX Association.

Digital Library

[16]

Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein. Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proc. VLDB Endow., 5(8):716--727, Apr. 2012.

Digital Library

[17]

G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, SIGMOD '10, pages 135--146, New York, NY, USA, 2010. ACM.

Digital Library

[18]

T. Neumann and G. Weikum. The RDF-3X engine for scalable management of RDF data. The VLDB Journal, 19(1), Feb. 2010.

Digital Library

[19]

K. Rohloff and R. E. Schantz. Clause-iteration with MapReduce to scalably query datagraphs in the SHARD graph-store. In Proceedings of the fourth international workshop on Data-intensive distributed computing, DIDC '11, pages 35--44, New York, NY, USA, 2011. ACM.

Digital Library

[20]

B. White and et al. An integrated experimental environment for distributed systems and networks. In Proceedings of the 5th symposium on Operating systems design and implementation, OSDI '02, pages 255--270, 2002.

Digital Library

[21]

P. Yuan, P. Liu, B. Wu, H. Jin, W. Zhang, and L. Liu. TripleBit: a Fast and Compact System for Large Scale RDF Data. Proceedings of the VLDB Endowment, 6(7), 2013.

Digital Library

Cited By

Si BLiang YZhao JZhang YLiao XJin HLiu HGu L(2022)GGraph: An Efficient Structure-Aware Approach for Iterative Graph ProcessingIEEE Transactions on Big Data10.1109/TBDATA.2020.30196418:5(1182-1194)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TBDATA.2020.3019641
Li SChen WLiu BLiu PWang XLi Y(2022)OntoSP: Ontology-Based Semantic-Aware Partitioning on RDF GraphsWeb Information Systems Engineering – WISE 202110.1007/978-3-030-90888-1_21(258-273)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-90888-1_21
Chinna JKavitha K(2021)An Efficient Node Priority and Threshold-Based Partitioning Algorithm for Graph ProcessingIntelligent Computing and Innovation on Data Science10.1007/978-981-15-3284-9_84(783-792)Online publication date: 18-Nov-2021
https://doi.org/10.1007/978-981-15-3284-9_84
Show More Cited By

Index Terms

Efficient data partitioning model for heterogeneous graphs in the cloud
1. Information systems
  1. Information retrieval
  2. Information storage systems

Recommendations

Partitioning 2-edge-colored graphs by monochromatic paths and cycles

We present results on partitioning the vertices of 2-edge-colored graphs into monochromatic paths and cycles. We prove asymptotically the two-color case of a conjecture of Sárközy: the vertex set of every 2-edge-colored graph can be partitioned into at ...
Partitioning powers of traceable or hamiltonian graphs

A graph G=(V,E) is arbitrarily partitionable (AP) if for any sequence @t=(n"1,...,n"p) of positive integers adding up to the order of G, there is a sequence of mutually disjoint subsets of V whose sizes are given by @t and which induce connected graphs. ...
Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus
STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing

In this paper, we address two longstanding questions about finding good separators in graphs of bounded genus and degree: 1. It is a classical result of Gilbert, Hutchinson, and Tarjan [12] that one can find asymptotically optimal separators on these ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '13: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis

November 2013

1123 pages

ISBN:9781450323789

DOI:10.1145/2503210

General Chair:
William Gropp
University of Illinois at Urbana-Champaign, Urbana, Illinois
,
Program Chair:
Satoshi Matsuoka
Tokyo Institute of Technology, Tokyo, Japan

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SC13

Sponsor:

SIGHPC
SIGARCH
IEEE-CS

SC13: International Conference for High Performance Computing, Networking, Storage and Analysis

November 17 - 21, 2013

Colorado, Denver

Acceptance Rates

SC '13 Paper Acceptance Rate 91 of 449 submissions, 20%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
493
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)3

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Si BLiang YZhao JZhang YLiao XJin HLiu HGu L(2022)GGraph: An Efficient Structure-Aware Approach for Iterative Graph ProcessingIEEE Transactions on Big Data10.1109/TBDATA.2020.30196418:5(1182-1194)Online publication date: 1-Oct-2022
https://doi.org/10.1109/TBDATA.2020.3019641
Li SChen WLiu BLiu PWang XLi Y(2022)OntoSP: Ontology-Based Semantic-Aware Partitioning on RDF GraphsWeb Information Systems Engineering – WISE 202110.1007/978-3-030-90888-1_21(258-273)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-90888-1_21
Chinna JKavitha K(2021)An Efficient Node Priority and Threshold-Based Partitioning Algorithm for Graph ProcessingIntelligent Computing and Innovation on Data Science10.1007/978-981-15-3284-9_84(783-792)Online publication date: 18-Nov-2021
https://doi.org/10.1007/978-981-15-3284-9_84
Leng YWang HLu F(2020)Artificial Intelligence Knowledge Graph for Dynamic Networks: An Incremental Partition AlgorithmIEEE Access10.1109/ACCESS.2020.29826528(63434-63442)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2982652
Chinna JKavitha K(2020)An Efficient Node Priority and Threshold-Based Partitioning Algorithm for Graph ProcessingIntelligent Computing and Innovation on Data Science10.1007/978-981-15-3284-9_90(783-792)Online publication date: 15-May-2020
https://doi.org/10.1007/978-981-15-3284-9_90
Gu ZZhang SCao C(2019) Reasoning and querying web-scale open data based on DL-Lite in a divide-and-conquer way Journal of Web Semantics10.1016/j.websem.2019.01.003Online publication date: Feb-2019
https://doi.org/10.1016/j.websem.2019.01.003
Devi RMurugaboopathi G(2019)An efficient clustering and load balancing of distributed cloud data centers using graph theoryInternational Journal of Communication Systems10.1002/dac.389632:5Online publication date: 4-Jan-2019
https://doi.org/10.1002/dac.3896
Farooqui NRoy IChen YTalwar VBarik RLewis BShpeisman TSchwan K(2018)Accelerating Data Analytics on Integrated GPU Platforms via Runtime SpecializationInternational Journal of Parallel Programming10.1007/s10766-016-0482-x46:2(336-375)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s10766-016-0482-x
Arfat YMehmood RAlbeshri A(2018)Parallel Shortest Path Graph Computations of United States Road Network Data on Apache SparkSmart Societies, Infrastructure, Technologies and Applications10.1007/978-3-319-94180-6_30(323-336)Online publication date: 22-Jul-2018
https://doi.org/10.1007/978-3-319-94180-6_30
Janke DStaab S(2018)Storing and Querying Semantic Data in the CloudReasoning Web. Learning, Uncertainty, Streaming, and Scalability10.1007/978-3-030-00338-8_7(173-222)Online publication date: 22-Sep-2018
https://dl.acm.org/doi/10.1007/978-3-030-00338-8_7
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents