含有计数量词的图模式匹配研究与实现

摘要

计数量词作为一种增强表达的方式，加入到图模式匹配中可以更加准确地描述客观世界。通过简单地在查询图的边上附加计数量词可以很自然的表达出全部和存在量化表达，比例和数量聚集表达，以及否定表达。这种增加了表达能力的图模式匹配在社会媒体营销，知识发现，网络安全等领域都有广泛且直接的应用。
　　关于量词化的图模式匹配问题的研究目前仍然比较新，而且该问题本身泛化了传统图模式匹配问题条件，传统图模式匹配问题仅属于本文问题的一个特例。因而本文所研究的量词化的图模式匹配问题复杂度远难于传统的图模式匹配。用边上计数量词是否包含否定计数量词可以将该问题划分成两个复杂度相异的两个子问题，第一类子问题模式图边上只包含肯定的计数量词，它的复杂度可以证明是NP完全的，并且在特定条件下复杂度的上下界都为NP难，而含有否定计数量词边的匹配问题复杂度则是 DP完全的，特定条件下复杂度上下界为DP难，如此高的复杂度使得蛮力法解决该问题的开销无法令人接受。
　　本文实现了（1）正QGP问题的匹配算法QMatch，该算法通过调用子图同构子算法而改进实现，本文通过实验验证发现算法在模式图规模在4以内时的匹配时间是比较好的，规模变大后的匹配时间呈指数式增长。（2）负QGP问题的匹配算法 IncQMatch，该算法避免了直接验证负计数量词的高复杂度，在正问题解决的基础上，利用集差思想，构建两个新的查询图结构得到最后的结果集，通过记录终结结果集的方式可以避免第二次查询从头开始有效地减少了运行时间，并且通过多线程的方式对该问题的匹配实现了并行化，实验表明当边上的负计数量词个数只有一时，IncQMatch的时间开销在查询图规模超过4以后同样呈显指数式的增长。（3）利用哈希编码技术给节点周围边标签和节点标签进行编码，通过与的手段压缩周围结构信息，并将周围的标签种类信息压缩到一串二进制字串当中，通过或运算匹配节点，得到小规模候选集合，在本文实验中，使用8+8位编码，可以过滤掉95%的不匹配，优化效率非常明显，且在查询图规模是6的时候都表现出了小于10秒的运行时间，优化效果非常显著。

目录

第1章 绪 论

1.1 课题背景及研究的目的和意义

1.2 国内外研究现状

1.3 本文的主要研究内容

1.4 论文组织结构

第2章 QGP的相关理论基础

2.1 引言

2.2 相关基本概念

2.2.1 传统的图模式匹配

2.2.2 量词化的图模式匹配

2.3 哈希编码

2.4 QGP问题的复杂性

2.5 本章小节

第3章 QGP问题相关算法的设计与实现

3.1 引言

3.2 QMatch算法的设计与实现

3.2.1 传统图模式匹配算法的优化

3.2.2 实验环境与使用数据集介绍

3.2.3 优化VF2后的实验结果

3.2.4 QSubMatch算法的设计与实现

3.2.5 正量化图模式匹配实验

3.3 IncQMatch算法的设计与实现

3.3.1 负量词化图模式匹配

3.3.2 负量词化图模式匹配实验

3.4 节点邻接信息编码

3.4.1 哈希编码的技术简述

3.4.2 哈希编码的效果实验

3.5 本章小节

结论

参考文献

攻读硕士学位期间发表的论文及其它成果

声明

致谢