首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
王旭丛  李翠平  陈红 《软件学报》2014,25(9):2136-2148
P-Rank是SimRank的扩展形式,也是一种相似度度量方法,被用来计算网络中任意两个结点的相似性.不同于SimRank只考虑结点的入度信息,P-Rank还加入了结点的出度信息,从而更加客观准确地评价结点间的相似程度.随着大数据时代的到来,P-Rank需要处理的数据日益增大.使用MapReduce等分布式模型实现大规模P-Rank迭代计算的方法,本质上是一种同步迭代方法,不可避免地具有同步迭代方法的缺点:迭代时间(尤其是迭代过程中处理器等待的时间)长,计算速度慢,因此效率低下.为了解决这一问题,采用了一种迭代计算方法——异步累积更新算法.这个算法实现了异步计算,减少了计算过程处理器结点的等待时间,提高了计算速度,节省了时间开销.从异步的角度实现了P-Rank算法,将异步累积更新算法应用在了P-Rank上,并进行了对比实验.实验结果表明该算法有效地提高了计算收敛速度.  相似文献   

2.
分析了分布式图计算框架的同步和异步计算模式在调度开销和收敛速度上存在的优点与不足.同步计算模式调度开销小,但是收敛较慢;而异步计算模式收敛较快,但调度开销大.基于上述发现,提出一种混合计算模式,能够在分布式环境下有效地结合同步与异步计算模式的优点克服各自不足,以获得最优性能.混合计算模式采用"同步控制流"以降低分布式环境下的调度开销,同时采用"异步数据流"使计算过程使用较新的数据以加快收敛速度.基于多个典型图算法和真实大规模图的评测显示,混合计算模式的性能是原有同步计算模式的1.2倍到2.4倍,计算量平均减少30%;相对于异步计算模式通过减少调度开销,整体性能可以提升至其2.3倍到4.6倍.  相似文献   

3.
为克服传统经济调度的目标单一,计算量大,优化不力等诸多不足导致模型适用的困难,从电网分区和协调计算的角度建立了基于多目标优化的分布式电网经济调度模型.该模型同时考虑了由售购电价差引起的经济效益最大,机组运行能耗最少和污染气体排放最小等三个目标函数.重点阐述了一种基于近似牛顿方向的多区域分布式计算方法,并利用改进的距离差分进化算法用于各个分区内的独立优化计算,然后采取异步迭代的信息同步机制实现了全局的等值修正计算.最终算例表明了该方法能够在分布式电网经济调度的优化计算过程中取得良好的应用效果.  相似文献   

4.
全局同步计算模型简单易用,但是路障同步导致收敛速度变慢。以顶点为中心的异步迭代虽然提高了收敛速度,但在计算节点之间需要频繁发送信息。在Spark环境下提出一种基于子图的异步迭代更新方法。在子图之间建立异步消息通信连接后,子图能以异步方式发送数据块;通过多线程同步避免数据读写冲突,保证异步更新时顶点状态的一致性。在大规模样本数据集上分别从收敛结果、收敛速度和通信代价验证方法有效性。实验结果表明,与全局同步迭代相比,该方法有效提高了计算收敛速度。与顶点为中心的异步更新方式相比,该方法在收敛时间上略有增长,但是显著降低了通信开销。  相似文献   

5.
Web页面相似度搜索对于网络新闻推荐、近似查询等研究领域具有重要作用。SimRank是经典的相似度计算模型,但其预计算时间和空间开销非常巨大,不适用大规模Web页面网络。利用SimRank快速收敛的特点,在SimRank基础上提出高效Web页面相似度搜索方法(WSR),预计算1步迭代相似度矩阵,根据预计算的1步迭代相似度矩阵在线计算给定查询页面和其他页面的2步迭代相似度。通过对Web网络进行静态剪枝,进一步提高预计算和在线查询处理的效率。实验结果显示,WSR显著降低了存储开销和预计算时间开销,且具有较高精确度和快速查询响应时间。  相似文献   

6.
SimRank方法是一种基于图的拓扑结构信息来衡量任意两个对象间相似程度的方法,针对在真实的大规模社交网络中节点与节点之间的迭代计算过程需要消耗大量的时间,提出了一种基于SimRank全局矩阵平滑收敛的网络社区发现方法(SimRank global smooth convergence,SGSC)。首先,该算法通过经典度量来识别网络中的初始核心节点;然后利用矩阵平滑收敛来计算SimRank得到最终核心节点;最后,基于全局收敛矩阵,将社区聚集在核心节点周围,使用Closeness指数合并两个社区,通过递归的重复该过程,聚类出最终社区。在3种真实的不同规模的社交网络中将SGSC和其他2种具有代表性的方法进行比较,并验证了提出的算法在不同规模的社交网络中社区划分的准确率和算法运行的时间性能上有所提升。  相似文献   

7.
CORDIC算法常用于高效地实现多种超越函数求值,但算法的通用性使其无法针对具体函数进行优化。提出一种统一的指数/对数函数迭代求值算法LnE,实现方式与CORDIC算法类似,每次迭代同样只需进行移位、加法和简单的判断操作,拥有线性收敛速度,但LnE算法具备更多优势:只需x、y两条通路;每次迭代均进行加法操作,不需根据迭代系数di选择加法/减法,控制简单;不需进行扩展因子补偿;不需重复某些迭代以保证收敛。因此LnE算法的迭代次数和每次迭代的开销均小于CORDIC算法,相对于CORDIC算法可节省1/3以上的面积开销。  相似文献   

8.
李慧勇  陈仪香 《计算机应用》2015,35(11):3139-3145
针对车联网中数据流分布式处理的调度问题,提出了多维服务质量(QoS)改进异构计算最早完成时间(HEFT)调度算法.首先,分别建立了车联网中数据流的分布式处理任务的带权有向无环图模型和车联网分布式计算资源的七维QoS属性带权无向拓扑结构图模型.其次,改进经典的HEFT调度算法中的列表构造方法为最高层最小后继任务优先列表构造方法; 同时,将车联网分布式计算资源的七维QoS属性进行分组、降维,转化为两维综合属性优先权:计算性能优先权和通信性能优先权,形成了两种不同用户偏好的多维QoS改进HEFT调度算法.最后,通过算例分析表明:两种不同用户偏好的多维QoS改进HEFT调度算法综合性能优于经典的HEFT调度算法和轮询调度算法.  相似文献   

9.
大规模的异步通信网络中,实时获取系统级网络平均值对于指导系统进行控制决策,比如资源选择、负载均衡等,具有重要的意义。基于此,重点研究了异步网络环境中的平均一致性问题,提出了一种基于流的异步平均一致性协议FBAA。FBAA协议适用于动态的异步通信网络系统,而且运行过程不需要全局协调。实验表明该协议能够以较快的速度收敛到平均值,且收敛时间与网络规模无关。进一步通过对实验数据的统计分析,得出收敛时间与相关参数的关系以及算法达到最优收敛时间的参数设置。  相似文献   

10.
针对EigenRep信任模型没有对节点恶意欺骗行为做出信誉惩罚修正的问题,改进了全局信誉的计算方法,即加入了影响因子,使得节点计算的全局信誉更客观。同时针对EigenRep模型每次交易都需要在全网络范围内做全局信誉的迭代计算从而导致系统开销过大的问题,提出了一种新的信任机制。实验表明,该机制结合风险、本地信任度和全局信誉的策略,可以大大减少系统开销,适合更大规模的网络环境的应用。最后,利用该机制实现了一个电子商务平台系统。  相似文献   

11.
云计算外包越来越流行的同时也带来了新的安全问题和挑战:输入/输出数据的隐私性和结果的可验证性。本文围绕云计算环境下的安全矩阵行列式计算外包展开研究,构建一个适用于大矩阵行列式计算的可验证的安全云外包协议,在客户端将原始矩阵盲化加密后传送到云服务器端执行计算,云服务器将计算结果和验证值返回给客户端进行解密和验证。理论分析表明,在恶意云的安全模型下协议满足正确性、输入/输出私密性、高效性和结果可验证性。  相似文献   

12.
自然计算的仿真研究   总被引:3,自引:0,他引:3  
针对近年来新兴的计算分支的挑战,如DNA计算、量子计算、免疫计算和进化计算等,提出自然计算的框架、编码、控制策略。以及从自然计算映射到计算机仿真的广义映射模型,来探究新兴计算分支的共同机理及其在自然界中的源泉。借助MATLAB仿真工具对其进行的仿真实验表明,自然计算有优于传统计算的特性,为计算学和计算机科学的发展以及自然计算的仿真开拓了广阔前景和无限生机。  相似文献   

13.
李祥 《计算机学报》1996,19(10):735-740
1989年Blum,Shbu与Smale提出了在实数域上的一个计算模型,BSS机器计算模型主要是基于有赂图的,它很直观但没有形式化,不方便使用经典的离散计算理论中的许多成熟的工具,本文从程序设计系统出发,提出一种在任意有序与的自然的程序设计设计语言,严格定义了它的语法与语义,研究了它与  相似文献   

14.
Future computing paradigms and technologies will have to be more like the physical processes by which they are realized, and because these processes are primarily continuous, post-Moore’s law computing will involve an increased use of analog computation. Traditionally analog computers have computed ordinary differential equations of time, but analog field computation permits massively parallel temporal integration of partial differential equations. In principle many different physical media – not just electronics – can be exploited to implement the basic operations of analog computing, a small number of which are sufficient to approximate a wide variety of analog computations, thus providing a basis for universal analog computation and general-purpose analog computers. The contentious issue of the computational power of analog computers is addressed best on its own terms, rather by asking it within the context of Church-Turing computation, which distorts the relevant questions and their answers.  相似文献   

15.
Three conditions are usually given that must be satisfied by a process in order for it to be called a computation, namely, there must exist a finite length algorithm for the process, the algorithm must terminate in finite time for valid inputs and return a valid output and, finally, the algorithm must never return an output for invalid inputs. These three conditions are advanced as being necessary and sufficient for the process to be computable by a universal model of computation. In fact, these conditions are neither necessary nor sufficient. On the one hand, recently defined paradigms show how certain processes that do not satisfy one or more of the aforementioned properties can indeed be carried out in principle on new, more powerful, types of computers, and hence can be considered as computations. Thus, the conditions are not necessary. On the other hand, contemporary work in unconventional computation has demonstrated the existence of processes that satisfy the three stated conditions, yet contradict the Church–Turing thesis and, more generally, the principle of universality in computer science. Thus, the conditions are not sufficient.  相似文献   

16.
为降低委托计算方案中委托方与计算方的计算量和通信量,提高有效计算率 ,利用可验的全同态加密方案构造非交互的委托计算方案。分析结果表明,该方案满足委托计算方案的健壮性、完整性要求,委托方的复杂度为 ,计算方的复杂度为 ,通信量为 。与同类方案相比,验证过程更简单,有效计算率 ≥1/2。  相似文献   

17.
With the advent of multicore processors, it has become imperative to write parallel programs if one wishes to exploit the next generation of processors. This paper deals with skyline computation as a case study of parallelizing database operations on multicore architectures. First we parallelize three sequential skyline algorithms, BBS, SFS, and SSkyline, to see if the design principles of sequential skyline computation also extend to parallel skyline computation. Then we develop a new parallel skyline algorithm PSkyline based on the divide-and-conquer strategy. Experimental results show that all the algorithms successfully utilize multiple cores to achieve a reasonable speedup. In particular, PSkyline achieves a speedup approximately proportional to the number of cores when it needs a parallel computation the most.  相似文献   

18.
An infinite network for parallel computation is presented which can for every k become partitioned in cube-connected cycles-networks of size 22k2k [1]. This construction extends a result from [2], where finite such networks are constructed. This infinite network is useful for simplifying the structure and improving the efficiency of the general purpose parallel computer shown in [3].  相似文献   

19.
We consider concurrent-write PRAMs with a large number of processors of unlimited computational power and an infinite shared memory. Our adversary chooses a small number of our processors and gives them a 0–1 input sequence (each chosen processor gets a bit, and each bit is given to one processor). The chosen processors are required to compute thePARITY of their input, while the others do not take part in the computation. Ifat most q processors are chosen andq 1/2 log logn, then we show that computing PARITY needsq steps in the worst case. On the other hand, there exists an algorithm which computes PARITY inq steps (for anyq <n) in this model, thus our result is sharp. Surprisingly, if our adversary choosesexactly q of our processors, then they can compute PARITY in [q/2] + 2 steps, and in this case we show that it needs at least [q2] steps. Our result implies that large parallel machines which are efficient when only a small number of their processors are active cannot be constructed. On the other hand, a result of Ajtai and Ben-Or [1] shows that if we haven input bits which contain at most polylogn 1's and polynomially many processors which are all allowed to work, then thePARITY can be solved inconstant time.  相似文献   

20.
We show efficient, practical (server-aided) secure two-party computation protocols ensuring privacy, correctness and fairness in the presence of malicious (Byzantine) faults. Our requirements from the server are modest. To ensure privacy and correctness, we only assume a circuit evaluation service, executing an initialisation program provided by both parties. To ensure fairness, we further assume a trusted-decryption service, providing decryption service using a known public key. Our fairness-ensuring protocol is optimistic, i.e., the decryption service is invoked only in case of faults.Both of these trusted services are feasible in practice, and may be useful for additional tasks; both can also be distributed, with linear overhead, for redundancy. We believe that the protocols are sufficiently efficient, to allow deployment, in particular for financial applications. We also propose applications which constitute natural candidates to benefit from our protocols.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号