FCS 文章精要：华中科技大学袁平鹏教授团队：回答标记图上有序标签限制可达性查询

　　FCS 文章精要：华中科技大学袁平鹏教授团队：回答标记图上有序标签限制可达性查询。论文标题：Answering reachability queries with ordered label constraints over labeled graphs

　　 期刊：Frontiers of Computer Science

　　 作者：Daoliang HE, Pingpeng YUAN, Hai JIN

　　 发表时间：15 Feb 2024

　　 DOI：10.1007/s11704-022-2368-y

　　 微信链接：点击此处阅读微信文章

　　 导读

　　 有向图中的可达性查询问题，因其在很多图分析任务中扮演者重要角色而被广泛研究。标签限制可达性（LCR）查询问题则致力于回答边标记图中由特定的标签集合限制的可达性查询。然而在很多应用场景中，标签限制是一个标签序列而不仅仅是一个标签集合。在本文中，我们考虑标签之间的相对顺序，提出了有序标签限制可达性查询（OLCR）问题。为了回答OLCR查询，我们首先提出了基于布隆过滤器的索引技术DHL。回答LCR查询时，DHL有受限的假阳性率，并且建立索引的时间和空间效率很高。然后，我们结合DHL和受限制DFS提出了用于回答OLCR查询的算法。在10个真实图和12个虚拟图上的大量实验结果显示，相对于最新的两个LCR方案，DHL实现了4.8∼22.5倍的索引空间效率以及4.6∼114倍的索引时间效率，同时实现可比的查询性能。实验结果也表。