论文标题
有效地回答大图中质量约束的最短查询
Efficiently Answering Quality Constrained Shortest Distance Queries in Large Graphs
论文作者
论文摘要
最短的路径距离是图分析中的一个基本概念，并且在文献中进行了广泛的研究。在许多实际应用中，质量约束自然与图表中的边缘相关联，并且仅沿有效边缘（即满足给定质量约束的边缘）之间找到两个顶点$ s $和$ t $之间的最短距离也很重要。在本文中，我们研究了质量约束最短查询的这个新颖而重要的问题。我们提出了基于2-HOP标记方法的有效指数结构。在包含质量和长度信息的路径优势关系的支持下，我们证明了新指数的最低属性。还开发了有效的查询处理算法。对现实数据集的广泛实验研究表明了我们技术的效率和有效性。
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.
