EUVIMEDEUVIMED entdecken
Crossref

Auxo: A Scalable and Efficient Graph Stream Summarization Structure

Zhiguo Jiang, Hanhua Chen, Hai Jin

Proceedings of the VLDB Endowment · 2023-02 · 16 (6) · 1386-1398

DOI: 10.14778/3583140.3583154 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 20.04.2023. Verfasst von Zhiguo Jiang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 17-mal zitiert (Crossref) und nennt 38 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A graph stream refers to a continuous stream of edges, forming a huge and fast-evolving graph. The vast volume and high update speed of a graph stream bring stringent requirements for the data management structure, including sublinear space cost, computation-efficient operation support, and scalability of the structure. Existing designs summarize a graph stream by leveraging a hash-based compressed matrix and representing an edge using its fingerprint to achieve practical storage for a graph stream with a known upper bound of data volume. However, they fail to support the dynamically extending of graph streams. In this paper, we propose Auxo, a scalable structure to support space/time efficient summarization of dynamic graph streams. Auxo is built on a proposed novel prefix embedded tree (PET) which leverages binary logarithmic search and common binary prefixes embedding to provide an efficient and scalable tree structure. PET reduces the item insert/query time from O (| E |) to O ( log | E |) as well as reducing the total storage cost by a log | E | scale, where | E | is the size of the edge set in a graph stream. To further improve the memory utilization of PET during scaling, we propose a proportional PET structure that extends a higher level in a proportionally incremental style. We conduct comprehensive experiments on large-scale real-world datasets to evaluate the performance of this design. Results show that Auxo significantly reduces the insert and query time by one to two orders of magnitude compared to the state of the arts. Meanwhile, Auxo achieves efficiently and economically structure scaling with an average memory utilization of over 80%.

Zitieren

APA

Jiang, Z., Chen, H., & Jin, H. (2023). Auxo: A Scalable and Efficient Graph Stream Summarization Structure. Proceedings of the VLDB Endowment, 16(6), 1386-1398. https://doi.org/10.14778/3583140.3583154

Vancouver

Jiang Z, Chen H, Jin H. Auxo: A Scalable and Efficient Graph Stream Summarization Structure. Proceedings of the VLDB Endowment. 2023;16(6):1386-1398. doi:10.14778/3583140.3583154

BibTeX
@article{Jiang2023,
  author = {Jiang, Zhiguo and Chen, Hanhua and Jin, Hai},
  title = {Auxo: A Scalable and Efficient Graph Stream Summarization Structure},
  journal = {Proceedings of the VLDB Endowment},
  year = {2023},
  volume = {16},
  number = {6},
  pages = {1386--1398},
  doi = {10.14778/3583140.3583154}
}
Kostenlos starten →