Efficient Temporal Subgraph Management: A New Interval Index
Proceedings of the VLDB Endowment · 01.02.2026 · 19 (6) · 1170-1183
DOI: 10.14778/3797919.3797926 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 08.05.2026. Verfasst von Dian Ouyang und 5 weiteren Autor:innen. Die Arbeit nennt 56 Literaturangaben.
Abstract (Originalsprache)
Many research efforts have been conducted to mine various substructures in temporal graphs. Given a set of temporal subgraphs and an arbitrary time window, we aim to design an index structure to efficiently retrieve all subgraphs contained in (sub-valid) or containing (super-valid) the window. The problem falls in the category of fundamental interval range queries studying the relationship between a set of intervals and a query interval. We propose a novel data structure that is tailored for real-world temporal subgraphs with high volumes, great overlaps, and frequent updates. We design a lightweight linear size index structure with a linear index construction time. The index enables us to answer queries in near optimal time. We also propose algorithms to maintain the index. Our running time to insert a subgraph is bounded by the size of the changed values in the index, which is optimal in the context. Deleting a subgraph takes constant time. Experiments on real-world datasets with numerous subgraph instances demonstrate our significant advantages compared with existing baselines.
Zitieren
APA
Ouyang, D., Wang, Y., Wen, D., Zhang, W., Liu, Y., & Lin, X. (2026). Efficient Temporal Subgraph Management: A New Interval Index. Proceedings of the VLDB Endowment, 19(6), 1170-1183. https://doi.org/10.14778/3797919.3797926
Vancouver
Ouyang D, Wang Y, Wen D, Zhang W, Liu Y, Lin X. Efficient Temporal Subgraph Management: A New Interval Index. Proceedings of the VLDB Endowment. 2026;19(6):1170-1183. doi:10.14778/3797919.3797926
BibTeX
@article{Ouyang2026,
author = {Ouyang, Dian and Wang, Yikun and Wen, Dong and Zhang, Wenjie and Liu, Yaping and Lin, Xuemin},
title = {Efficient Temporal Subgraph Management: A New Interval Index},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {6},
pages = {1170--1183},
doi = {10.14778/3797919.3797926}
}
EUVIMED