巨量标记图数据查询的大规模并行处理方法研究

Labeled graph is a common model for social networks, publication networks and knowledge graphs etc. Now, the volume of labeled graph is very big and still growing. Modern computer has massive parallel processors and is more powerful than ever. Thus, it exposes a choice to process huge scale labeled graph with modern hardware instead of distributed systems. However, the key to massively parallel processing queries on huge scale labeled graph is to fully take advantage of massively parallel processors while enhance the neighborhood among data and organizing them well because irregular data flow will induce memory wall and communication wall. However, to achieve the goals, current partitioning and placing approaches, parallel processing framework and query plan generator face challenges. For example, Partitioning approaches should switch their focuses from redundancy and semantic integrity to locality. And, the query plan generator should generate massive plans with fine grained tasks instead of deep and narrow plans with coarse grained tasks. Motivated by this, our proposal investigates the following research issues. (1) We study the hypergraph model for labeled graph, the definition of semantic clique, semantic clique based partitioning and placing approaches and measures to evaluate the approach. The goal is to reduce extensive data access, improve locality. (2) We study semantic clique based parallel processing model and scheduling strategies with modern hardware for query execution tasks. So, tasks are executed efficiently and data flows smoothly. (3) We explore the approach to generate massive query plan with fine grained tasks and optimized technologies for complex queries, such as theta join and update on labeled graph. The goal is to assign tasks evenly and optimize the data flow among tasks. Along with these research issues, we will design a prototype system. Research findings from this project will be significant to promote research and development of emerging applications and enhance the technology advancement in massive Web data management.

标记图是社会网络、文献网络及知识图谱等网络图的共同基础模型。标记图规模庞大且在持续增长。具有大规模并行处理器的现代计算机为处理巨规模标记图查询提供了一种新选择。然而高效处理巨规模标记图查询的重要基础是在充分利用大规模处理器的同时规范数据的传输，提高局部性。对此，首先研究标记图的超图模型、语义簇的构成及基于语义簇的划分及放置方法和评价指标，提高数据的邻近性，减少大范围的访问，提高局部性。其次，研究基于语义簇的查询并行处理模型，以及适应大规模并行处理器结构特征的任务调度方法，为标记图查询的大规模并行处理提供保障。在此基础上，研究生成大规模细粒度高并行查询计划的方法，并针对复杂查询，如theta join和更新等研究优化方法，以合理分配任务，优化数据标记图数据传输。本项目研究所形成的有关标记图数据划分和放置方法、查询并行处理模型及细粒度大规模并行查询计划的生成方法等将为Web大数据处理提供支持

标记图是社会网络、文献网络及知识图谱等网络图的共同基础模型。标记图规模庞大且在持续增长。具有大规模并行处理器的现代计算机为处理巨规模标记图查询提供了一种新选择。然而高效处理巨规模标记图查询的重要基础是在充分利用大规模处理器的同时规范数据的传输，提高局部性。对此，首先研发了并行图存储系统ParTriple，该系统能存储具有多种数据类型的标记图数据，同时支持高效的图数据更新。其次，ParTriple提出了一种基于语义簇的多级数据并行计算模型。该并行计算模型充分发掘了算子内并行和算子间并行。第三，为查询的流水线处理生成一个DAG形状的计划，这样每一流水线不需要频繁与其他流水线同步，从而快速执行查询并有效地减少中间结果的大小。第四，提出了一种无锁并发任务调度机制，该机制利用循环三端队列的工作窃取机制和基于窗口的任务批量执行来最大化任务处理的并行性。最后，对于复杂的查询，我们提出了一种多维图标记方法（称为MGTag）来支持快速可达性查询处理。在合成数据集和真实数据集上的大量实验表明，我们的方法比现有的解决方案具有更高的性能。