检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

标签约束图上的k步可达性查询

计算机科学 2022年第12期49卷 283-292页

作者：杜明邢瑞萍周军锋谭玉婷东华大学计算机科学与技术学院上海201620

标签约束图上的k步可达性查询问题,回答了在一个标签约束图上两点之间是否存在一条长度不大于k的路径并且这条路径上的标签都在用户给定的标签集中的问题。标签约束图上的k步可达性查询问题在现实中有着广泛的应用,然而现有算法无法直... 详细信息

标签约束图上的k步可达性查询问题,回答了在一个标签约束图上两点之间是否存在一条长度不大于k的路径并且这条路径上的标签都在用户给定的标签集中的问题。标签约束图上的k步可达性查询问题在现实中有着广泛的应用,然而现有算法无法直接回答这个问题。因此,首先提出Lk2H算法。Lk2H算法主要包括构建索引和查询两个步骤。第一步是给图上的所有顶点构建一组包含k和标签信息的2-Hop索引,第二步是基于构建好的索引进行查询。在查询时,为了尽可能地为用户返回更多的信息,Lk2H算法优化了一类不可达查询的返回结果:当用户无法明确所有的标签类型,不能给出完整的标签约束,进而导致查询结果为不可达时,将完整的标签集返回给用户。其次,提出优化算法Lk2H+。Lk2H+算法通过构建部分顶点的2-Hop索引进一步缩减索引大小和索引的构建时间,并基于构建好的索引进行查询。查询时,需要对顶点按照是否构建了索引进行分类讨论。最后,基于15个真实数据集进行测试。实验结果表明,Lk2H算法和Lk2H+算法都可以高效地解决标签约束图上的k步可达性查询问题。

关键词：标签约束图 k步可达性查询 2-Hop索引顶点覆盖图论

在线全文

学校读者我要写书评

暂无评论

一种适用于大图的k步可达性查询算法

计算机科学 2024年第S1期51卷 651-660页

作者：同正南卜天明华东师范大学软件工程学院上海200062

k步可达查询用于在给定的有向无环图(Directed Acyclic Graph,DAG)中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出了一种构建在大图上的基于树覆盖的倍增索引来提高索引查询效率,并结... 详细信息

k步可达查询用于在给定的有向无环图(Directed Acyclic Graph,DAG)中回答两点之间是否存在长度不超过k的路径。针对现有方法的索引规模大、查询处理效率低的问题,提出了一种构建在大图上的基于树覆盖的倍增索引来提高索引查询效率,并结合GRAIL算法和改进的FELINE算法对本身就不可达查询点对进行剪枝。基于19个真实的数据集进行了实验测试,并将所提算法与现有算法在构建索引大小、索引时间、查询时间3个指标上进行了实验对比。实验结果验证了所提算法的高效性。

关键词： k步可达性查询倍增索引索引标签树覆盖在线搜索

在线全文

学校读者我要写书评

暂无评论

基于双向双区间标签实现k步可达性查询

计算机科学 2018年第3期45卷 178-181页

作者：宋亚青武优西刘靖宇李艳河北工业大学计算机科学与软件学院天津300401 河北省大数据重点实验室天津300401 河北工业大学经济管理学院天津300401

近年来,图的可达性查询已经成为一个研究热点。传统的可达性查询算法——GRAIL在处理k步可达性查询时具有较高的查询效率,但不适合处理不同分支顶点之间的k步可达性查询。为了解决上述问题,提出了一种新的双向双区间标签索引,进而实现了... 详细信息

近年来,图的可达性查询已经成为一个研究热点。传统的可达性查询算法——GRAIL在处理k步可达性查询时具有较高的查询效率,但不适合处理不同分支顶点之间的k步可达性查询。为了解决上述问题,提出了一种新的双向双区间标签索引,进而实现了RE-GRAIL算法,从而有效解决了k步可达性查询问题。最后,在5个不同特征的数据集上进行实验,并从索引构建时间、索引大小、查询时间、扩展性4个方面进行验证。实验结果表明,与众多同类算法相比,RE-GRAIL算法具有更好的性能。

关键词： k步可达性查询不同分支双向双区间

在线全文

学校读者我要写书评

暂无评论

标签约束图上的k步可达性查询处理研究

标签约束图上的k步可达性查询处理研究

作者：邢瑞萍东华大学

学位级别：硕士

可达性查询是图数据处理中的一个基本操作,在现实生活中有着广泛的应用。给定有向图中的一个源顶点u和一个目标顶点v,传统的可达性查询用于回答是否存在一条路径,使得顶点u能够到达顶点v。实际应用中,图的边上可能会标注特定信息,同时... 详细信息

可达性查询是图数据处理中的一个基本操作,在现实生活中有着广泛的应用。给定有向图中的一个源顶点u和一个目标顶点v,传统的可达性查询用于回答是否存在一条路径,使得顶点u能够到达顶点v。实际应用中,图的边上可能会标注特定信息,同时节点之间的联系路径也有长短之分,用户通常需要查询的是能满足标签约束和长度约束的结果（LCkR查询）。LCkR查询在社交网络、金融网络、知识图谱中有着广泛的应用,但现有算法无法处理LCkR查询问题。本文对LCkR查询进行了深入研究,具体研究内容如下。首先,提出Lk2H算法来回答LCkR查询。Lk2H算法的基本思想是对图中顶点预先构建标签索引,用于保存顶点之间的最短路径信息,从而加速查询处理。Lk2H算法包括索引构建和查询处理两个部分。在索引构建时,通过双向剪枝BFS对所有顶点构建包含长度和标签信息的2-Hop索引。查询时,通过比较源点和目标点的标签索引来得到查询结果。同时,优化了返回结果,即当结果判定为不可达时,会明确到底是什么原因导致的不可达,并根据不同情况返回不同信息。其次,提出了优化算法Lk2H+来进一步减小构建索引的时间和索引大小。Lk2H+算法的基本思想是在图中选取部分顶点构建索引。查询时,如果查询顶点构建了索引,则直接基于索引回答查询,否则需要遍历数据图。为了降低遍历数据图的代价,Lk2H+算法选取最小顶点覆盖集中的顶点来构建索引。最后,以索引大小、索引构建时间以及查询响应时间为指标,基于15个真实数据集对本文所提出的两个算法的性能进行测试。实验结果表明,Lk2H算法和Lk2H+算法可以高效回答标签约束图上的k步可达性查询问题。

关键词：标签约束图 k步可达性查询 2-Hop标签索引图论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于图数据的k步可达性查询处理研究

基于图数据的k步可达性查询处理研究

作者：费春苹燕山大学

学位级别：硕士

k步可达性查询问题是图数据管理中的热点问题之一,可以应用到现实生活中的很多领域,包括无线传感器网络、互联网、电信网及社交网络等。k步可达性查询能够体现顶点的影响力,因而在许多实际应用中,可以为用户提供比可达性查询更多的信息... 详细信息

k步可达性查询问题是图数据管理中的热点问题之一,可以应用到现实生活中的很多领域,包括无线传感器网络、互联网、电信网及社交网络等。k步可达性查询能够体现顶点的影响力,因而在许多实际应用中,可以为用户提供比可达性查询更多的信息。本文从以下几个方面对基于图数据的k步可达性查询处理方法进行研究,具体研究内容如下。首先,通过对现有算法进行分析,发现现有算法要么低效、要么索引规模庞大。其次,提出一种基于双向搜索的BIRCH算法,该算法采用双向搜索策略和区间标签索引来进行判断,当判断顶点u是否满足在k步之内可达顶点v时,首先比较u的出度和v的入度,优先处理度小的顶点,其优点体现在使用较小的索引,同时避免由于u的出度过大所带来的效率下降问题。再次,提出基于双向广度层数、双向拓扑层数和双向区间索引的剪枝策略来辅助过滤,并设计了相应的BIRCH-BL、BIRCH-BTL和RE-BIRCH-BTL算法。算法在处理图中的查询顶点对时,利用剪枝策略来进行剪枝,减少需要访问的顶点数量,从而提高查询效率。最后,基于19个真实的数据集进行测试,实验结果从索引构建时间、索引大小、查询响应时间、处理顶点数量以及扩展性方面验证了本文方法相对于现有方法的高效性。

关键词： k步可达性查询双向搜索广度层数拓扑层数

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

大图上的k步可达性查询算法研究

大图上的k步可达性查询算法研究

作者：同正南华东师范大学

学位级别：硕士

可达性查询已经应用于有向无环图网络中的多个地方,例如社交网络、XML文档结构、生物网络分析、代谢网络、引用网络、传感器网络、数据库术语关系等多个领域。可达性查询是指给定任意两点u和v,回答节点u是否可达节点v。而k步可达性查询... 详细信息

可达性查询已经应用于有向无环图网络中的多个地方,例如社交网络、XML文档结构、生物网络分析、代谢网络、引用网络、传感器网络、数据库术语关系等多个领域。可达性查询是指给定任意两点u和v,回答节点u是否可达节点v。而k步可达性查询是指对于任意两点回答节点u是否可在k步以内到达节点v。针对于现有k步可达性查询算法在大图上构建索引规模过大,创建的索引不能对任意k值具有一般适用性,且查询效率一般等问题。本文提出了一个新的k步可达性查询算法。本文的主要贡献如下:(1)提出在原有向无环图上构建最短路径森林,在最短路径树上构建自适应k值的倍增索引,在此基础上设计出基于倍增索引的k步可达性查询算法,并分析了查询算法的正确性和时间复杂性,成功将k步可达性问题扩展至大图。(2)针对高密度节点构建动态索引,提高了对于关注度较高的高密度查询点对的查询性能,在经典伸展树基础上扩展出基于双关键字伸展的动态索引表,并提出了针对动态索引的查找、更新算法。(3)最后在19个真实的数据集上和已有算法进行比较,验证了倍增索引在索引构造时间、索引大小、查询时间上的高效性,动态索引在应对高密度点对查询的高效性。

关键词： k步可达性查询标签索引动态规划倍增索引动态索引

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图数据上k步可达性查询关键技术研究

图数据上k步可达性查询关键技术研究

作者：宋亚青河北工业大学

学位级别：硕士

随着大数据时代的来临,数据规模呈指数级速度增长,越来越多的复杂结构数据需要用图数据结构模型来表示。即点代表事物,边代表事物之间的关系。在现实生活中,图数据模型有着十分广泛的应用前景,其中包括:社交网络、蛋白质交互网络、交通... 详细信息

随着大数据时代的来临,数据规模呈指数级速度增长,越来越多的复杂结构数据需要用图数据结构模型来表示。即点代表事物,边代表事物之间的关系。在现实生活中,图数据模型有着十分广泛的应用前景,其中包括:社交网络、蛋白质交互网络、交通网络等,因此如何高效而快速地检索大图数据成为近几年来研究的热点。可达性查询是图查询中一个主要的研究方向。然而,实际应用中,和传统的可达性查询相比,k步可达性查询可以为用户提供更多的有用信息,因此k步可达性查询问题成为图数据管理中的热点问题之一。本文从以下几个方面对k步可达性查询的处理方法进行了研究,具体研究内容如下:首先,对现有k步可达性查询算法进行了详细分析,发现现有方法在处理k步可达性查询时,存在大量冗余顶点对的重复判断现象。其次,在BiRch-BTL算法的单向双区间标签和四种剪枝策略的基础上提出了新的查询方法——基于哈希表的单向搜索算法(A unidirectional search algorithm based on hash table,UniRch-Hash),该算法采用哈希表来存放已经判断过的不可达顶点对和相应的步数,防止对不可达顶点对造成重复判断,从而提高了算法的性能和系统的响应速度。再次,经研究发现UniRch-Hash算法存在一些不足,即该算法不适合处理不同分支顶点之间的k步可达性查询,为了解决上述问题,本文接着提出了一种双向双区间标签索引,RE-UniRch-Hash算法就是在新的区间标签索引的基础上实现的。最后,在20个不同特征的数据集上进行实验,并从索引构建时间、索引大小、查询时间、访问顶点数量、哈希表占用空间大小和扩展性等多方面进行验证,实验结果表明,UniRch-Hash算法和RE-UniRch-Hash算法都优于现有的多种算法。

关键词： k步可达性查询重复判断哈希表单向搜索不可达顶点对

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

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

网络安全技术与应用 2017年第1期 54-54,57页

作者：宋亚青河北工业大学计算机科学与软件学院天津300401

随着大数据时代的来临,数据规模呈指数级速度增长,越来越多的复杂结构数据需要用图数据结构模型来表示。如何高效而快速地检索大图数据成为研究的热点。现阶段,大部分k步可达性查询都是通过构建索引来实现的。研究发现,构建索引的时间... 详细信息

随着大数据时代的来临,数据规模呈指数级速度增长,越来越多的复杂结构数据需要用图数据结构模型来表示。如何高效而快速地检索大图数据成为研究的热点。现阶段,大部分k步可达性查询都是通过构建索引来实现的。研究发现,构建索引的时间、空间消耗和查询时间之间存在瓶颈,如何合理地构建索引成为研究的热点问题。

关键词：图数据 k步可达性查询索引

在线全文

学校读者我要写书评

暂无评论

基于参考节点嵌入的图可达性查询

计算机应用 2016年第7期36卷 1998-2005,2045页

作者：温菊屏胡小生林冬梅曾亚光佛山科学技术学院电子与信息工程学院广东佛山528000 佛山市计算机学会广东佛山528000 佛山科学技术学院信息与教育技术中心广东佛山528000

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树... 详细信息

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、k-Reach算法进行实验对比测试。相较于k-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明:所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。

关键词： k步可达性查询带距离约束的图可达性查询参考节点嵌入三角不等式关系最短路径树