EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Enabling Cost-effective and Efficient All-Distance Sketching in Out-of-core Approximate Graph System

Tsun-Yu Yang, Yizou Chen, Yi Li, Bingzhe Li, Ming-Chang Yang

ACM Transactions on Storage · 30.12.2026 · 22 (4) · 1-30

DOI: 10.1145/3813113 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Storage, online erschienen am 17.08.2026. Verfasst von Tsun-Yu Yang und 4 weiteren Autor:innen. Die Arbeit nennt 51 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Research Grants Council, University Grants Committee.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 article 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.

Förderung

  • Research Grants Council, University Grants Committee

Zitieren

APA

Yang, T., Chen, Y., Li, Y., Li, B., & Yang, M. (2026). Enabling Cost-effective and Efficient All-Distance Sketching in Out-of-core Approximate Graph System. ACM Transactions on Storage, 22(4), 1-30. https://doi.org/10.1145/3813113

Vancouver

Yang T, Chen Y, Li Y, Li B, Yang M. Enabling Cost-effective and Efficient All-Distance Sketching in Out-of-core Approximate Graph System. ACM Transactions on Storage. 2026;22(4):1-30. doi:10.1145/3813113

BibTeX
@article{Yang2026,
  author = {Yang, Tsun-Yu and Chen, Yizou and Li, Yi and Li, Bingzhe and Yang, Ming-Chang},
  title = {Enabling Cost-effective and Efficient All-Distance Sketching in Out-of-core Approximate Graph System},
  journal = {ACM Transactions on Storage},
  year = {2026},
  volume = {22},
  number = {4},
  pages = {1--30},
  doi = {10.1145/3813113}
}
Kostenlos starten →