基于DAG的可达性查询算法研究

发布时间：2020-12-31 13:32

　　有向无环图(DAG)的可达性查询处理是图数据管理中的热点问题之一,可以应用到现实生活中的很多领域,包括语义网、互联网、电信网、无线传感网络、社交网络及生物信息网等。可达性查询就是在有向无环图G上,给定任意的2个结点u和v,回答u是否能够到达v。通过分析现有可达性查询算法,发现已有的算法构建索引的时间较长,查询效率低。本文主要从以上2个方面对可达性查询处理进行研究,研究内容如下。首先,提出基于影子定位的索引构建算法SP。SP算法基于区间扩展策略为每个结点设定标签。给定需要处理的n个结点,不同于以往算法需要多次的遍历才能完成当前结点的处理,SP算法基于影子定位技术,将待处理结点分别存放在待处理栈和待扫描链表中,待处理栈中每个结点记录了其在待扫描链表中的位置,从而将已有方法的O(logn)搜索代价降低为O(1)代价,加速了索引构建的效率。其次,提出双向编码方案和基于巨大结点的剪枝策略来提升查询处理的效率。通过正向和反向进行编码,为每个结点指定相应的索引标签,增强了区间过滤的能力。为了进一步的增强可达查询的处理能力,提出巨大结点的位标签过滤策略。该策略选取k个度最大的hop结点,根据每个结点与... 

【文章来源】：燕山大学河北省

【文章页数】：70 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 研究背景
    1.2 研究现状
    1.3 本文研究内容
    1.4 本文组织结构
第2章 基础知识概述
    2.1 相关数据结构及其定义
    2.2 可达性查询的基本知识
    2.3 可达性查询的相关算法
        2.3.1 Label-Only类可达性算法
        2.3.2 Label+G类可达性算法
    2.4 本章小结
第3章 基于影子定位索引构建算法SP
    3.1 问题分析
    3.2 SP基本思想
    3.3 算法描述
        3.3.1 索引构建
        3.3.2 查询处理
    3.4 本章小结
+">第4章 高效可达性查询算法IERch+

    4.1 问题分析
    4.2 高效可达性查询索引的生成
        4.2.1 双向编码方案
        4.2.2 基于巨大结点的剪枝策略
        4.2.3 查询处理
    4.3 本章小结
第5章 实验分析
    5.1 实验简介
    5.2 数据集
    5.3 评价指标
+可达性查询算法性能分析">    5.4 IERch⁺可达性查询算法性能分析
        5.4.1 Label+G类算法性能比较分析
        5.4.2 区间扩展类算法性能比较分析
    5.5 本章小结
结论
参考文献
攻读硕士学位期间承担的科研任务与主要成果
致谢



本文编号：2949692

suoshi