Efficiently Answering Quality Constrained Shortest Distance Queries in Large Graphs
Preprint
Abstract
The shortest-path distance is a fundamental concept in graph analytics and has been extensively studied in the literature. In many real-world applications, quality constraints are naturally associated with edges in the graphs and finding the shortest distance between two vertices $s$ and $t$ along only valid edges (i.e., edges that satisfy a given quality constraint) is also critical. In this paper, we investigate this novel and important problem of quality constraint shortest distance queries. We propose an efficient index structure based on 2-hop labeling approaches. Supported by a path dominance relationship incorporating both quality and length information, we demonstrate the minimal property of the new index. An efficient query processing algorithm is also developed. Extensive experimental studies over real-life datasets demonstrates efficiency and effectiveness of our techniques.
Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Answering reachability and K-reach queries on large graphs with label constraintsThe VLDB Journal, 2021
- Efficient Hop-constrained s-t Simple Path EnumerationThe VLDB Journal, 2021
- Relationship strength estimation for online social networks with the study on FacebookNeurocomputing, 2012
- Computing weight constraint reachability in large networksThe VLDB Journal, 2012
- Solving shortest path problems with a weight constraint and replenishment arcsComputers & Operations Research, 2012
- Fast point-to-point shortest path computations with arc-flags2009
- A query language for biological networksBioinformatics, 2005
- Improved preprocessing, labeling and scaling algorithms for the Weight‐Constrained Shortest Path ProblemNetworks, 2003
- Graph minors. III. Planar tree-widthJournal of Combinatorial Theory, Series B, 1984
- S-functions for graphsJournal of Geometry, 1976