不确定图上基于标签限制的可达性查询技术的研究

摘要

近年来，图模型得到越来越多的重视，它不仅可以应用到路网及社交网络中，还可以应用到各种生物网络中。作为图上的基本查询之一，可达性查询得到了广泛的研究。可达性查询也是子图同构的图形查询的一个基本构成部分，因此可能会被频繁调用以处理大量数据和复杂查询，对它的有效支持就显得尤为重要。然而，由于统计误差等原因，图数据往往具有不确定性，且随着图中包含的信息越来越丰富，各式各样的标签图应需产生。在这些图上的一个基础研究问题是基于标签限制的可达性查询(LCR)，即查询任意两点间路径满足标签集限制的可达概率。针对不确定标签图，传统的可达性查询技术不再适用。
　　针对上面提出的问题，本文对不确定图上基于标签限制的可达性查询技术进行了研究。首先，针对概率图的不确定性，本文形式化定义了不确定图上基于标签和距离限制的可达性问题，接着提出了一种基于子路径的高效的剪枝方法，根据子路径和距离阈值的特性，通过分支路径过滤的剪枝方法，大幅度减少了子路径处理个数。最后给出了抽样方法包括Random Walk、不等概率抽样和DC树抽样方法。其次，针对标签集为有序限制的情况下，对上面的问题进行改进，定义了不确定图上有序标签限制的可达性查询问题，由此提出了一个迭代算法，即使用路径索引及有效的剪枝方法定位含有有序标签的边，接着用这些边构造新的子路径，连接成完整路径并记录，再使用蒙特卡罗采样方法对所有路径的概率和进行估计，并给出了Bonferroni和Chung-Erdos不等式界和路径/割界。最后，实验通过比其他方法验证了本文所提出的算法在高效性和准确性上的优越性，同时检验了各种剪枝优化方法的效率。
　　总之，本文从越来越接近实际应用的不确定图上基于标签限制的可达性查询的典型特征和挑战出发，针对不确定图上的路径标签的关键技术展开研究，如基于子路径、路径索引的数据结构的标签查询技术，预处理技术、分支路径过滤技术和拓扑顺序剪枝技术等，从而提供高效健壮的不确定图上基于标签限制的查询处理方法。本文的研究工作所采用的算法思想和剪枝更新策略将为相关课题的开展打下了坚实的基础。

目录

声明

摘要

第1章 引言

1．1 研究背景

1．2 图论相关知识

1．2．1 图的基本概念

1．2．2 图的基本算法

1．3 路径查询分类

1．3．1 简单的可达性查询

1．3．2 路径表达式查询

1．3．3 带有约束条件的可达性查询

1．4 问题提出

1．5 本文贡献

1．6 组织结构

第2章 相关工作

2．1 传统确定图的可达性查询

2．1．1 遍历访问次序的编码

2．1．2 节点遍历结果次序的编码

2．1．3 图的传递闭包矩阵

2．2 确定图上基于标签限制的可达性查询

2．3 不确定图上的可达性查询

2．3．1 解决树

2．3．2 不相交路径界

2．3．3 基于d-path和d-cut的方法

2．4 本章小结

第3章 不确定图上基于标签距离限制的可达性查询算法

3．1 问题描述

3．2 基于子路径的查询处理过程

3．2．1 子路径

3．2．2 子路径图

3．2．3 分治树

3．3 抽样

3．3．1 Random Walk抽样

3．3．2 基于DC-Tree的抽样

3．3．3 耶茨-格伦迪-森估计量

3．4 实验结果与分析

3．4．1 实验设置

3．4．2 实验分析

3．5 本章小结

第4章 不确定图上基于有序标签限制的可达性查询算法

4．1 问题描述

4．2 基于路径索引的查询处理过程

4．2．1 路径索引

4．2．2 有序标签定位

4．2．3 路径拼接

4．3 蒙特卡洛估计量

4．3．1 蒙特卡洛采样

4．3．2 收敛性分析与线性时间采样

4．3．3 Bonferroni和Chung-Erdos不等式界

4．3．4 路径／割界

4．4 结果与分析

4．4．1 实验设置

4．4．2 实验分析

4．5 本章小结

第5章 结论

5．1 本文的主要贡献与结论

5．2 进一步的工作

参考文献

致谢

攻读硕士学位期间的论文项目情况