  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.
