Answering reachability queries with ordered label constraints over labeled graphs  

作　　者：Daoliang HE Pingpeng YUAN Hai JIN 

机构地区：[1]National Engineering Research Center for Big Data Technology and System,Services Computing Technology and System Lab,Cluster and Grid Computing Lab,School of Computer Science&Technology,Huazhong University of Science and Technology,Wuhan 430074,China

出　　处：《Frontiers of Computer Science》2024年第1期105-117,共13页中国计算机科学前沿（英文版）

基　　金：supported by the National Natural Science Foundation of China(Grant Nos.61932004 and 62072205).

摘　　要：Reachability query plays a vital role in many graph analysis tasks.Previous researches proposed many methods to efficiently answer reachability queries between vertex pairs.Since many real graphs are labeled graph,it highly demands Label-Constrained Reachability(LCR)query inwhich constraint includes a set of labels besides vertex pairs.Recent researches proposed several methods for answering some LCR queries which require appearance of some labels specified in constraints in the path.Besides that constraint may be a label set,query constraint may be ordered labels,namely OLCR(Ordered-Label-Constrained Reachability)queries which retrieve paths matching a sequence of labels.Currently,no solutions are available for OLCR.Here,we propose DHL,a novel bloom filter based indexing technique for answering OLCR queries.DHL can be used to check reachability between vertex pairs.If the answers are not no,then constrained DFS is performed.So,we employ DHL followed by performing constrained DFS to answer OLCR queries.We show that DHL has a bounded false positive rate,and it's powerful in saving indexing time and space.Extensive experiments on 10 real-life graphs and 12 synthetic graphs demonstrate that DHL achieves about 4.8-22.5 times smaller index space and 4.6-114 times less index construction time than two state-of-art techniques for LCR queries,while achieving comparable query response time.The results also show that our algorithm can answer OLCR queries effectively.

关 键 词：graph ordered-label-constrained reachability partial index bloom filter query processing 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]