基于倒排索引的正则路径查询算法  

Efficient matching algorithm for regular path query based on inverted index

作　　者：夏秀峰 孙翔天 孙尧[2] 邓国鹏 朱康 邱涛 XIA Xiu-feng;SUN Xiang-tian;SUN Rao;DENG Guo-peng;ZHU Kang;QIU Tao(Department of Computer,Shenyang Aerospace University,Shenyang 110136,China;Flight Test Station,Shenyang Aircraft Industry(Group)Co.Ltd,Shenyang 110034,China)

机构地区：[1]沈阳航空航天大学计算机学院,辽宁沈阳110136 [2]沈阳飞机工业(集团)有限公司试飞站,辽宁沈阳110034

出　　处：《计算机工程与设计》2024年第8期2343-2349,共7页Computer Engineering and Design

基　　金：国家自然科学基金项目(62002245);科技部国家重点研发计划课题基金项目(2021YFB01);辽宁省自然科学基金项目(2022-BS-218)。

摘　　要：对于图数据上的正则路径查询(regular path query, RPQ)问题,其使用正则表达式定义图中两个节点之间的约束。针对现有的RPQ在图上遍历匹配方法效率低下这一问题,提出一种基于倒排索引的RPQ算法,在图上构建标签的倒排索引,匹配过程中快速检索标签的相应倒排列表。设计的IRPQ算法将查询转化为面向倒排列表的查询计划树,经过优化以减少冗余列表合并操作。在真实数据集上进行了实验,其结果表明,IRPQ及其优化算法相比现有方法显著提高了查询性能。Aiming the regular path query(RPQ)problem on graph data,in which regular expressions are used to define the constraints between two nodes in the graph,a RPQ algorithm based on inverted index was proposed to address the low efficiency issue of existing RPQ matching methods on graphs.An inverted index of labels was constructed on the graph,and it was used to quickly obtain posting lists of labels during RPQ processing to complete matching on the inverted lists.The designed IRPQ algorithm was used to convert the query into a query plan tree oriented to the inverted list and it was optimized to reduce redundant list merging operations.Experiments on real datasets show that the proposed IRPQ algorithm and its optimization methods significantly improve query performance compared to existing methods.

关 键 词：属性图模型 正则路径查询 倒排索引 查询计划树 树结构递归 启发式算法 查询树优化 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]