【摘 要】
：
可达性查询是图上的基本操作之一,用于判断图中两结点之间是否存在可达路径。现有的可达性查询算法可分为两类,第一类是直接在原图G上构建索引来回答查询,但其查询性能会受图规模的影响。第二类是首先将原图G进行规约,得到规模较小的规约图Gr,然后在Gr上构建索引来回答查询。现有的图规约算法可以显著减小原图G的规模,但是无法保证规约图上的查询性能。本文针对现有方法存在的问题展开研究,具体研究内容如下。首先,提
论文部分内容阅读
可达性查询是图上的基本操作之一,用于判断图中两结点之间是否存在可达路径。现有的可达性查询算法可分为两类,第一类是直接在原图G上构建索引来回答查询,但其查询性能会受图规模的影响。第二类是首先将原图G进行规约,得到规模较小的规约图Gr,然后在Gr上构建索引来回答查询。现有的图规约算法可以显著减小原图G的规模,但是无法保证规约图上的查询性能。本文针对现有方法存在的问题展开研究,具体研究内容如下。首先,提出一种新的图规约方法,称为RCN（Removable Complete Node）规约。该方法将有|V|个结点的图G简化为有|Vr|个结点的图Gr,|Vr|＜|V|。假设G中任一结点为查询点的概率为1/|V|,本文方法可以保证查询q可在常量时间回答的概率下界为1-（|Vr|/|V|）2,即Gr规模越小,q可在常量时间内被回答的概率越大。RCN规约的关键在于找到图中更多的RCNs,以减小规约图的规模,从而提高查询q可在常量时间内回答的概率。本文提出Yes-Label扩展方法,可有效增加图中RCNs数目,但其执行效率与扩展效果受到No-Label的影响。基于此,提出基于BT-order的No-Label,该标签可以支持高效的Yes-Label扩展,以增加图中RCNs数目。提出了大度结点剪枝和弱等价规约两个优化策略来提升Yes-Label扩展的效果,进一步增加RCNs数目。其次,基于RCN规约的结果图,提出一种新的编码方案IL。该编码方案基于结点的影响力来确定结点的处理顺序,可以保证可达性关系覆盖面大的结点被尽早地处理。IL算法在RCN规约的基础上,引入了新的剪枝策略:若结点u无入邻居,则无需为它构造标签。从而显著减小索引规模,支持高效的查询处理。最后,本文在20个真实数据集上进行实验。从图规约与可达性查询处理两方面对RCN规约方法在处理可达性查询时的高效性进行了验证。实验结果表明,RCN规约方法的性能优于现有的图规约方法。基于RCN规约方法,可以显著缩短现有可达性查询方法的查询处理时间。
其他文献
在大数据时代,信息产生的速度越来越快,各行各业所累积的数据量也越来越大。比如在淘宝和京东这样的电商场景中,无论是用户的数量还是商品的数量,都是以亿为计量单位的。因此,对于一个普通的用户而言,在不借助任何工具的情况下,想要从海量的商品池中快速地找到自己感兴趣的商品是一件极其困难的事情。在这种情况下,推荐系统的产生成为了一种必然,可以帮助用户从海量信息中迅速获取有效的信息。深度学习兴起之后,融合因子分
阿尔茨海默病（Alzheimers Disease,AD）是一种与年龄高度相关且患病过程不可逆的神经退行性疾病。在临床表现上,患者早期通常会出现日常记忆丧失、表达受阻以及行动受限等症状,随着病情的不断发展,患者会逐渐丧失个人的生活自理能力,给患者的家庭以及社会带来沉重的经济压力与看护负担。由于该疾病的特殊性与复杂性,医学上至今仍未找到具体的致病原因,以及有效治愈患者的方法,只能通过人为干扰或药物治
多标签图像分类（MLIC）广泛应用于场景理解、多目标识别、视觉问答等领域。虽然基于深度卷积神经网络（CNN）在图像分类中表现出了能够媲美人眼识别率的精度和性能,但基于CNN的分类模型已经被证明非常容易受到对抗样本的攻击。因此,对于MLIC系统的安全性研究成为一个亟待解决的问题。本文结合现实场景中多标签图像分类器的应用情况,对多标签图像攻击算法开展了研究。其主要内容包括:1、本文提出在多标签图像对抗
随着智能监控设备的普及,从视频中获取和分析行人数据变得十分便捷,人群行为分析和建模引起了越来越多研究人员的关注。一方面,通过计算机视觉和物理方法研究人群行为特征;另一方面,通过对人群行为进行建模,验证和改进人类行为动力学模型。本论文以视频行人轨迹提取为主线,对多视角行人目标检测进行深入研究,结合相似性度量发展了基于轨迹相似度的时空聚类方法,并对行人运动时空特性进行了挖掘分析。论文的主要工作和成果如
任务型对话系统是人工智能领域的研究热点,其实用价值也颇受业界重视。流水线型对话系统是目前采用的主流架构,它将整个对话过程划分为自然语言理解、对话策略、对话生成等多个模块,其中用于识别语句中关键词的槽填充和用于语句中预测情感的对话的情感分析是自然语言理解模块的重要子任务,因此受到学术界和工业界的重点关注,而用深度学习建模槽填充和对话的情感分析是当前的主流方法。然而目前槽填充和对话的情感分析模型存在着
复杂系统云仿真是利用云计算资源共享等优势为复杂系统仿真提供支持的新模式,具有实体规模大,交互复杂,依赖库多样等特点。应用封装可以降低应用部署的复杂度。准确的资源预测可以实现复杂系统云仿真应用最优性能。然而,目前的云环境下主流的封装技术依靠手动编写Dockerfile文件,导致封装效率低下,目前的资源预测技术没有考虑复杂系统仿真应用实体规模,时间同步等特征,难以准确预测应用所需资源,导致资源利用不充
三维超声计算机断层扫描（Three dimensional ultrasonic computed tomography,简称3D USCT）在乳腺癌早期检测筛查及诊断等方面有很好的效果,有助于乳腺癌的及早发现与治疗,提高治愈机率。但在3D USCT系统中,换能器的延迟、位置偏差和温度误差等系统误差会影响到重建图像的质量,其中换能器延迟和位置偏差影响最大,故而需进行换能器的校正。论文基于与浙江衡玖
流数据变化速度快,价值密度稀疏且只能单次访问的特性,导致难以对其价值进行有效评估。采样作为数据价值评估的重要手段,现有在全量流数据上采样会产生过多存储计算资源浪费,访问部分流数据的采样评估方法易丢失蕴含大量离散值的流数据的价值和信息。基于上述问题,如何高效精准的对流数据进行采样使得能够准确的评估其价值成为一个尚待解决的问题。本文针对此问题展开研究,主要贡献如下:首先,针对全量流数据采样产生资源浪费
云计算由于其海量存储和计算而快速发展起来,为个人和组织提供了存储和计算服务。为了保护存储在云中的数据隐私,内容提供商通常会对其数据进行加密。然而云中存在许多数据共享场景,这种存储模式相应的增加了用户之间共享数据的困难。代理重加密是解决数据共享的重要技术手段,让云服务提供商充当代理方来转换密文。但当用户退出时,现有的撤销方案忽视了撤销的用户可能会解密撤销前访问的数据,这会导致内容提供商存储在云服务提
近年来,三维网格模型分割成为计算机图形、图像学的研究热点,越来越多的研究者深入网格分割领域,促使分割技术不断发展,但现有的网格分割方法大多不能完全适用于不同种类的模型,这些三维分割算法或多、或少存在各自的分割缺陷。仅仅利用传统形状直径函数的三维分割算法,存在计算量大、无法较好的适应复杂模型等缺点。为了使三维分割能够较好的适用于不同类别的模型,提高分割速度、增强分割鲁棒性和提高模型分割准确度等,本文