Enabling Cost-effective and Efficient All-Distance Sketching in Out-of-core Approximate Graph System
Open Access
- 8 May 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Storage
- Vol. 22 (4) , 1-30
Abstract
The All-Distances Sketch (ADS) is a powerful and theoretically-sound sketching scheme that captures neighborhood information in graphs for approximate processing. It enables high-accuracy estimation of many useful applications with a guarantee of accuracy and can significantly accelerate the execution times by orders of magnitude. However, ADS requires a substantial amount of space that is multiple times larger than the graph data. More seriously, existing studies mainly focus on managing ADSs in memory, posing an increasing challenge for users who aim to leverage ADS for large-scale graph processing, particularly in light of the exponential growth of real-world graphs nowadays. To this end, this paper introduces Oasis, an O ut-of-core A pproximate graph SYS tem that brings the ADS technique into practical use by leveraging storage effectively. Specifically, Oasis offers a holistic framework that facilitates both ADS construction and estimation. For ADS construction, it allows users to adjust the memory usage based on the machine’s available memory and enable an efficient construction process. For ADS estimation, Oasis provides a user-friendly interface to easily execute the estimators while mitigating the impact of slow storage I/O. Evaluation results show that Oasis provides a practical graph processing solution with exceptional execution time and low memory usage, at the cost of a slight decrease in accuracy.Keywords
Funding Information
- Research Grants Council, University Grants Committee (CUHK14208521)
This publication has 36 references indexed in Scilit:
- DKWS: A Distributed System for Keyword Search on Massive GraphsIEEE Transactions on Knowledge and Data Engineering, 2023
- An Unequal Caching Strategy for Shared-Memory Graph AnalyticsIEEE Transactions on Parallel and Distributed Systems, 2023
- Reciprocal Recommender Systems: Analysis of state-of-art literature, challenges and opportunities towards social recommendationInformation Fusion, 2021
- PPKWS: An Efficient Framework for Keyword Search on Public-Private Networks2020
- Social network analysis: An overviewWIREs Data Mining and Knowledge Discovery, 2018
- Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+2015
- Scalable Influence Maximization in Social Networks under the Linear Threshold Model2010
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined ClustersInternet Mathematics, 2009
- Approximate distance oraclesJournal of the ACM, 2005
- Size-Estimation Framework with Applications to Transitive Closure and ReachabilityJournal of Computer and System Sciences, 1997