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

对于图数据上的正则路径查询(regular path query, RPQ)问题,其使用正则表达式定义图中两个节点之间的约束。针对现有的RPQ在图上遍历匹配方法效率低下这一问题,提出一种基于倒排索引的RPQ算法,在图上构建标签的倒排索引,匹配过程中快速检索标签的相应倒排列表。设计的IRPQ算法将查询转化为面向倒排列表的查询计划树,经过优化以减少冗余列表合并操作。在真实数据集上进行了实验,其结果表明,IRPQ及其优化算法相比现有方法显著提高了查询性能。