【摘 要】
：
可达性查询是图数据处理中的一个基本操作,在现实生活中有着广泛的应用。给定有向图中的一个源顶点u和一个目标顶点v,传统的可达性查询用于回答是否存在一条路径,使得顶点u能够到达顶点v。实际应用中,图的边上可能会标注特定信息,同时节点之间的联系路径也有长短之分,用户通常需要查询的是能满足标签约束和长度约束的结果（LCKR查询）。LCKR查询在社交网络、金融网络、知识图谱中有着广泛的应用,但现有算法无法处
论文部分内容阅读
可达性查询是图数据处理中的一个基本操作,在现实生活中有着广泛的应用。给定有向图中的一个源顶点u和一个目标顶点v,传统的可达性查询用于回答是否存在一条路径,使得顶点u能够到达顶点v。实际应用中,图的边上可能会标注特定信息,同时节点之间的联系路径也有长短之分,用户通常需要查询的是能满足标签约束和长度约束的结果（LCKR查询）。LCKR查询在社交网络、金融网络、知识图谱中有着广泛的应用,但现有算法无法处理LCKR查询问题。本文对LCKR查询进行了深入研究,具体研究内容如下。首先,提出LK2H算法来回答LCKR查询。LK2H算法的基本思想是对图中顶点预先构建标签索引,用于保存顶点之间的最短路径信息,从而加速查询处理。LK2H算法包括索引构建和查询处理两个部分。在索引构建时,通过双向剪枝BFS对所有顶点构建包含长度和标签信息的2-Hop索引。查询时,通过比较源点和目标点的标签索引来得到查询结果。同时,优化了返回结果,即当结果判定为不可达时,会明确到底是什么原因导致的不可达,并根据不同情况返回不同信息。其次,提出了优化算法LK2H+来进一步减小构建索引的时间和索引大小。LK2H+算法的基本思想是在图中选取部分顶点构建索引。查询时,如果查询顶点构建了索引,则直接基于索引回答查询,否则需要遍历数据图。为了降低遍历数据图的代价,LK2H+算法选取最小顶点覆盖集中的顶点来构建索引。最后,以索引大小、索引构建时间以及查询响应时间为指标,基于15个真实数据集对本文所提出的两个算法的性能进行测试。实验结果表明,LK2H算法和LK2H+算法可以高效回答标签约束图上的k步可达性查询问题。
其他文献
随着互联网时代的发展,软件技术的应用越来越普遍,对相应软件的漏洞检测要求高效、准确。然而,软件漏洞是多种多样的,通过源代码检测漏洞对开发人员的专业经验要求很高。以往的漏洞检测方案要么依赖专家定义的特征,要么只对代码序列使用递归神经网络,很难在传统的代码空间中提取复杂的漏洞特征。近年来,随着人工智能技术的蓬勃发展,一些学者开始尝试提取源代码的抽象表示图,结合图神经网络用于软件漏洞检测,但目前此类研究
知识图谱是一种重要的存储结构化数据的技术,它可以为多种信息化应用提供知识支持,例如推荐系统、问答系统等。知识图谱自动构建技术的研究在通用文本上开展的如火如荼,而在特定领域上则鲜有人问津。但对于医学、经济、军事等领域,专业的知识图谱是推动其领域信息化发展的关键因素。特定领域的标注文本往往是稀疏的,因此,本文立足于样本稀疏领域这一出发点,对知识图谱自动构建的问题展开研究。知识图谱中结构化知识的一个重要
我国海岸线较长,海上交通制约因素较多且面临日益复杂的政治环境。且我国海上观测资源有限,在这种情况下如何利用有限的不同种类资源,共同解决海上目标搜索问题,对于解决海上搜救、灾害预警、加强我国海上执法能力等许多现实问题都具有重大意义。本文首先对海上目标搜索的问题特点进行分析,然后对各种观测平台的能力、使用约束、适用情况都进行了分析。不同平台都有各自的特点和使用约束,在海上目标搜索问题中扮演了不同的角色
随着全球经济的快速发展,纺织服装行业市场的并驱争先日渐激烈,用户对服装需求的日趋多样化使服装订单的生产要求也随之提升。纺织服装工业互联网平台汇聚了供应链上游众多相同或相近生产能力的服装企业,所接服装订单数量庞大。传统的方式是根据经验对订单进行安排,但这种人工分配方法效率低下,且无法保证分配结果是否能最大化平台利益,因此,如何通过科学手段对这些订单进行合理分配是目前平台面临的一大难题和挑战。目前对于
在近些年人工智能的研究热潮中,深度学习作为其领域下的重要研究方向得到了学术界和工业界的高度关注,并在算法、理论和应用等方面取得了丰富成果。而随着深度学习与业界融合的深入以及相关从事人员的增多,深度学习应用程序和软件系统的研发将会越来越规范化和自动化,如何使用传统软件工程的理论和实践引导这一过程也成为研究热点。相比传统软件,深度学习程序软件对数据有更强的依赖性,当环境中数据的统计属性变化或类别增加时
中药多糖具有抗感染、抗氧化、免疫调节等多种活性，其优势在于毒副作用小、安全性高、功能多样。多糖通过炎症反应通路、神经递质通路、HPA轴、信号转导通路等途径可抑制抑郁症的发病进程。本文还总结分析了中药多糖目前存在问题和下一步研究重点，以期为抑郁症治疗靶点与机制、中药多糖有效成分研究与开发提供科学依据和新思路。
未来的信息化战争,不再是单纯的机械与火力对抗,而是需要充分利用一切信息资源的信火一体作战形式。谁拥有更强大的电磁情报分析能力,谁就能在战场上获得主动。尤其是在战争状态下,通过侦察敌方的电磁信号来预测分析敌方装备,进而分析其背后所隐藏的作战意图,从而辅助指挥员迅速决策,具有极其重要的战略意义。但随着信息技术的发展,电磁情报所搜集到的电磁信号数据在不断地增长,基于领域专家的电磁情报分析在面对海量数据时
抑郁症已成为严重的全球健康问题。以化学药物为主的临床治疗方案呈现出不同程度的不良反应和耐药性。植物多糖来源丰富，是研究最广泛的一种多糖类物质，具有抗氧化、抗肿瘤、抗炎、抗衰老、抗抑郁等多种生物活性。植物多糖可以通过调节神经递质及其受体表达、炎症反应、下丘脑–垂体–肾上腺轴、神经营养因子、抗氧化应激损伤以及调节色氨酸代谢、肠道菌群发挥抗抑郁作用。植物多糖结构与抗抑郁功效关系的大多数研究仅仅停留在描述
在制造业快速发展的时代背景下,工业互联网作为一种将工业系统与新一代互联网技术深度融合的新型应用模式,正在推动着全球工业体系的智能化变革。数字孪生是工业互联网蓬勃发展不可缺少的技术支撑之一,能够实现对生产过程的监控。目前,数字孪生被广泛应用于各行业领域中。行为分析是评价产线运行情况的工具,它能够在产品投入制造前评估产线的性能并分析产线的运行情况,提高生产线的智能性、主动性和预测性。然而,目前的数字孪