【摘 要】
:
最短路径查询问题已被研究多年,然而,目前已有大部分工作主要集中在普通图上,针对时态图最短路径查询的研究工作相对较少.时态图中,2个顶点之间有多条边,每条边附带有时态区间,记录着边上代表事件的发生时间和结束时间.时态图最短路径查询在城市交通路径规划、社交网络分析、通信网络挖掘等领域有着广泛的应用.由于最短时态路径的子路径不能保证是最优子结构,传统的普通图最短路径计算方法不再适用于时态图.因此提出了基于压缩转化图树(CTG-tree)索引的查询方法,该方法包含预处理和在线查询2个阶段.预处理阶段将时态图转化为
【机 构】
:
浙江工业大学计算机科学与技术学院 杭州 310023;浙江大学计算机科学与技术学院 杭州 310013
论文部分内容阅读
最短路径查询问题已被研究多年,然而,目前已有大部分工作主要集中在普通图上,针对时态图最短路径查询的研究工作相对较少.时态图中,2个顶点之间有多条边,每条边附带有时态区间,记录着边上代表事件的发生时间和结束时间.时态图最短路径查询在城市交通路径规划、社交网络分析、通信网络挖掘等领域有着广泛的应用.由于最短时态路径的子路径不能保证是最优子结构,传统的普通图最短路径计算方法不再适用于时态图.因此提出了基于压缩转化图树(CTG-tree)索引的查询方法,该方法包含预处理和在线查询2个阶段.预处理阶段将时态图转化为普通图,提出了一种无损压缩方法将转化图压缩以减小图规模,采用层次划分技术将压缩有向图分解为若干个子图,并基于子图建立CTG-tree索引.CTG-tree中的节点保存相应子图内部分顶点之间的最短路径、孩子节点对应子图的边界点之间的最短路径、孩子节点对应子图的边界点与当前节点相应子图的边界点之间的最短路径信息.在线查询阶段基于构建的CTG-tree索引,提出了一种高效的最短路径查询方法.基于4个真实的时态图数据集实验结果表明,与现有方法相比,提出的方法具有更优的查询性能.
其他文献
情绪识别与日常生活的诸多领域都有很大联系.然而,通过单一算法难以获得较高的情绪识别准确率,为此,提出一种基于支持向量机(support vector machine,SVM)和K近邻(K-nearest neighbors,KNN)融合算法(SVM-KNN)的情绪脑电识别模型.在情绪分类时,首先计算待识别样本与最优分类超平面的空间距离,若两者距离大于提前设定的阈值,选用SVM分类器对情绪样本分类,否则选用KNN分类器.最后在SEED情感数据集上进行实验测试,通过对比实验,得出SVM-KNN算法提高了情绪三
随着数码相机的成本降低和普及,基于计算机视觉的非接触式结构健康监测技术越来越受到重视.传统的接触式测量仪器可能导致轻质结构上的质量负荷,并且在大型土木结构上安装和维护成本高且耗时,特别是对于长期应用.作为一种替代的非接触方法,使用数码相机的计算机视觉方法成本相对较低、灵活.针对传统光流方法在微小位移测量精度和稳定性不足的问题,本文提出了一种改进的基于相位的光流法来计算结构的振动位移.在这种方法中,通过引入基于相位的视频运动放大方法中构造的部分复数可操纵滤波器,与视频序列图像的卷积得到结构的局部空间相位信息
随着经济的发展,机器人制造单元对制造行业的生产效率和生产质量有很大提高.相对于传统的柔性制造单元,带机器人搬运的车间的调度问题还考虑了加工物料的搬运环节.因此,生产调度所面临的问题越来越复杂.针对Pareto支配关系在高维多目标优化中的支配能力不足,本文将Lorenz支配和CDAS支配分别与NSGA-Ⅲ算法相结合,并首次应用到带机器人制造单元的高维多目标车间调度问题上来.考虑到现代生产过程的复杂化,本文提出对最大完工时间、加工总能耗、交货期提前量、延迟量、生产总成本等多个目标同时进行优化,用于确定机器人工
眼球区域分割是医学超声图像处理和分析的关键步骤,由于临床设备采集的眼球超声图像具有噪声干扰、区域模糊、边缘灰度相似等缺点,从而导致现有的方法不能准确地分割出眼球区域,因此本文基于可变形卷积提出了一种语义嵌入的注意力机制的分割方法.首先使用可变形卷积替代传统的卷积,提高本文网络对眼球区域的表征能力;其次构建语义嵌入的注意力机制,融合不同层之间的语义信息,增强目标区域中的显著特征,减少对背景区域的错误分割,从而提升网络的分割准确度;最后,为了验证本文模型的分割性能,分别与现有的3种深度学习分割模型进行对比,在
在面向持续集成测试用例优先排序(continuous integration test case prioritization,CITCP)的强化学习方法中,智能体通过对测试用例实施奖励从而调整测试用例优先排序策略以适应后续集成测试,可以满足持续集成测试频繁迭代和快速反馈的需求.智能体通常只奖励执行失效测试用例,但实际工业程序持续集成测试具有集成高频繁但测试低失效的特点,对CITCP的实际应用提出新的挑战.测试低失效,即稀少的执行失效测试用例数量,会导致强化学习中奖励对象稀少,引发强化学习的稀疏奖励问题.
针对现有高速铁路中LTE-R通信系统安全评估方法不足且评估过程存在模糊性和灰色性等问题,建立基于集对可拓和改进层次分析法的LTE-R通信系统风险评估模型.从影响通信系统的人、设备和网络等主要方面建立评估体系,确定风险评估指标和评价标准.利用改进层次分析法计算权重,基于集对可拓构建系统风险集对和计算风险联系隶属度,从而判断通信系统风险等级.实例分析表明,使用集对可拓和改进层次分析法可有效和真实反映LTE-R通信系统的风险状态,可为LTE-R通信系统的安全建设系统与风险管控提供理论依据.
为促进矿业领域向信息化、智能化的方向转变,实现对石墨的智能识别尤为关键.针对人工识别石墨花费时间长、效率低等问题,提出了一种改进的AlexNet网络应用于石墨的图像识别.首先通过随机裁剪、依概率水平翻转和归一化处理等手段对数据集进行图像预处理达到数据增强的目的;然后采用激活函数ReLU6压缩动态范围,使算法更稳健;运用批标准化算法进行归一化加快收敛速度;修改卷积核的大小增强泛化能力;在全连接层加上dropout正则化进一步防止过拟合.在仿真实验中,与已有方法进行比较,所给方法降低了损失值,提高了石墨的识别
交通问题不仅影响人们的出行,同时也会带来环境污染以及安全等问题,准确的交通流预测是构建智能交通系统、预防和缓解交通问题的关键.目前的预测方法大多没有考虑到交通流动态的时空相关性、周期性以及线性与非线性等特点.在充分考虑上述因素的基础上,提出一种基于信息增强传输的时空图神经网络模型,主要包含多特征注意力模块、信息增强传输模块、时间注意力模块以及线性与非线性融合模块.其中,多特征注意力模块捕获多种交通特征之间的内在联系,考虑交通流的周期性;信息增强传输模块充分利用了交通网络信息,以增强交通网络的信息传输能力,
传统的空间并置模式挖掘旨在发现空间中实例频繁共存的特征子集.目前空间并置模式的大多数研究都将模式的频繁性作为兴趣度度量.然而,在实际应用场景中,用户往往不仅对特征集的频繁性感兴趣,而且对它的完整性也感兴趣.结合并置模式的频繁性和完整性,提出主导空间并置模式(dominant spatial co-location patterns,DSCPs),目的 是为用户提供一组高质量的并置模式,具体地,在空间并置模式挖掘任务中引入了模式占有度,以衡量并置模式的完整性.我们通过同时考虑模式的完整性和频繁性形式化了主导
随着空间数据体量的持续增长,空间数据所蕴含的价值巨大.传统的数据感知存储技术和处理分析方法已然不能充分挖掘海量空间数据的价值.因此,空间数据智能,一个专注于海量空间数据的研究与应用的多学科交叉的领域,正扮演着越来越重要的角色.介绍了空间数据智能的概念、空间数据智能领域所面临的技术挑战及空间数据智能的关键技术,同时介绍了空间数据智能在社会生活中的典型应用场景,最后对空间数据智能研究的发展做出了展望.