Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs

Summary: Index-based reachability for temporal bipartite graphs using time-aware 2-hop labeling over time-constrained wedges. Optimizations and parallelization speed up index construction; supports single-source reachability and earliest-arrival path queries, validated on 16 real-world graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12556
Venue: VLDB
Year: 2021
Pagerank: 6.3883109e-05
Overall Rank: 5,044 | 65.40%
DOI: 10.14778/3467861.3467873

Incoming Non-self Citations Over Time

Authors

1. Xiaoshuang Chen (University of New South Wales)
2. Kai Wang (University of New South Wales)
3. Xuemin Lin (University of New South Wales)
4. Wenjie Zhang (University of New South Wales)
5. Lu Qin (University of Technology Sydney)
6. Ying Zhang (University of Technology Sydney)

BibTeX Citation

@article{chen_vldb21,
        title = {{Efficiently Answering Reachability and Path Queries on Temporal Bipartite Graphs}},
        author = {Chen, Xiaoshuang and Wang, Kai and Lin, Xuemin and Zhang, Wenjie and Qin, Lu and Zhang, Ying},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {10},
        pages = {1845--1858},
        doi = {10.14778/3467861.3467873},
        url = {https://doi.org/10.14778/3467861.3467873},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,911	Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs	2024	VLDB	7.0240227e-05
9,049	BCviz: A Linear-Space Index for Mining and Visualizing Cohesive Bipartite Subgraphs	2025	SIGMOD	5.3251649e-05
9,118	Efficient Distributed Hop-Constrained Path Enumeration on Large-Scale Graphs	2024	SIGMOD	5.3201316e-05
9,132	HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs	2023	SIGMOD	5.31719e-05
9,557	Common Neighborhood Estimation over Bipartite Graphs under Local Differential Privacy	2024	SIGMOD	5.2528121e-05
9,916	Efficient Historical Butterfly Counting in Large Temporal Bipartite Networks via Graph Structure-aware Index	2025	VLDB	5.1955087e-05
10,446	Efficient and Effective Biclique Counting with Local Differential Privacy	2026	SIGMOD	5.093636e-05
10,683	Bursting Flow Query on Large Temporal Flow Networks	2025	SIGMOD	5.093636e-05
10,845	Efficient Maintenance of 2-Hop Labeling Index on Dynamic Small-World Graphs	2025	VLDB	5.093636e-05
11,225	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	5.093636e-05
11,248	Distributed Shortest Distance Labeling on Large-Scale Graphs	2024	VLDB	5.093636e-05
11,267	Efficient Maximal Frequent Group Enumeration in Temporal Bipartite Graphs	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 20 of 20 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022786599
322	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00021275303
444	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00018350865
679	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00015055389
706	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014789612
1,123	Path Problems in Temporal Graphs	2014	VLDB	0.00012089975
1,211	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011648789
1,301	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011255351
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
1,378	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010971508
1,553	Hop Doubling Label Indexing for Point-to-Point Distance Querying on Scale-Free Networks	2014	VLDB	0.0001037809
1,598	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00010242826
2,024	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.2907829e-05
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.2411888e-05
3,979	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB	6.9754185e-05
3,997	Efficient Bi-triangle Counting for Large Bipartite Networks	2021	VLDB	6.9679551e-05
4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB	6.6355948e-05
6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.824568e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
2	9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB
3	3,979	Reachability Querying: An Independent Permutation Labeling Approach	2014	VLDB
4	10,283	Querying Cohesive Subgraphs in Temporal Graphs	2026	SIGMOD
5	7,322	DLCR: Efficient Indexing for Label-Constrained Reachability Queries on Large Dynamic Graphs	2022	VLDB
6	3,836	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD
7	6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB
8	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
9	6,075	On Querying Historical Connectivity in Temporal Graphs	2024	SIGMOD
10	8,149	Efficient Index for Temporal Core Queries over Bipartite Graphs	2024	VLDB