{"ID":2878635,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.18151","arxiv_id":"2508.18151","title":"Accelerating Historical K-Core Search in Temporal Graphs","abstract":"We study the temporal k-core component search (TCCS), which outputs the k-core containing the query vertex in the snapshot over an arbitrary query time window in a temporal graph. The problem has been shown to be critical for tasks such as contact tracing, fault diagnosis, and financial forensics. The state-of-the-art EF-Index designs a separated forest structure for a set of carefully selected windows, incurring quadratic preprocessing time and large redundant storage. Our method introduces the ECB-forest, a compact edge-centric binary forest that captures k-core of any arbitrary query vertex over time. In this way, a query can be processed by searching a connected component in the forest. We develop an efficient algorithm for index construction. Experiments on real-world temporal graphs show that our method significantly improves the index size and construction cost (up to 100x faster on average) while maintaining the high query efficiency.","short_abstract":"We study the temporal k-core component search (TCCS), which outputs the k-core containing the query vertex in the snapshot over an arbitrary query time window in a temporal graph. The problem has been shown to be critical for tasks such as contact tracing, fault diagnosis, and financial forensics. The state-of-the-art...","url_abs":"https://arxiv.org/abs/2508.18151","url_pdf":"https://arxiv.org/pdf/2508.18151v1","authors":"[\"Zhuo Ma\",\"Dong Wen\",\"Kaiyu Chen\",\"Yixiang Fang\",\"Xuemin Lin\",\"Wenjie Zhang\"]","published":"2025-08-25T15:57:28Z","proceeding":"cs.DB","tasks":"[\"cs.DB\"]","methods":"[]","has_code":false}