The Library
Distributed block formation and layout for disk-based management of large-scale graphs
Tools
Yaşar, Abdurrahman, Gedik, Buğra and Ferhatosmanoglu, Hakan (2017) Distributed block formation and layout for disk-based management of large-scale graphs. Distributed and Parallel Databases, 35 (1). pp. 23-53. doi:10.1007/s10619-017-7191-3 ISSN 0926-8782.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/s10619-017-7191-3
Abstract
We are witnessing an enormous growth in social networks as well as in the volume of data generated by them. An important portion of this data is in the form of graphs. In recent years, several graph processing and management systems emerged to handle large-scale graphs. The primary goal of these systems is to run graph algorithms and queries in an efficient and scalable manner. Unlike relational data, graphs are semi-structured in nature. Thus, storing and accessing graph data using secondary storage requires new solutions that can provide locality of access for graph processing workloads. In this work, we propose a scalable block formation and layout technique for graphs, which aims at reducing the I/O cost of disk-based graph processing algorithms. To achieve this, we designed a scalable MapReduce-style method called ICBL, which can divide the graph into a series of disk blocks that contain sub-graphs with high locality. Furthermore, ICBL can order the resulting blocks on disk to further reduce non-local accesses. We experimentally evaluated ICBL to showcase its scalability, layout quality, as well as the effectiveness of automatic parameter tuning for ICBL. We deployed the graph layouts generated by ICBL on the Neo4j open source graph database, http://www.neo4j.org/ (2015) graph database management system. Our results show that the layout generated by ICBL reduces the query running times over Neo4j more than $$2\times $$2× compared to the default layout.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Distributed and Parallel Databases | ||||
Publisher: | Springer New York LLC | ||||
ISSN: | 0926-8782 | ||||
Official Date: | March 2017 | ||||
Dates: |
|
||||
Volume: | 35 | ||||
Number: | 1 | ||||
Page Range: | pp. 23-53 | ||||
DOI: | 10.1007/s10619-017-7191-3 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |