检索结果-南通市图书馆

一种基于悬挂顶点关联索引的最短路径查询算法

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

燕山大学学报 2018年第3期42卷 265-271页

作者：陈伟楼志斌杨清章河北环境工程学院信息工程系河北秦皇岛066102 上海科学院上海201203 燕山大学信息科学与工程学院河北秦皇岛066004

最短路径查询是图数据查询中的热点问题。针对现有的"索引+查询"方法存在的查询效率低下且扩展性差等问题,本文提出了悬挂顶点关联索引策略,即先对度为1的顶点构建顶点关联索引,再对其他顶点构建2-hop标签索引,并依此提出了相应的最短... 详细信息

最短路径查询是图数据查询中的热点问题。针对现有的"索引+查询"方法存在的查询效率低下且扩展性差等问题,本文提出了悬挂顶点关联索引策略,即先对度为1的顶点构建顶点关联索引,再对其他顶点构建2-hop标签索引,并依此提出了相应的最短路径查询算法。本文提出的索引策略降低了索引规模,减少了构建索引时间,使得最短路径查询算法的效率和扩展性得到了改善。最后,通过对11个真实的数据集进行实验,从索引构建时间、索引规模大小、查询时间等方面验证了本文方法的高效性。

关键词：图最短路径查询悬挂顶点顶点关联索引 2-hop标签索引

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

面向大图的最短路径查询算法研究

面向大图的最短路径查询算法研究

作者：王冠宇燕山大学

学位级别：硕士

最短路径查询用于返回图中两点之间的最短路径,是图数据管理中的核心操作之一,一直以来都是研究者关注的热点问题。最短路径查询广泛应用在各种道路交通网络、社会网络、生物信息网络中对数据进行分析。随着实际中数据图规模的不断增大... 详细信息

最短路径查询用于返回图中两点之间的最短路径,是图数据管理中的核心操作之一,一直以来都是研究者关注的热点问题。最短路径查询广泛应用在各种道路交通网络、社会网络、生物信息网络中对数据进行分析。随着实际中数据图规模的不断增大和应用领域的不断扩张,最短路径查询处理效率的进一步提升是亟待解决的关键问题。本文针对无向无权图的最短路径查询问题进行研究,具体研究如下:首先,针对实际中数据图比较稀疏且服从幂律分布的特点,提出对原始图进行分割,分别处理的策略。该策略首先从原始图中删除单枝路径来得到一个规模缩减的图。对单枝路径,利用顶点在路径中的相对位置对顶点进行编码,快速计算路径内顶点间的最短距离。对简化图,构建基于简化图的地标标签索引,用于快速求解简化图上顶点对的最短路径。其次,基于单枝路径索引和简化图索引,提出一种高效的最短路径求解方法。该方法的基本思想是:给定两个查询点,如果这两个点同时位于单枝路径或简化图中,则用相应的单枝路径索引或地标标签索引进行快速求解;否则,先查找两个顶点在简化图上的基点,通过计算基点之间的最短路径,以及基点和查询点的最短路径来得到最终的查询回答结果。最后,利用现实当中的数据集进行检验和验证,从构建标签索引时间和规模,以及查询的响应时间等方面与现有方法做对比,来分析验证本文提出方法的高效性。

关键词：简化图 2-hop标签索引最短路径查询

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

标签约束图上的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标签索引图论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

面向大图的可达性查询算法研究

面向大图的可达性查询算法研究

作者：张海燕燕山大学

学位级别：硕士

可达性查询用于回答在有向图中从给定源点到终点是否存在一条路径。可达性查询处理是图数据处理中的基础操作之一,广泛应用于交通网络、社交网络、模式识别及生物信息网等图数据,支持复杂的数据分析,其查询处理的效率决定了众多图数据... 详细信息

可达性查询用于回答在有向图中从给定源点到终点是否存在一条路径。可达性查询处理是图数据处理中的基础操作之一,广泛应用于交通网络、社交网络、模式识别及生物信息网等图数据,支持复杂的数据分析,其查询处理的效率决定了众多图数据分析操作的效率,是研究者关注的热点问题之一。本文重点研究如何高效处理可达性查询,具体研究内容如下。首先,针对已有2-hop索引回答不可达查询效率低的问题,提出一种高效的可达性查询处理方法(Obstacle Labels,OL)。OL基于妨碍点的概念构建针对妨碍点的2-hop标签。和已有索引方法构建所有顶点的2-hop标签相比,本文提出的基于妨碍点的索引构建方法减少了2-hop标签所占用的空间,可以快速回答妨碍点正反传递闭包范围内顶点之间的可达性。在删除妨碍点的基础上,提出基于互逆的拓扑标签,用于回答妨碍点标签不能处理的查询。其次,针对OL在回答不可达查询时效率较低的问题,提出优化的方法OL+,用于同时高效回答可达和不可达查询。OL+在回答不可达查询时的高效性体现在所提出的既互逆又互补的拓扑标签,因而可以首先通过拓扑标签在常量时间里回答大部分可达和不可达查询。对剩余少量无法通过拓扑标签回答的查询,OL+采用基于妨碍点的2-hop标签进行处理。最后,基于33个真实的数据集进行实验测试,从索引构建时间、索引规模大小、可达性查询时间三个角度对实验结果进行分析,实验结果验证了本文方法查询的高效性。

关键词：可达性查询 2-hop标签索引妨碍点

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

最短路径查询方法研究

最短路径查询方法研究

作者：杨清章燕山大学

学位级别：硕士

最短路径查询是图论研究中的热点问题之一,最短路径查询在很多领域中扮演着最基本也最重要的角色,包括城市交通网络、社交网络、生物信息网络等。目前最短路径查询算法主要有两类,一类是精确最短路径查询,一类是近似最短路径查询,本文... 详细信息

最短路径查询是图论研究中的热点问题之一,最短路径查询在很多领域中扮演着最基本也最重要的角色,包括城市交通网络、社交网络、生物信息网络等。目前最短路径查询算法主要有两类,一类是精确最短路径查询,一类是近似最短路径查询,本文主要研究精确最短路径查询问题。具体研究内容如下。首先,通过对现有算法进行分析,发现现有算法存在构建索引时间长和索引规模庞大所导致的低效性和扩展性问题。其次,在索引构建方面,提出了三种索引构建策略。对度数为1的顶点,构建顶点关联索引;对单枝路径上的顶点,构建路径关联索引;对其他顶点,提出了基于部分顶点进行遍历来构建2-hop标签索引的方法,通过减少冗余数据存储和图的遍历次数,降低了索引规模,减少了构建索引时间。再次,在最短路径查询方面,针对不同的索引构建策略,提出相应的查询策略。对顶点关联索引,利用顶点关联关系和2-hop标签来回答最短路径查询;对路径关联索引,利用路径关联关系和2-hop标签来回答最短路径查询;对部分2-hop标签索引,利用2-hop标签结合图遍历的方式来回答最短路径查询。最后,基于15个真实的数据集进行测试,实验结果从构建索引时间、索引规模大小、查询响应时间等方面验证了本文方法相对于现有方法的高效性。

关键词：最短路径查询顶点关联索引路径关联索引 2-hop标签索引