基于索引的大规模动态图窗口查询研究

摘要

当前，社交网络等领域存在着个体联系形成的网络图，这些图数据有很重要的价值。随着个体之间联系的改变会产生动态图，动态图窗口查询是分析动态图的一种重要方法。已有的研究主要是对动态图窗口建立索引，而现有的索引方法还存在着查询效率和更新效率待提高等问题。同时，动态图的规模越来越大，对索引的构建提出了很大的挑战。为了进一步提高查询效率和索引更新效率，对大规模动态图窗口查询的索引问题进行研究很有必要和意义。
　　针对已有的图窗口索引存在查询效率不高的问题，设计了一种大规模动态图窗口的分层索引，通过构建两层索引来提高图窗口查询之间的计算共享率，提高查询效率，并设计支持大规模动态图的图窗口查询系统；针对索引构建效率问题，利用索引构建的不同阶段内存在相互独立数据的计算，设计并行构建分层索引方法；针对索引更新效率问题，通过设计不同更新类型的规则，设计索引的增量更新方法，保证索引更新的正确和提高索引更新的效率。
　　最后，对大规模动态图窗口查询系统进行功能实验和性能实验分析。实验表明，本文设计的分层索引，支持大规模动态图的高效图窗口查询，在查询效率上相对于已有索引有所提高；通过并行构建分层索引方法，提高了分层索引的构建效率，通过增量更新索引方法，提高了索引更新效率。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景

1.2 国内外概况

1.3 本文研究的主要内容

2 大规模动态图窗口查询系统总体结构

2.1 设计目标

2.2 总体结构

2.3 主要模块介绍

2.4 小结

3 大规模动态图窗口查询的索引问题研究

3.1 相关定义描述

3.2 大规模动态图窗口索引优化目标

3.3 分层索引

3.4 基于分层索引的查询

3.5 分层索引构建方法

3.6 分层索引更新

3.7 与已有索引方法对比

3.8 小结

4 实验与结果分析

4.1 实验环境及数据来源

4.2 分层索引功能实验

4.3 分层索引性能实验

4.4 小结

5 总结与展望

5.1 全文总结

5.2 研究展望

致谢

参考文献