论文标题：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倍的索引时间效率，同时实现可比的查询性能。实验结果也表明，我们的方法可以有效回答有序标签限制可达性查询。

文章精要

相关内容推荐：

文章精要 | 基于社交图和消息文本的自监督谣言检测 2023 17(4): 174611

文章精要 | D-Cubicle: 加速单GPU系统上的大规模分析查询的数据传输 2023 17(4): 174610

文章精要 | 一种新颖的面向长文本的稠密检索框架 2023 17(4): 174609

文章精要 | 合肥工业大学吴信东教授团队：采用分层注意力网络的联合用户画像 2023 17(3): 173608

文章精要 | 中山大学朱怀杰团队：最稀疏群体查询 2023 17(2): 172605

文章精要 | 东北大学张天成团队：认知诊断模型的新进展 2023 17(1): 171604

文章精要 | 东北大学乔百友团队：一种基于PredRNN结合注意力机制的有效海表温集成学习预测方法 2023 17(1): 171601

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中12种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn