可达性查询用于研究图中给定源点和终点之间是否存在一条可达路径,基于权值约束的可达性查询是可达性查询的其中一种,用于回答给定两个查询的顶点之间是否存在一条路径,并且其每条边上的权值都满足给定的约束条件。相较于传统的可达性查询,权值约束的可达性查询在实际生活中更有意义,如基因蛋白质生物网络、通信网络、道路交通网络等,这些图的边上往往会记录包含特定信息的数据以描述顶点之间关联性的强弱程度,而这种关联的约束信息无法用传统可达查询来体现,只能通过基于权值约束的可达查询处理。现有的基于权值约束可达性查询的相关算法尽管查询响应时间较快,但是其构建的索引规模太大,无法在内存有限的情况下,处理规模较大的数据图。针对以上问题,本文提出三种高效索引来支持在有限内存的环境下高效处理大规模数据图上的权值约束可达查询。本文的研究内容如下:首先,提出一种基于加权图的2-hop索引及其构建算法。该算法基于顶点的度来确定顶点的处理顺序,然后基于该顺序来构建加权图的2-hop索引。该方法的基本思想是将加权图上的权值约束可达查询转换为基于顶点标签的集合交集操作。考虑到基于加权图来构建2-hop索引的时间和空间代价过高,进一步提出基于最小和最大生成树的2-hop索引方法。该方法首先构建原图的最小和最大生成树,然后按照度从大到小的顺序在生成树上构建索引,从而减小构建索引的时间和空间代价。其次,考虑到顶点的处理顺序会极大影响2-hop索引的规模和构建时间,提出优化的2-hop索引构建策略。和以上提出的2-hop索引方法不同,优化方法是在构建2-hop索引的过程中,根据顶点划分子图的变化情况来动态确定下一个最适合处理的顶点,以此来减小2-hop索引的规模和构建时间。具体来说,该方法在生成树的基础上,通过找树的中间结点作为hop点来构建2-hop索引。之后删除该点,可得到若干子树,对每棵子树重复以上操作。最后,基于多个真实数据集进行实验测试,以索引大小、索引构建时间和查询响应时间为指标,对本文提出的算法的高效性进行了验证。实验结果表明,基于大度顶点的优化策略和基于中间结点的优化策略都能够有效降低索引的规模大小,并且后者具有更好的查询效率。