|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
I/O Efficient Core Graph Decomposition at Web Scale | | Dong Wen
; Lu Qin
; Ying Zhang
; Xuemin Lin
; Jeffrey Xu Yu
; | | Date: |
2 Nov 2015 | | Abstract: | Core decomposition is a fundamental graph problem with a large number of
applications. Most existing approaches for core decomposition assume that the
graph is kept in memory of a machine. Nevertheless, many real-world graphs are
big and may not reside in memory. In the literature, there is only one work for
I/O efficient core decomposition that avoids loading the whole graph in memory.
However, this approach is not scalable to handle big graphs because it cannot
bound the memory size and may load most parts of the graph in memory. In
addition, this approach can hardly handle graph updates. In this paper, we
study I/O efficient core decomposition following a semi-external model, which
only allows node information to be loaded in memory. This model works well in
many web-scale graphs. We propose a semi-external algorithm and two optimized
algorithms for I/O efficient core decomposition using very simple structures
and data access model. To handle dynamic graph updates, we show that our
algorithm can be naturally extended to handle edge deletion. We also propose an
I/O efficient core maintenance algorithm to handle edge insertion, and an
improved algorithm to further reduce I/O and CPU cost by investigating some new
graph properties. We conduct extensive experiments on 12 real large graphs. Our
optimal algorithm significantly outperform the existing I/O efficient algorithm
in terms of both processing time and memory consumption. In many
memory-resident graphs, our algorithms for both core decomposition and
maintenance can even outperform the in-memory algorithm due to the simple
structures and data access model used. Our algorithms are very scalable to
handle web-scale graphs. As an example, we are the first to handle a web graph
with 978.5 million nodes and 42.6 billion edges using less than 4.2 GB memory. | | Source: | arXiv, 1511.0367 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER