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

k-step Reachability Query Processing on Label-constrained Graph

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

The k-step reachability query processing on label-constrained graph is used to answer whether there is a path with a length not greater than k between two points and the labels on this path are in the specified label set.The k-step reachability query processing on label-constrained graph is widely used in reality,but there is no relevant algorithm to answer it.Therefore,the LK2H algorithm is proposed firstly.LK2H algorithm mainly consists of two steps.The first step is to build a pair of 2-Hop in-dexes containing k and label information for all vertices on the graph,and the second step is querying based on the built index.In order to return information as much as possible to the user,LK2H optimizes the results of a type of unreachable query:when the user cannot specify all the label types,and cannot give full label constraints resulting in unreachable query results,the complete label set will return to the user.Secondly,an optimization algorithm,LK2H+,is proposed.LK2H+algorithm further reduces the index size and time of construction by building a 2-Hop index for part of vertices,and queries based on the built index.Queries require a discussion of whether query vertices are indexed or not.Finally,the test is conducted based on 15 real-world datasets.Experiment results show that both LK2H and LK2H+algorithms can solve k-step reachability query processing on label constraint graphs efficiently and quickly.