Efficient Index for Temporal Core Queries over Bipartite Graphs
Proceedings of the VLDB Endowment · 2024-07 · 17 (11) · 2813-2825
DOI: 10.14778/3681954.3681965 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 30.08.2024. Verfasst von Anxin Tian und 4 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 69 Literaturangaben.
Abstract (Originalsprache)
Many real-world binary relations can be modelled as bipartite graphs, which can be inherently temporal and each edge is associated with a timestamp. The ( α, β )-core, a popular structure that requires minimum degrees over two layers of vertices, is useful for understanding the organisation of bipartite networks. However, the temporal property has rarely been considered in cohesive subgraph mining in bipartite graphs. This gap prevents the finding of time-sensitive ( α, β )-cores in real-world applications. In this paper, we aim at finding ( α, β )-cores within any time window over a temporal bipartite graph. To address this problem, we propose a novel DAG (Directed Acyclic Graph)-like hierarchy with qualified time windows to describe the temporal containment property of the ( α, β )-core. Furthermore, we construct the superior-optimized index which significantly optimizes space complexity and guarantees efficient query performance. We also propose a maintenance approach that can efficiently update the index by removing stale information and incorporating newly inserted temporal edges. Extensive experiments are conducted on eight real-world graphs and the results show the effectiveness and efficiency of our indexes.
Zitieren
APA
Tian, A., Zhou, A., Wang, Y., Jian, X., & Chen, L. (2024). Efficient Index for Temporal Core Queries over Bipartite Graphs. Proceedings of the VLDB Endowment, 17(11), 2813-2825. https://doi.org/10.14778/3681954.3681965
Vancouver
Tian A, Zhou A, Wang Y, Jian X, Chen L. Efficient Index for Temporal Core Queries over Bipartite Graphs. Proceedings of the VLDB Endowment. 2024;17(11):2813-2825. doi:10.14778/3681954.3681965
BibTeX
@article{Tian2024,
author = {Tian, Anxin and Zhou, Alexander and Wang, Yue and Jian, Xun and Chen, Lei},
title = {Efficient Index for Temporal Core Queries over Bipartite Graphs},
journal = {Proceedings of the VLDB Endowment},
year = {2024},
volume = {17},
number = {11},
pages = {2813--2825},
doi = {10.14778/3681954.3681965}
}
EUVIMED