Sage
Authors:
Open Access
- 1 September 2022
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 15 (13) , 3897-3910
Abstract
We propose Sage, a system for uncertain network analysis. Algorithms for uncertain network analysis require large amounts of memory and computing resources as they sample a large number of network instances and run analysis on them. Sage makes uncertain network analysis simple and efficient. By extending the edge-centric programming model, Sage makes writing sampling-based analysis algorithms as simple as writing conventional graph algorithms in Pregel-like systems. Moreover, Sage proposes four optimization techniques, namely, deterministic sampling, hybrid gathering, schedule-aware caching, and copy-on-write attributes, that exploit common properties of uncertain network analysis. Extensive evaluation of Sage with eight algorithms on six real-world networks shows that the four optimizations in Sage jointly improve performance by up to 13.9X and on average 2.7X.Keywords
This publication has 30 references indexed in Scilit:
- Uncertain Graph Processing through Representative InstancesACM Transactions on Database Systems, 2015
- Estimating unreliable objects and system reliability in P2P networksPeer-to-Peer Networking and Applications, 2014
- Detecting Protein Complexes Based on Uncertain Graph ModelIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2014
- Distributed socialiteProceedings of the VLDB Endowment, 2013
- A survey of frequent subgraph mining algorithmsThe Knowledge Engineering Review, 2012
- Distance-constraint reachability computation in uncertain graphsProceedings of the VLDB Endowment, 2011
- k-nearest neighbors in uncertain graphsProceedings of the VLDB Endowment, 2010
- Correlated pattern mining in quantitative databasesACM Transactions on Database Systems, 2008
- The link‐prediction problem for social networksJournal of the American Society for Information Science and Technology, 2007
- Maximizing the spread of influence through a social network2003