学位论文简介
随着信息化时代的到来，图数据的规模得到了极大的增长。图数据结构在许多实际应用的模型构建中都起到关键作用，如何从大规模图数据中挖掘有效信息成为一个广受关注的研究问题。作为图数据理论中的经典问题，图的路径查询广泛应用在社交网络、道路网络等实际应用中，是计算机科学、地理信息科学和交通运输等领域的研究热点。现有路径查询技术大都是集中式算法，逐渐难以满足查询性能上的需求，因此亟需设计分布式并行化的高效算法。为了满足查询效率的需求以及优化用户的实际体验，本文重点研究了不同类型的图数据中的路径搜索问题，包括：基于简单图的集合可达性查询、基于标签图的标签约束集合可达性查询、以及简单图中的基于跳数约束的路径枚举。本文的主要工作和创新点如下：
(1) 针对简单图中的集合可达性查询，首先提出了一种多层索引(multi-level 2-hop，ML2hop)的方法。通过在分区内部和分区之间构建索引来辅助优化查询任务的计算开销和通信开销。然后，设计了一种基于该索引的查询算法，在不影响查询准确率的前提上，通过限制查询过程中的迭代次数来优化时间开销和通信开销。最后，提出了一种索引维护算法来对ML2hop进行动态更新，使该索引也能有效地扩展至动态图处理。
(2) 针对标签图中的集合可达性查询，首先提出了一种基于边界图(boundary graph-based index，BoundG)的索引结构来保证不同分区之间顶点对的连通性。基于松弛化的连接结构和预先计算的辅助结构，BoundG的构建效率能够得到极大的提高。为了进一步提升查询效率，提出了一种两层索引(two layer 2-hop index，TL2hop)的方法用于优化计算成本和通信开销，并且设计了一种适用于多标签图的索引构建算法来保证索引的完备性和最小性。此外，设计了一种基于TL2hop的双向查询算法来提高查询效率。
(3) 针对路径枚举问题所存在的搜索范围极大，冗余计算较多等挑战，首先提出了一个基于查询任务的重构图结构，并且从理论上证明了查询任务的搜索空间的上限。然后提出了一种基于并行dfs的方法(PDFS)，通过高效的任务分解策略和剪枝策略来并行的枚举所有的简单路径，且不会产生重复的结果。此外，为了进一步减小由于共享子路径遍历所产生的时间开销，设计了一种基于并行连接的方法(PJOIN)，并在大规模搜索空间的查询任务上取得了更好的查询性能。
主要学术成果
Yuanyuan Zeng, Wangdong Yang, Xu Zhou, Guoqing Xiao, Yunjun Gao, Kenli Li. Distributed Set Label-Constrained Reachability Queries over Billion-Scale Graphs [C]. IEEE International Conference on Data Engineering, 2022. (第一作者，CCF 推荐 A 类会议)
Yuanyuan Zeng, Kenli Li, Xu Zhou, Wensheng Luo, Yunjun Gao. An Efficient Index-based Approach to Distributed Set Reachability on Small-World Graphs [J]. IEEE Transactions on Parallel and Distributed Systems, 2022. (第一作者，CCF 推荐 A 类期刊)
Yuanyuan Zeng, Yangfan Li, Xu Zhou, Jianye Yang, Wenjun Jiang, Kenli Li. Efficient game theoretic approach to dynamic graph partitioning [J]. Information Science, 2022. (第一作者，SCI 二区)
Peiying Lin, Yangfan Li, Wensheng Luo, Xu Zhou, Yuanyuan Zeng, Kenli Li, Keqin Li. Personalized query techniques in graphs: A survey [J]. Information Science, 2022. (第五作者，SCI 二区)
黄阳, 周旭, 杨志邦, 余婷, 张吉, 曾源远, 李肯立. 基于缓存的时变道路网最短路径查询算法 [J]. 计算机研究与发展, 2022. (第六作者，CCF 推荐 A 类中文期刊)
