基于大规模图数据k步可达性索引技术研究现状.pdf

《基于大规模图数据k步可达性索引技术研究现状.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、安全模型、算法与编程基于大规模图数据k步可达性索引技术研究现状◆宋亚青（河北工业大学计算机科学与软件学院天津300401）摘要:随着大数据时代的来临，数据规模呈指数级速度增长，越来越多的复杂结构数据需要用图数据结构模型来表示。如何高效而快速地检索大图数据成为研究的热点。现阶段，大部分k步可达性查询都是通过构建索引来实现的。研究发现，构建索引的时间、空间消耗和查询时间之间存在瓶颈，如何合理地构建索引成为研究的热点问题。关键词:图数据;k步可达性查询;索引0前言k步可达性查询问题。随着互联网技术的高速发展，大量数据

2、每天不断涌现，“大深度优先搜索算法的核心思想是：判断顶点u到顶点v是否数据”这个名词已经逐步融入我们的日常生活，伴随着海量数据k步可达，从u出发，访问u的任意一个未被访问过的邻接点v0，[1]出现的是数据结构的多样化。图做为一种特殊的数据结构，在即判断顶点v0是否k-1步可达顶点v，此时需要遍历v0的任意一处理大规模数据的时候有着广泛的应用。由于往日研究的可达性个未被访问过的邻接点，依次类推，直至走完k步为止，若一直查询存在着很大的局限性，因此能够为用户提供更多信息的k步没有判断出结果，则回溯到上一个访问过的顶

3、点，对该顶点未访[2]可达性查询将成为研究的重点和难点问题。在许多实际问题中，问过的其他邻接点继续进行遍历，直至遍历完所有邻接点为止。[3]k步可达性查询具有更加重要的研究意义。所有的查询都是通若中途，判断出顶点u是k步可达顶点v的，则直接返回;否则过构建索引来实现的。研究发现，构建索引的时间、空间消耗和要遍历与顶点u相连接长度为k的所有路径。查询时间之间存在瓶颈。但是随着科学技术的进步，计算机的配广度优先搜索算法的核心思想是：判断顶点u到顶点v是否置变得越来越高，存储容量也变得越来越大，空间消耗不再是制k步可

4、达，需要访问和顶点u相连接的所有邻接点qi，然后从这约算法查询效率的首要考虑因素，因此本着空间换取时间的原些邻接点qi出发，依次判断qi是否k-1步可达顶点v，重复上述则，通过创建索引可以有效地提高算法的查询效率，下面主要介操作，直至遍历完所有邻接点。若中途，判断出顶点u是k步可绍了5类基于不同索引的查询算法。达顶点v的，则直接返回;否则需要遍历完与顶点u相连接的长1索引介绍度为k的所有路径。现阶段k步可达性查询研究中的查询方法主要包括：基于图1.2基于区间标签的查询方法遍历的查询方法、基于区间标签的查询方法、

5、基于最短路径的该类查询算法主要包括GRAIL、GRIPP和PathTree，典型算查询方法、基于k步索引的查询方法、基于双向搜索的查询方法是2010年Jin等人提出的GRAIL索引方法，该方法的基本思法。其中第一类方法不需要构建索引来实现，后四种算法是基想是:为了降低判断过程中的误判率，该算法按照从左到右和从于构建的索引实现的。右到左两种不同的深度优先遍历方式为每个顶点w构建双区间121.1基于图遍历的查询方法标签，记为Lw和Lw。给定有向无环图G，判断u→kv是否成立，122图的遍历指的是从图中某一顶点出

6、发访问遍图中其余所有只有满足条件（Lv1Lu）（LvLu）时，则得出结论顶点u顶点，且使每一个顶点仅被访问一次，通常有两条遍历图的路径：不可达顶点v，对于所有没有通过区间标签判断出可达性的顶深度优先搜索和广度优先搜索。基于这两种遍历方式，可以解决（下转第57页）（上接第53页）[3]PirrettiM,TraynorP,McdanielP,etal.Secureattribute-本文针对云存储数据访问控制问题,在CP-ABE加密策略基basedsystems[C]//ACMConferenceonCompu

7、terandCom础下融合信任管理机制，将信任级属性嵌入访问结构中,通过实时municationsSecurity,CCS2006，Alexandria,Va，Usa，Ioctober监控用户行为来实现访问控制。在安全方面，信任级属性主导用30–November,2006.户权限，信任值取决于用户行为,而用户行为被系统实时监控,一[4]LiS，FuJ.Userrevocationfordatasharingbasedonb旦触发信任级访问条件立即撤销权限，所以有效的制止了非法用roadcastCP-ABEinc

8、loudcomputing[C]//Communications户的违规操作;在开销方面,利用基于信任等级属性的撤销机制，SecurityConference.IET，2014.更加灵活地解决了因属性撤销而频繁更换密钥所导致的巨大计[5]游静，冯辉，孙玉强.云环境下基于协同推荐的信任评算开销，实验结果也验证了方案的有效性。下一步工作希望在此估与服务选择[J].计算机科学，2016.基础