On More Efficiently and Versatilely Querying Historical k-Cores

Summary: 'Core time shell' and MCTS-index expose hierarchical core-time structure to avoid full-vertex scans, yielding approximately optimal historical k-core query time with PHC-like space. MCTS also enables a novel 'when' query and empirically outperforms PHC. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13802
Venue: VLDB
Year: 2025
Pagerank: 4.1905499e-05
Overall Rank: 10,556 | 26.64%
DOI: 10.14778/3718057.3718063

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,150	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013647447
3,369	Online Density Bursting Subgraph Detection from Temporal Graphs	2019	VLDB	7.1656755e-05
4,133	On Querying Historical K-Cores	2021	VLDB	6.4185206e-05
4,209	Mining Bursting Core in Large Temporal Graphs	2022	VLDB	6.3511029e-05
4,726	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.9632682e-05
6,501	Reliable Community Search in Dynamic Networks	2022	VLDB	5.0293058e-05
6,660	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9672425e-05
7,339	Scalable Time-Range k-Core Query on Temporal Graphs	2023	VLDB	4.7530782e-05
7,446	QTCS: Efficient Query-Centered Temporal Community Search	2024	VLDB	4.7232788e-05
7,581	Querying Structural Diversity in Streaming Graphs	2024	VLDB	4.701915e-05
8,172	LM-SRPQ: Efficiently Answering Regular Path Query in Streaming Graphs	2024	VLDB	4.5653572e-05
9,042	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	4.3997447e-05
11,047	Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation	2024	VLDB	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,548	Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs	2021	VLDB	5.4445937e-05
9,484	MCR-Tree: An Efficient Index for Multi-dimensional Core Search	2024	SIGMOD	4.3300131e-05
7,446	QTCS: Efficient Query-Centered Temporal Community Search	2024	VLDB	4.7232788e-05
4,726	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.9632682e-05
10,232	Efficient Temporal Subgraph Management: A New Interval Index	2026	VLDB	4.1905499e-05
11,047	Evolution Forest Index: Towards Optimal Temporal k-Core Component Search via Time-Topology Isomorphic Computation	2024	VLDB	4.1905499e-05
6,660	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD	4.9672425e-05
11,045	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB	4.1905499e-05
7,339	Scalable Time-Range k-Core Query on Temporal Graphs	2023	VLDB	4.7530782e-05
4,133	On Querying Historical K-Cores	2021	VLDB	6.4185206e-05