【摘 要】
:
随着云计算等新技术的快速发展、社交网络等新型互联网应用的兴起,人类获取和存储数据的规模正以前所未有的速度爆炸式增长,与大规模图数据相关的技术变革成为学术界和工业界
论文部分内容阅读
随着云计算等新技术的快速发展、社交网络等新型互联网应用的兴起,人类获取和存储数据的规模正以前所未有的速度爆炸式增长,与大规模图数据相关的技术变革成为学术界和工业界的热点问题。针对大规模图数据的可达查询是一项基础性查询,在图分析及处理中被频繁使用,将一些复杂的查询分解成包含多个可达查询的操作集合,其高效处理具有重要意义。现有的可达索引机制在面对大规模图时呈现查询效率低或索引代价过大的问题,为此,本文对大规模有向图的可达查询进行了深入的研究。首先,提出了一种基于NoSQL的面向大规模图数据的分布式可达性索引与查询框架,在不破坏原图中节点可达性的前提下,将大规模图进行划分成若干个子图作为预处理,通过创建跨边集来保留原图中各子图间的可达性信息。由于子图可达性保持算法保留原图中各子图内节点间的可达性信息,从而使各子图可并行生成可达性索引。其次,设计了基于所提框架的查询处理算法。算法预先判断查询节点所属子图的可达性信息,可直接返回一部分不可达结果。对于一般查询,最多进行两次子图内部的可达性查询即可返回查询结果。最后,通过真实数据集的实验与现有方法对比,验证了本文提出的基于NoSQL的面向大规模图数据的分布式可达性索引与查询框架在大规模稀疏图和稠密图上创建索引所需的时间短,生成的索引规模小,且具有良好的查询性能。
其他文献
图G的一个k-无圈边染色是满足任意两种颜色类的导出子图是森林的G的一个k-正常边染色,G的无圈边色数是使G存在无圈边染色最少的颜色数,记为a’(G).G的一个k-孪生边染色σ是指
除海洋外,陆地表面是气候系统中的另一重要下边界,对大气和气候变化也有着显著的影响。许多研究表明前期陆地下垫面状态异常尤其是地表水状态(土壤湿度及雪盖)异常与后期天气
随着网络技术的发展,到了今天,复杂网络已随处可见。而在实际的复杂网络中,最多见的就是无标度网络。无标度网络由于其自身的演化过程造成其拓扑结构有一定的特殊性。在网络
本学位论文主要对带有时滞脉冲的混杂随机微分系统的指数稳定性与脉冲镇定性展开研究,基于平均脉冲区间方法,Lyapunov函数,Razuminkhin型方法以及一些随机分析的技巧研究了带
为攻克四色猜想,Tutte在1954年提出了整数流理论.此后,整数流理论成为图论一个重要的研究分支.上世纪五十年代,Tutte证明了普通图存在处处非零的k-流当且仅当它存在处处非零
在许多实际研究中,由于一些客观条件,实验观测到的数据往往是缺失的,只知道研究对象的失效时间大于或者等于某个时间,或者在某段时间之间,这样不完整的数据在生存分析中叫做
趋磁细菌能在细胞内合成有生物膜包被的、纳米尺寸、单磁畴的磁铁矿(Fe3O4)或胶黄铁矿(Fe3S4)晶体颗粒,也叫磁小体。它是迄今发现的唯一能利用地磁场定向的原核微生物,是研究
互联网时代的到来及信息科技的高速发展,产生出各种大规模在线网络,这些网络的出现推动了复杂网络的研究。从蛋白质关系网络、科学家论文合作网络到微博关系网络、商品推荐网
计算机视觉是指对动物和人类的视觉形成机制进行模拟,对场景的图像信息处理与分析。随着计算机技术的快速进步,以及人工智能和模式识别等领域研究的不断深入,使得计算机视觉
随着真实世界的复杂网络规模变大,对于网络全局信息很难把握,一些经典的社团发现方法的时间复杂度也随之变高。因此,一种基于网络局部信息的局部社团发现方法被提出来。局部