Correlation Constraint Shortest Path over Large Multi-Relation Graphs

Summary: Shortest path under vertex-correlation constraints on multi-relational graphs with recursive necessity and denial; extends beyond edge-label reachability. HyRE encodes topology and relation types compactly to prune search; evaluated on real-world graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12169
Venue: VLDB
Year: 2019
Pagerank: 5.5152959e-05
Overall Rank: 7,976 | 45.28%
DOI: 10.14778/3303753.3303756

Incoming Non-self Citations Over Time

Authors

1. Xiaofei Zhang (University of Memphis)
2. M. Tamer Özsu (University of Waterloo)

BibTeX Citation

@article{zhang_vldb19,
        title = {{Correlation Constraint Shortest Path over Large Multi-Relation Graphs}},
        author = {Zhang, Xiaofei and Özsu, M. Tamer},
        journal = {PVLDB},
        series = {{VLDB} '19},
        volume = {12},
        number = {5},
        pages = {488--501},
        doi = {10.14778/3303753.3303756},
        url = {https://doi.org/10.14778/3303753.3303756},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,603	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	5.824568e-05
11,271	Efficient Betweenness Centrality Computation over Large Heterogeneous Information Networks	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
370	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00019937972
433	Scalable Network Distance Browsing in Spatial Databases	2008	SIGMOD	0.00018532516
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
937	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013091546
1,251	Graph Indexing of Road Networks for Shortest Path Queries with Label Restrictions	2011	VLDB	0.00011484136
1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010318258
2,700	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	8.2411888e-05
3,948	Shortest Paths and Distances with Differential Privacy	2016	PODS	6.9993183e-05
4,289	Graph Indexing for Shortest-Path Finding over Dynamic Sub-Graphs	2016	SIGMOD	6.779194e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,647	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB
2	3,908	Diversified Top-k Graph Pattern Matching	2013	VLDB
3	10,748	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD
4	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
5	9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB
6	4,551	Hop-constrained s-t Simple Path Enumeration: Towards Bridging Theory and Practice	2020	VLDB
7	13,289	Effective Clustering for Large Multi-Relational Graphs	2026	SIGMOD
8	2,490	Computing Label-Constraint Reachability in Graph Databases	2010	SIGMOD
9	2,321	Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks	2020	VLDB
10	8,206	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB