欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2021108724124
申请人: 苏州工业职业技术学院
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2025-07-02
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于时间约束的时间图近似查询方法,其特征在于,包括如下步骤:S1:接收若干查询图,将若干所述查询图按照时间顺序放入查询等待队列;

S2:从所述查询等待队列依次取出若干所述查询图,并接收相对应的受限跳数h;

S3:将所述查询图在预存储的时间图中进行所述受限跳数h范围内的近似匹配,得到近似查询结果集;

S4:根据所述近似查询结果集和所述查询图的时间约束关系进行筛选,得到最终查询结果集;

S5:输出最终查询结果集,结束时间图近似查询。

2.根据权利要求1所述的基于时间约束的时间图近似查询方法,其特征在于,所述时间图内的相邻两个节点之间设有时间区间,所述时间约束关系为两个所述时间区间的关系,所述时间约束关系包括先于、部分重叠和包含。

3.根据权利要求2所述的基于时间约束的时间图近似查询方法,其特征在于,所述时间约束关系还包括时间约束值Δt,{ΔtαT|α∈{<,≤,=,>,≥}},其中,T为时间阈值;

两个所述时间区间之间先于关系下的先于时间间隔与所述时间约束值Δt相干;

两个所述时间区间之间部分重叠关系下的重叠时间区域与所述时间约束值Δt相干。

4.根据权利要求1所述的基于时间约束的时间图近似查询方法,其特征在于,所述步骤S3具体包括如下步骤

S31:读取所述查询图的第一个表项Q0,得到所述表项Q0的节点值和出入度值,并与所述时间图进行匹配得到点匹配结果集ResultV和边匹配结果集ResultE;

S32:根据所述步骤S31中的所述边匹配结果集ResultE进行合并,将合并结果放入结果集ResultQ,并更新所述点匹配结果集ResultV,而后清空执行合并后的所述边匹配结果集ResultE;

S33:读取所述查询图的下一个表项Q1,得到所述表项Q1的节点值和出入度值,并与所述时间图进行匹配更新所述点匹配结果集ResultV和所述边匹配结果集ResultE;

S34:根据所述步骤S33中的所述边匹配结果集ResultE进行合并,将合并结果放入所述结果集ResultQ,并更新所述点匹配结果集ResultV,而后清空所述边匹配结果集ResultE边匹配结果集;

S35:重复所述步骤S33和所述步骤S34直至读取完所述查询图内所有表项,得到所述近似查询结果集。

5.根据权利要求4所述的基于时间约束的时间图近似查询方法,其特征在于,所述步骤S31具体包括如下步骤

S311:读取所述查询图的第一个表项Q0,得到所述表项Q0的节点值和出入度值;

S312:从所述时间图找到与所述表项Q0相对应的数据块,读取所述数据块的每一数据项,

若所述数据项中所记载的出入度值大于或等于所述表项Q0的出入度值,则根据所述数据项更新所述点匹配结果集ResultV;

若读取完所述数据块的每一所述数据项,所述点匹配结果集ResultV未更新,则跳转至所述步骤S5,输出NULL并结束查询;

S313:读取所述表项Q0的链表项,得到所述表项Q0指向另一表项Qx;

S314:读取所述点匹配结果集ResultV内所述表项Q0的所对应的若干所述数据项,并依次对若干所述数据项在所述时间图中以所述受限跳数h范围内进行匹配,找到所述表项Q0至所述表项Qx的可达路径获取Q0Qx边匹配结果,并将与所述表项Qx相对应的匹配结果更新至所述点匹配结果集ResultV中,所述Q0Qx边匹配结果更新至所述边匹配结果集ResultE中;

S315:重复所述步骤S314,更新所述点匹配结果集ResultV和所述边匹配结果集ResultE,直至与所述表项Q0的所有所述链表项均匹配后跳转至所述步骤S32。

6.根据权利要求4所述的基于时间约束的时间图近似查询方法,其特征在于,所述步骤S33具体包括以下步骤

S331:读取所述查询图的下一个表项Q1,得到所述表项Q1的节点值和出入度值,查找所述点匹配结果集ResultV内是否存在所述表项Q1的匹配结果,若存在则进入步骤S332,若不存在则通过所述步骤S31对所述表项Q1进行匹配,并更新至所述点匹配结果集ResultV;

S332:读取所述表项Q1的链表项,得到所述表项Q1指向另一表项Qy,查找所述点匹配结果集ResultV是否存在所述表项Qy的匹配结果,若存在则进入步骤S333,若不存在则进入步骤S334;

S333:读取所述点匹配结果集ResultV内所述表项Q1和Qy的匹配结果,并依次对所述表项Q1的匹配结果在所述时间图中以所述受限跳数h范围内进行匹配,找到所述表项Q1至所述表项Qy的可达路径获取Q1Qy边匹配结果,并将所述Q1Qy边匹配结果更新至所述边匹配结果集ResultE中,跳转至步骤S335;

S334:读取所述点匹配结果集ResultV内所述表项Q1的匹配结果,并依次对所述表项Q1的匹配结果在所述时间图中以所述受限跳数h范围内进行匹配,找到所述表项Q1至所述表项Qy的可达路径获取Q1Qy边匹配结果,并将与所述表项Qy相对应的匹配结果更新至所述点匹配结果集ResultV中,所述Q1Qy边匹配结果更新至所述边匹配结果集ResultE中,跳转至步骤S335;

S335:重复所述步骤S332至所述步骤S334,更新所述点匹配结果集ResultV和所述边匹配结果集ResultE,直至与所述表项Q1的所有所述链表项均匹配后跳转至所述步骤S34。

7.根据权利要求1所述的基于时间约束的时间图近似查询方法,其特征在于,所述步骤S4具体包括如下步骤

S41:读取所述查询图的所述时间约束关系;

S42:依次读取所述结果集ResultQ的匹配结果,并基于所述查询图的所述时间约束关系将不符合时间约束的匹配结果去除,得到所述最终查询结果集。

8.一种基于时间约束的时间图近似查询装置,其特征在于,包括查询图接收器、第一存储器、查询图分析器、查询图匹配处理器、时间约束处理器和第二存储器,所述查询图接收器用于接收若干查询图,将若干所述查询图按照时间顺序放入所述第一存储器;

所述查询图分析器从所述第一存储器依次取出若干所述查询图,并接收相对应的受限跳数h;

所述查询图匹配处理器用于接收所述查询图和所述受限跳数h,并将所述查询图在预存储的时间图中进行所述受限跳数h范围内的近似匹配,得到近似查询结果集;

所述时间约束处理器用于接收所述近似查询结果集和所述查询图的时间约束关系,以此进行筛选得到最终查询结果集;

所述第二存储器用于接收并储存所述最终查询结果集,且能够输出所述最终查询结果集。

9.根据权利要求8所述的基于时间约束的时间图近似查询装置,其特征在于,所述查询图匹配处理器用于读取所述查询图的若干个表项,得到若干所述表项的节点值和出入度值,并将若干所述表项依次与所述时间图进行匹配得到点匹配结果集ResultV和边匹配结果集ResultE;将所述边匹配结果集ResultE进行合并,将合并结果放入结果集ResultQ,并更新所述点匹配结果集ResultV,而后清空执行合并后的所述边匹配结果集ResultE,得到所述近似查询结果集。

10.根据权利要求8所述的基于时间约束的时间图近似查询装置,其特征在于,所述时间约束处理器用于从所述查询图匹配处理器接收所述查询图的所述时间约束关系,并依次读取所述结果集ResultQ的匹配结果,并基于所述查询图的所述时间约束关系将不符合时间约束的匹配结果去除,得到所述得到最终查询结果集。