成梦佳，杜 明，周军锋

(东华大学，上海 松江 200000)

0 引言

互联网技术的发展与应用，催生出了海量的数据[1-2]。图作为一种常见的数据结构，能够较好地抽象描述数据之间的关联性。因此，图被广泛应用在各个领域中，如通信网络、生物信息网络、道路网络等[3-5]。

传统的可达性查询[6-11]用来回答给定的源点和终点之间是否存在可达的路径。但是实际网络中，顶点和边往往都会包含权值，例如通信网络中站点间的通讯交流就是通过带宽约束，保证多媒体流端到端的服务质量。因此，在回答可达性查询时考虑权值约束更贴合实际，有较高的研究价值。

现有的基于权值约束的可达性查询相关是Edge_Index[12]，它的主要思想是通过边上的权值构建索引树，预先存储先序遍历索引树得到的序列，尽管该算法的查询效率很高，但是构建的索引占用的空间内存过大，无法在内存有限的环境下处理顶点规模大的数据图。

针对以上问题，本文提出一种基于权值约束的 2-hop索引算法。该算法基于顶点的度来确定顶点的处理顺序，然后基于该顺序来构建加权图的 2-hop索引。其基本思想是将加权图上的权值约束可达查询转换为基于顶点标签的集合交集操作，从而减小构建索引的时间和空间代价。实验结果表明，本文提出的方法能有效地降低索引规模，提高回答查询的响应速度。

1 问题定义和相关工作

1.1 相关概念和问题定义

本文基于无向加权图处理权值约束可达性查询的问题。……