不确定图上的近邻查询与近邻模式挖掘算法研究

摘要

图数据的不确定性普遍存在，研究不确定图上的高效查询处理与模式挖掘方法具有重要意义。本文研究的不确定图是指边上附带存在概率的不确定图。现有的不确定图上的查询和挖掘工作都是基于精确结构的，如子图匹配查询，子图模式挖掘等。然而实际应用存在两个问题：1.用户对于查询结果的结构要求并没有那么严格。2.图中许多重要的模式不一定都以同样的连接结构存在。
　　针对问题1，本文提出一种新型查询——近邻查询。给定一个查询标签集R和距离约束ζ，在不确定图G上进行近邻查询就是要找到标签集包含R并且任意两个顶点间距离不超过ζ的匹配顶点子集。为解决该问题，本文提出“可靠期望距离”，并基于可靠期望距离建立高效的近邻关系图索引，从而将不确定图上的近邻查询转化为近邻关系图上的团查询问题。最后使用树搜索算法解决近邻关系图上的团查询问题，其中一种两阶段预处理算法可以有效的降低搜索空间，分支界限方法可以进一步提高检索效率。
　　针对问题2，本文提出了不确定图上的近邻模式挖掘问题。近邻模式是一个由顶点标签构成的集合，这些标签在图中联系紧密且频繁。给定一个不确定图G和支持度阈值min_sup，近邻模式挖掘就是找出G中所有支持度超过min_sup的标签集合。本文基于可靠期望距离定义了不确定图近邻模式的支持度，并基于和近邻关系图索引提出了提出“近邻模式覆盖树”概念，提出两种高效的剪枝策略来得到所有近邻模式。
　　基于真实数据和合成数据的实验表明本文提出的近邻查询处理和近邻模式挖掘算法具有有效性和高效性。

目录

不确定图上的近邻查询与近邻模式挖掘算法研究

RESEARCH ON PROXIMITY QUERY AND PROXIMITY PATTERN MINING ALGORITHMS ON UNCERTAIN GRAPHS

摘 要

Abstract

目 录

第1章 绪 论

1.1 课题研究背景

1.2 不确定图上的查询研究现状

1.3 不确定图上的挖掘研究现状

1.4 不确定图上的查询与挖掘遇到的问题

1.5 论文的主要工作及章节安排

第2章 不确定图顶点距离度量

2.1 引言

2.2 不确定图

2.3 不确定图顶点距离度量函数

2.4 可靠期望距离及其计算

2.5 本章小结

第3章 不确定图上的top-k近邻查询处理

3.1 引言

3.2 不确定图上的top-k近邻查询

3.3 近邻查询处理

3.4 实验结果及分析

3.5 本章小结

第4章 不确定图上的近邻模式挖掘

4.1 引言

4.2 不确定图上的近邻模式

4.3 近邻模式挖掘算法

4.4 实验结果及分析

4.5 本章小结

结 论

参考文献

攻读硕士学位期间发表的论文

哈尔滨工业大学硕士位论文原创性声明

哈尔滨工业大学硕士学位论文使用授权书

致 谢