大规模图数据查询处理关键技术研究

摘要

随着互联网和数据库技术的不断发展，作为一种通用的数据结构，图数据已在越来越多的应用中广泛存在，例如生物信息网络、社交网络、知识图谱等。图数据上的查询处理（如最短路径查询、可达查询、关键字查询等）是数据库领域最基础的问题之一。尤其随着现如今大数据时代的到来，如何在大规模图数据上进行高效的查询处理显得日益重要。虽然研究者近年来在图数据的查询处理技术上已经取得了长足的进展，但随着数据发展日趋多样性，在实际应用中，图数据混合了多种复杂的信息，如不确定信息、时空信息等。因此，为迎合用户在实际生活中的需求，图数据上的查询处理需要针对特定环境下进行更加合理高效建模，并设计相应的高效计算处理技巧。而另一方面，由于图数据本身所具有的复杂拓扑结构的性质，图上的查询处理大多计算复杂度非常高，因而为大数据环境下的高效计算带来了巨大的挑战。为此，本文从用户在不同实际应用场景下的需求入手进行分析，进行合理的建模，并提出了有针对性的高效查询处理算法。 (1)大规模关联不确定图上的最短路径查询。分析了实际应用中图数据上的不确定信息彼此间存在的相关性，从而提出了一种基于马尔可夫网络的关联不确定图模型，以克服现有独立不确定图模型中的不足。由于在关联不确定图模型上计算最短路径概率是一个#P-难问题，本文提出了一种过滤-验证的方法来高效地求解该问题。在过滤步骤中，本文计算出最短路径概率的一系列上界。同时，设计一种概率最短路径索引，来管理这些上界，并辅助利用这些上界来过滤掉对查询结果无用的结点和边。由于构建最优索引依然是一个NP-难问题，本文提供一种O(logn)-近似的多项式时间算法来构建索引。在过滤步骤之后，仅剩余一小部分子图作为候选集。验证步骤在该候选集上进行高效的采样算法来计算出最终结果。 (2)分布式环境下不确定图上的可达查询。分析了在实际应用中，尤其是大数据环境下，不确定图数据通常是分布式存储的。而现在有的不确定图上的可达查询均为集中式算法，且由于该问题是#P-完全的，即使在集中式小图环境下计算，其代价也非常高。本文发现，虽然在全图上计算可达概率是#P-完全的，但在一大部分子图上的可达概率却是多项式时间可计算的。因此，本文提出一种分布式图简化和分布式确认的策略来高效地计算结果。在分布式图简化的步骤中，将所有的可达概率在多项式时间内可计算的子图简化成一条单边。在分布式确认步骤中，将该问题转化为高效的表连接问题，并利用近似算法来计算最终结果。 (3)大规模容错知识图谱上的关键字查询。分析了容错性是知识图谱在现实生活中的主要特征之一。而现有的图数据上关键字查询定义如果直接应用到容错知识图谱中则会返回给用户错误的结果。为此，本文针对容错知识图谱环境设计了一种称为置信r-团的关键字查询定义，使其可以返回给用户更合理的关键字查询结果。另一方面，由于计算置信r-团中的r-团置信度是#P-难的，因此提出了一种过滤-验证算法框架来高效地解决该问题。在过滤步骤中，计算出置信r-团的候选结构和置信度上界，并设计出一种适应于大数据环境的索引，将没有机会出现在结果集中的结点和边进行剪枝。大量的基于真实数据集的实验证明，本文所提出的置信r-团定义所返回的结果比直接将传统关键字查询定义应用到容错知识图谱中所返回的结果更能令用户满意，且所提出的算法具有高效性。 (4)基于事件的社交网络上事件参与规划查询。考虑在实际应用中二分图匹配结合了时空信息的情况，提出一种为基于事件的社交网络平台上的用户制定个性化参与其感兴趣的事件的规划查询问题。然而现有的技术要么忽略了参加每个事件的最少人数需求条件，要么假设所有的事件一旦发布，任何信息都不能被改变。这些假设在现实生活中均难以实现。为此，本文提出了一个复杂事件规划(GEPC)问题及其动态变种(IEP)问题，并证明这两个问题都是NP-难的。因而，提出了带误差界保障的近似算法来解决这些问题。大量基于真实数据集的实验证明了本文所提出算法的有效性和高效性。 本文的研究工作为不同环境下的用户对图数据查询处理的具体需求提供了新的解决方案，为图数据查询处理技术提供了新的视角供研究者们参考。

目录

声明

摘要

第1章绪论

1．1研究背景及意义

1．2相关技术及研究成果

1．2．1传统图数据上的查询处理

1．2．2不确定图上的查询处理

1．2．3分布式环境下图数据的查询处理

1．2．4新型图数据应用上的查询处理

1．3本文的研究内容和主要贡献

1．4本文的组织结构

第2章关联不确定图上最短路径查询处理

2．1问题背景

2．2关联不确定图模型及问题描述

2．3过滤-验证算法框架

2．4过滤步骤

2．4．1索引过滤机制

2．4．2索引过滤算法的实现

2．4．3索引的构建方法

2．5验证步骤

2．6实验评估

2．6．1实验环境及数据集

2．6．2过滤步骤评估

2．6．3验证步骤评估

2．6．4查询的总体评估

2．7本章小结

第3章分布式不确定图上的可达查询处理

3．1问题背景

3．2问题描述

3．3分布式图简化及图确认算法框架

3．3．1分布式图简化

3．3．2分布式确认

3．4实验评估

3．4．1实验环境及数据集

3．4．2实验结果及分析

3．4．3实验分析总结

3．5本章小结

第4章容错知识图谱上的关键字查询处理

4．1问题背景

4．2问题描述

4．3索引过滤步骤

4．3．1结构过滤

4．3．2置信度过滤

4．4验证步骤

4．5实验评估

4．5．1实验环境及数据集

4．5．2查询定义的有效性

4．5．3查询算法的高效性

4．6本章小结

第5章基于事件的社交网络上事件参与规划查询处理

5．1问题背景

5．2问题描述

5．2．1复杂事件规划问题

5．2．2增量事件规划问题

5．3复杂事件规划问题的解决方案

5．3．1基于GAP的近似算法

5．3．2基于贪心的算法

5．4增量事件规划问题的解决方案

5．4．1事件参与者人数上界降低

5．4．2事件参与者人数下界提高

5．4．3事件举办时间改变

5．5实验评估

5．5．1实验环境及数据集

5．5．2复杂事件规划问题的实验结果

5．5．3增量事件规划问题的实验结果

5．6本章小结

第6章结束语

6．1本文工作总结

6．2未来的研究方向

参考文献

致谢

攻博期间发表的论文

攻博期间参与的项目

作者简介