基于双向双区间标签实现k步可达性查询

k-step Reachability Queries Based on Bidirectional Double Interval Labeling Indexes

近年来,图的可达性查询已经成为一个研究热点。传统的可达性查询算法——GRAIL在处理k步可达性查询时具有较高的查询效率,但不适合处理不同分支顶点之间的k步可达性查询。为了解决上述问题,提出了一种新的双向双区间标签索引,进而实现了RE-GRAIL算法,从而有效解决了k步可达性查询问题。最后,在5个不同特征的数据集上进行实验,并从索引构建时间、索引大小、查询时间、扩展性4个方面进行验证。实验结果表明,与众多同类算法相比,RE-GRAIL算法具有更好的性能。

Recently,reachability query is one of the main research topics on graph data.GRAIL can deal with k-step reachability queries efficiently,however,it is not suitable for processing the query in which the vertex pairs are located in different branches.This paper further proposed RE-GRAIL algorithm which employs a bidirectional double interval labeling indexes to tackle the problem.At last,five real datasets were employed to validate the performances of the proposed algorithm in terms of different metrics,including indexing time index size,query processing time and scalability.Experimental results show that RE-GRAIL has better performance than other competitive algorithms.