اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFully distributed PageRank computation with exponential convergence
51
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
This work studies a fully distributed algorithm for computing the PageRank vector, which is inspired by the Matching Pursuit and features: 1) a fully distributed implementation 2) convergence in expectation with exponential rate 3) low storage requirement (two scalar values per page). Illustrative experiments are conducted to verify the findings.
قيم البحث
اقرأ أيضاً
In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a giv
en task. At the same time, the distributed task itself may now require global reconfiguration from a given initial network $G_s$ to a target network $G_f$ from a family of networks having some good properties, like small diameter. With reasonably powerful computational entities, there is a straightforward algorithm that transforms any $G_s$ into a spanning clique in $O(log n)$ time. The algorithm can then compute any global function on inputs and reconfigure to any target network in one round. We argue that such a strategy is impractical for real applications. In real dynamic networks there is a cost associated with creating and maintaining connections. To formally capture such costs, we define three edge-complexity measures: the emph{total edge activations}, the emph{maximum activated edges per round}, and the emph{maximum activated degree of a node}. The clique formation strategy highlighted above, maximizes all of them. We aim at improved algorithms that achieve (poly)log$(n)$ time while minimizing the edge-complexity for the general task of transforming any $G_s$ into a $G_f$ of diameter (poly)log$(n)$. We give three distributed algorithms. The first runs in $O(log n)$ time, with at most $2n$ active edges per round, an optimal total of $O(nlog n)$ edge activations, a maximum degree $n-1$, and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations and gives a target network of diameter $O(log n)$. Our third algorithm shows that if we slightly increase the maximum degree to polylog$(n)$ then we can achieve a running time of $o(log^2 n)$.
We measured the impact of long-range exponentially decaying intra-areal lateral connectivity on the scaling and memory occupation of a distributed spiking neural network simulator compared to that of short-range Gaussian decays. While previous studie
s adopted short-range connectivity, recent experimental neurosciences studies are pointing out the role of longer-range intra-areal connectivity with implications on neural simulation platforms. Two-dimensional grids of cortical columns composed by up to 11 M point-like spiking neurons with spike frequency adaption were connected by up to 30 G synapses using short- and long-range connectivity models. The MPI processes composing the distributed simulator were run on up to 1024 hardware cores, hosted on a 64 nodes server platform. The hardware platform was a cluster of IBM NX360 M5 16-core compute nodes, each one containing two Intel Xeon Haswell 8-core E5-2630 v3 processors, with a clock of 2.40 G Hz, interconnected through an InfiniBand network, equipped with 4x QDR switches.
This paper investigates the online motion coordination problem for a group of mobile robots moving in a shared workspace. Based on the realistic assumptions that each robot is subject to both velocity and input constraints and can have only local vie
w and local information, a fully distributed multi-robot motion coordination strategy is proposed. Building on top of a cell decomposition, a conflict detection algorithm is presented first. Then, a rule is proposed to assign dynamically a planning order to each pair of neighboring robots, which is deadlock-free. Finally, a two-step motion planning process that combines fixed-path planning and trajectory planning is designed. The effectiveness of the resulting solution is verified by a simulation example.
There are several ideas being used today for Web information retrieval, and specifically in Web search engines. The PageRank algorithm is one of those that introduce a content-neutral ranking function over Web pages. This ranking is applied to the se
t of pages returned by the Google search engine in response to posting a search query. PageRank is based in part on two simple common sense concepts: (i)A page is important if many important pages include links to it. (ii)A page containing many links has reduced impact on the importance of the pages it links to. In this paper we focus on asynchronous iterative schemes to compute PageRank over large sets of Web pages. The elimination of the synchronizing phases is expected to be advantageous on heterogeneous platforms. The motivation for a possible move to such large scale distributed platforms lies in the size of matrices representing Web structure. In orders of magnitude: $10^{10}$ pages with $10^{11}$ nonzero elements and $10^{12}$ bytes just to store a small percentage of the Web (the already crawled); distributed memory machines are necessary for such computations. The present research is part of our general objective, to explore the potential of asynchronous computational models as an underlying framework for very large scale computations over the Grid. The area of ``internet algorithmics appears to offer many occasions for computations of unprecedent dimensionality that would be good candidates for this framework.
The conditional posterior Cramer-Rao lower bound (PCRLB) is an effective sensor resource management criteria for large, geographically distributed sensor networks. Existing algorithms for distributed computation of the PCRLB (dPCRLB) are based on raw
observations leading to significant communication overhead to the estimation mechanism. This letter derives distributed computational techniques for determining the conditional dPCRLB for quantized, decentralized sensor networks (CQ/dPCRLB). Analytical expressions for the CQ/dPCRLB are derived, which are particularly useful for particle filter-based estimators. The CQ/dPCRLB is compared for accuracy with its centralized counterpart through Monte-Carlo simulations.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
