【摘 要】
：
近年来，图规模和图数据量的快速增长使得分布式图计算吸引了越来越多研究者的注意。拥塞模型是分布式算法设计中最常使用的模型之一，然而带宽的限制使得一些复杂的图计算问题在时间复杂度(在分布式算法中多用轮数复杂度表示时间复杂度)上往往难以令人满意。分布式图性质测试是一种可以有效降低算法轮数复杂度的方法：根据给定图具备或者ε-远离目标性质，图性质测试算法会相应地以一定概率(通常为2/3)输出肯定或否定结果。
论文部分内容阅读
近年来，图规模和图数据量的快速增长使得分布式图计算吸引了越来越多研究者的注意。拥塞模型是分布式算法设计中最常使用的模型之一，然而带宽的限制使得一些复杂的图计算问题在时间复杂度(在分布式算法中多用轮数复杂度表示时间复杂度)上往往难以令人满意。分布式图性质测试是一种可以有效降低算法轮数复杂度的方法：根据给定图具备或者ε-远离目标性质，图性质测试算法会相应地以一定概率(通常为2/3)输出肯定或否定结果。为凸显分布式图性质测试算法在时间效率上的提升，以k-边(点)连通性为切入点，讨论如何高效地设计满足拥塞模型的分布式k-边(点)连通性质测试算法。
如果一个图中的任意两点彼此之间都有k条边(点)不相交的路径，则称该图是k-边(点)连通的。连通度是图的全局属性，传统方法中精确计算该性质需要全局通信，这使得算法的轮数复杂度严重依赖于图规模。针对这一问题，适用于无向稀疏图和有向稀疏图的分布式k-边(点)连通性质测试算法首次在拥塞模型下被提出。新提出的分布式k-边(点)连通性质测试算法利用边连通性的等价性和点连通性的边增广技术，将整图划分成数量较多的小图，通过对这些小图进行处理，不但缓解了结点之间通信的带宽压力，还能摆脱轮数复杂度对图规模的依赖。此外，新提出的分布式测试算法将传统的集中式连通度测试算法的研究模型从有界度模型(bounded-degree graph model)拓展到稀疏图模型，扩大了算法的适用范围。这些技术方法的运用使得新算法的轮数复杂度不再依赖于图规模，达到了O(ck/εk)(c为常数，k,ε均为常数参数)轮。实验模拟也进一步验证了新提出的测试算法在轮数复杂度上带来的提升。
其他文献
我国西南地区已建成了多个超千万千瓦级水电基地，形成了跨流域、跨电网互联的超大规模水电系统，呈现出梯级规模大、巨型电站多、集中程度高、送电范围广、水力电力耦合紧密等不同于常规水电系统的独特特征，给其调度运行带来了巨大挑战，具体表现为:1.西南水电站群的发电能力远超当地电网的负荷水平，需要远距离跨省区输送至多个电网进行消纳、响应多个电网的负荷需求，面临电网负荷水平差异下的多电网调峰问题;2.西南水电站
AlGaN作为直接带隙的宽禁带（3.4eV-6.02eV）半导体材料，具有优秀的光电性质、高热稳定性和热导率、优良的介电特性和高机械强度，可以用来制备高性能电学器件和光电器件。纳米材料由于内部晶体周期性被破坏，在光电等邻域，表现出了比体材料更加优秀的性质。目前， AlGaN纳米材料及相关器件仍处于研究阶段，各种工艺下制备的AlGaN纳米材料的质量有待提高，其生长机理和模型还需要进一步地研究和完善。
在过去的几年中，DNN已被证明是解决许多实际问题的通用有效工具，使用DNN的应用数量呈爆炸式增加。DNN推理业务已开始成为云计算环境所提供的服务之一，低延迟，高准确度的响应质量成为服务提供者的目标。受深度强化学习在AI领域的良好变现，人们也尝试用深度强化学习方法来实现DNN推理业务系统的高质量响应。本文主要研究以下几个问题：1．基于深度强化学习的DNN业务调度。如今，这些问题中的大多数都是通过精心
键值数据库由于其结构简单、查询速度快，具有高可靠性和高扩展性的特点，·得到了广泛的应用。各类应用对键值存储系统读写性能的要求也越来越高，要求存储设备提供更快的读写性能。Intel公司为了解决SSD和内存中存在的巨大性能差异，推出了Optane系列产品。傲腾固态盘作为非易失存储器的硬盘产品，有良好的读写性能同时随机读写与顺序读写性能差异不大。传统的键值存储系统采用LSM-Tree(Log Struc
云计算近年来在工业界越来越普及，这主要得益于虚拟化技术的成熟和容器技术的发展，将应用以容器方式部署在云环境中已非常普遍。无服务器计算是基于容器技术衍生出的一种新的云计算范式，容器为无服务器计算带来了无显式管理成本、按用量计费、弹性扩容等优势。然而这种计算范式将传统的宏应用分解成无状态的细粒度函数，当突发负载到来时，无服务器计算平台启动大量容器并初始化函数执行环境(即冷启动)，这会带来显著的启动延迟
容器虚拟化技术因为其轻量的特点，已经在云中被广泛使用。Docker是目前最受欢迎的容器框架，原因是它可以将应用及其依赖打包成一个独立的容器镜像。通过容器镜像，用户可以方便地存储、部署容器。当前Docker采取了层级结构构建镜像，使得容器在存储和部署时相同的层只会被存储和拉取一次。然而，当前层级结构下的镜像会在镜像中引入冗余数据和不必要数据，造成容器存储和部署的低效。调研DockerHub上使用率前
在大数据、物联网和5G时代，随着各类智能终端、智能应用和传感器的普及和发展，数据呈现快速动态增长的趋势，需要面对流式数据的应用也越来越多。流式数据中虽然蕴藏着巨大的潜在价值，但因其具有增长迅速、持续不断、时效性强等特点，如何对流式数据进行高效、动态的挖掘分析成为重要的课题。 基于张量的多聚类作为聚类领域在高阶数据上较为先进的方法，能够在多个不同维度上对高阶大数据进行多模态分析挖掘。目前关于张量多
随着私家车的普及和交通体量的增大，智能交通监测技术已经得到了越来越多的关注，智能交通监测可以支持一系列应用例如交通堵塞疏导，智能交通管理和自动驾驶辅助等。而针对于一些需要低投入，部署范围广，方便扩展的特定场景如乡村道路监测，特定时间和路段的交通量调查等，如何实现便携的，有效的，易扩展的，低成本的，便于部署的以及鲁棒性强的智能交通监测就尤为重要。 通过测量细粒度的无线信号信道状态信息的变化实现智能
随着RDF(ResourceDescriptionFramework，资源描述框架)数据的逐渐增多和SPARQL(SPARQL Protocol and RDF Query Language)查询处理场景的日益丰富，查询计划的生成面临很多挑战。一方面，现有的RDF查询处理系统在生成查询计划时比较耗时。另一方面，这些系统在生成查询计划时对代价的估计不够准确，且较少考虑查询执行的并行技术，使得查询执行
深度学习作为最强大的数据挖掘技术，在各个领域都有着广泛的应用前景。然而在基于云计算的服务模式下，如果用户数据中存在隐私敏感信息，那么将存在潜在的隐私泄露风险。同时，深度学习算法提取到的中间特征不具有抗隐私分析能力，也存在对应的隐私泄露风险。 针对深度学习应用在推理阶段面临的用户数据隐私泄露风险，模型分割部署模式基于深度神经网络层级连接的特点，将神经网络从中间层一分为二，分别部署在客户端与服务器端