Efficiently Answering Quality Constrained Shortest Distance Queries in Large Graphs
Authors:
- 1 April 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 856-868
Abstract
One of the fundamental concept in the graph-related problem is the shortest path distance. This problem is widely studied for decades, and has numerous real-life applications. Nevertheless, quality constraints are naturally associated with edges. For instance, finding the distance between two vertices along valid edges (i.e., edges that satisfy a given quality constraint) is also critical. To fill this research gap, we investigate this vital problem, i.e., the quality constraint shortest distance problems. An efficient index structure is proposed based on 2-hop labeling approaches. By using a path dominance relationship into both quality and length information, it is demonstrated that the new index could ensure the minimal property. To further speed up the performance, we present an efficient query processing algorithm. Extensive experimental studies over real-life datasets demonstrates efficiency and effectiveness of our techniques.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Activity‐based kinase profiling of approved tyrosine kinase inhibitorsGenes to Cells, 2012
- GTPase activity regulates kinase activity and cellular phenotypes of Parkinson's disease-associated LRRK2Human Molecular Genetics, 2012
- Relationship strength estimation for online social networks with the study on FacebookNeurocomputing, 2012
- Solving shortest path problems with a weight constraint and replenishment arcsComputers & Operations Research, 2012
- Fast algorithm for successive computation of group betweenness centralityPhysical Review E, 2007
- A query language for biological networksBioinformatics, 2005
- Improved preprocessing, labeling and scaling algorithms for the Weight‐Constrained Shortest Path ProblemNetworks, 2003
- Reachability and Distance Queries via 2-Hop LabelsSIAM Journal on Computing, 2003
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- Complexity of Finding Embeddings in a k-TreeSIAM Journal on Algebraic Discrete Methods, 1987