EUVIMEDEUVIMED entdecken
Crossref

On Querying Historical Connectivity in Temporal Graphs

Jingyi Song, Dong Wen, Lantian Xu, Lu Qin, Wenjie Zhang, Xuemin Lin

Proceedings of the ACM on Management of Data · 29.05.2024 · 2 (3) · 1-25

DOI: 10.1145/3654960 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2024. Verfasst von Jingyi Song und 5 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 40 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the historical connectivity query in temporal graphs where edges continuously arrive. Given an arbitrary time window, and two query vertices, the problem aims to identify if two vertices are connected by a path in the snapshot of the window. The state-of-the-art method designs an index based on the two-hop cover, and updating the index is costly when new edges arrive. In this paper, we propose a new framework and design a novel forest-based index for historical connectivity queries. The index enables us to answer queries by searching if two vertices are connected in the forest. We update the index by modifying a forest structure. Our techniques also work for connectivity query processing in a sliding window of temporal graphs. Extensive experiments have been conducted to show the considerable advantages of our approach compared with the state-of-the-art methods in both historical connectivity queries and sliding-window connectivity queries.

Zitieren

APA

Song, J., Wen, D., Xu, L., Qin, L., Zhang, W., & Lin, X. (2024). On Querying Historical Connectivity in Temporal Graphs. Proceedings of the ACM on Management of Data, 2(3), 1-25. https://doi.org/10.1145/3654960

Vancouver

Song J, Wen D, Xu L, Qin L, Zhang W, Lin X. On Querying Historical Connectivity in Temporal Graphs. Proceedings of the ACM on Management of Data. 2024;2(3):1-25. doi:10.1145/3654960

BibTeX
@article{Song2024,
  author = {Song, Jingyi and Wen, Dong and Xu, Lantian and Qin, Lu and Zhang, Wenjie and Lin, Xuemin},
  title = {On Querying Historical Connectivity in Temporal Graphs},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2024},
  volume = {2},
  number = {3},
  pages = {1--25},
  doi = {10.1145/3654960}
}
Kostenlos starten →