EUVIMEDEUVIMED entdecken
Crossref

Efficient Temporal Subgraph Management: A New Interval Index

Dian Ouyang, Yikun Wang, Dong Wen, Wenjie Zhang, Yaping Liu, Xuemin Lin

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →