标签约束图上的k步可达性查询

标签约束图上的k步可达性查询问题,回答了在一个标签约束图上两点之间是否存在一条长度不大于k的路径并且这条路径上的标签都在用户给定的标签集中的问题。标签约束图上的k步可达性查询问题在现实中有着广泛的应用,然而现有算法无法直接回答这个问题。因此,首先提出LK2H算法。LK2H算法主要包括构建索引和查询两个步骤。第一步是给图上的所有顶点构建一组包含k和标签信息的2-Hop索引,第二步是基于构建好的索引进行查询。在查询时,为了尽可能地为用户返回更多的信息,LK2H算法优化了一类不可达查询的返回结果:当用户无法明确所有的标签类型,不能给出完整的标签约束,进而导致查询结果为不可达时,将完整的标签集返回给用户。其次,提出优化算法LK2H+。LK2H+算法通过构建部分顶点的2-Hop索引进一步缩减索引大小和索引的构建时间,并基于构建好的索引进行查询。查询时,需要对顶点按照是否构建了索引进行分类讨论。最后,基于15个真实数据集进行测试。实验结果表明,LK2H算法和LK2H+算法都可以高效地解决标签约束图上的k步可达性查询问题。