Computing Historical k-core in Parallel

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Temporal graphs capture time-stamped interactions in domains such as finance and social networks. Prior work formalized historical k-core queries and the PHC index; constructing it reduces to computing, for every vertex and start time, its core time--the earliest end time at which the vertex enters the k-core of the windowed snapshot. The existing method computes start times serially and propagates neighbor updates, introducing dependencies within each round of computation, which hinder parallelization and scalability. We revisit the task through a parallel lens and propose a vertex-centric algorithm that computes core times for multiple start times in parallel, then updates them incrementally for subsequent start times, preserving exactness while mitigating these dependencies. Experiments on real temporal graphs show consistent speedups over a single-threaded baseline and a naive lock-based parallelization.

Author Affiliations

@inproceedings{ma2025computing,
  title = {Computing Historical k-Core in Parallel},
  author = {Ma, Zhuo and Huang, Wei and Wen, Dong and Wang, Hanchen and Yang, Zhengyi},
  editor = {Borovica-Gajic, Renata and Khan, Arijit and Zheng, Bolong and Wang, Xiaoyang and Gan, Junhao},
  booktitle = {Databases Theory and Applications},
  year = {2026},
  publisher = {Springer Nature Singapore},
  address = {Singapore},
  pages = {18--32},
  isbn = {978-981-95-6196-4}
}