
You have already added 0 works in your ORCID record related to the merged Research product.
You have already added 0 works in your ORCID record related to the merged Research product.
<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://beta.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
DDSL: Efficient Subgraph Listing on Distributed and Dynamic Graphs
DDSL: Efficient Subgraph Listing on Distributed and Dynamic Graphs
Subgraph listing is a fundamental problem in graph theory and has wide applications in areas like sociology, chemistry, and social networks. Modern graphs can usually be large-scale as well as highly dynamic, which challenges the efficiency of existing subgraph listing algorithms. Recent works have shown the benefits of partitioning and processing big graphs in a distributed system, however, there is only few work targets subgraph listing on dynamic graphs in a distributed environment. In this paper, we propose an efficient approach, called Distributed and Dynamic Subgraph Listing (DDSL), which can incrementally update the results instead of running from scratch. DDSL follows a general distributed join framework. In this framework, we use a Neighbor-Preserved storage for data graphs, which takes bounded extra space and supports dynamic updating. After that, we propose a comprehensive cost model to estimate the I/O cost of listing subgraphs. Then based on this cost model, we develop an algorithm to find the optimal join tree for a given pattern. To handle dynamic graphs, we propose an efficient left-deep join algorithm to incrementally update the join results. Extensive experiments are conducted on real-world datasets. The results show that DDSL outperforms existing methods in dealing with both static dynamic graphs in terms of the responding time.
- Shanghai Jiao Tong University China (People's Republic of)
- Shanghai Jiao Tong University China (People's Republic of)
- Hong Kong University of Science and Technology (香港科技大學) China (People's Republic of)
- Shenzhen University China (People's Republic of)
- Hong Kong Polytechnic University China (People's Republic of)
FOS: Computer and information sciences, Computer Science - Databases, Databases (cs.DB)
FOS: Computer and information sciences, Computer Science - Databases, Databases (cs.DB)
8 Research products, page 1 of 1
- 2019IsAmongTopNSimilarDocuments
- 2019IsAmongTopNSimilarDocuments
- 2019IsAmongTopNSimilarDocuments
- 2019IsAmongTopNSimilarDocuments
- 2016IsAmongTopNSimilarDocuments
- 2020IsAmongTopNSimilarDocuments
- IsRelatedTo
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
