检索结果-内蒙古大学图书馆

12th International Workshop on algorithms and Models for the Web-Graph (WAW)

作者： Nassar, Huda Kloster, Kyle Gleich, David F. Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Purdue Univ Dept Math W Lafayette IN 47907 USA

ISBN: (纸本)9783319267845;9783319267838

The personalized PageRank diffusion is a fundamental tool in network analysis tasks like community detection and link prediction. It models the spread of a quantity from a set of seed nodes, and it has been observed to stay localized near this seed set. We derive an upper-bound on the number of entries necessary to approximate a personalized PageRank vector in graphs with skewed degree sequences. This bound shows localization under mild assumptions on the maximum and minimum degrees. Experimental results on random graphs with these degree sequences show the bound is loose and support a conjectured bound.

关键词： PageRank Diffusion local algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Convex Thresholding 15

Distributed Convex Thresholding

引用

34th Annual ACM Symposium on Principles of Distributed Computing (PODC)

作者： Wolff, Ran Yahoo Labs Haifa Israel

ISBN: (纸本)9781450336178

Over the last fifteen years, a large group of algorithms emerged which compute various predicates from distributed data with a focus on communication efficiency. These algorithms are often called "communication-efficient", "geometric-monitoring", or "local" algorithms. We jointly call them distributed convex thresholding algorithms, for reasons which will be explained in this work. Distributed convex thresholding algorithms have found their applications in domains in which bandwidth is a scarce resource, such as wireless sensor networks and peer-to-peer systems, or in scenarios in which data rapidly streams to the different processors but outcome of the predicate rarely changes. Common to all of these algorithms is the use of a data dependent criteria to determine when further messaging is required. This work presents two very simple yet exceedingly general theorems from which the correctness of all distributed convex thresholding algorithms can be elicited, and demonstrates that for key examples. Because the theorems are general, they extend the range of predicates which can be computed in a communication efficient manner beyond what is currently known. Unlike the previous correction proofs given to these algorithms, the proofs of the theorems presented here do not depend on the communication infrastructure. So the correctness of any distributed convex thresholding algorithm is immediately extended from broadcast enabled networks or from cycle free networks to general networks. Inspecting existing algorithms in light of the new theorems reveals that they contain redundant requirements, which cause them to send messages when indeed none are needed.

关键词： local algorithms Geometric monitoring Communication efficient algorithms Wireless sensor networks Peer-to-peer systems

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds on localized Sensor Self-Deployment for Focused Coverage 24

Tight Bounds on Localized Sensor Self-Deployment for Focused...

引用

International Conference on Computer Communications and Networks ICCCN

作者： Sharma, Gokarna Krishnan, Hari Louisiana State Univ Sch Elect Engn & Comp Sci Baton Rouge LA 70803 USA

ISBN: (纸本)9781479999644

We consider the self-deployment problem in mobile sensor networks with the objective of providing focused coverage for a point of interest (POI) such that the maximum area around it is covered by sensors without sensing holes. We present a local greedy algorithm, called TTGREEDY, that solves this problem in at most R + 2 . (n - 1) time steps, where R is the distance to the farthest initial sensor position from the POI and n is the number of sensors. This is a significant improvement over the best previously known O(D) time step algorithm of Blazovics and Lukovszki, where D is the sum of the initial distances to the sensors from the POI. The main idea is to synchronously drive mobile sensors along a locally-computed triangle tessellation avoiding collisions of sensors. We also show that there are initial configurations of n sensors in this problem where at least R+ (n-1)/2 time steps are needed by any greedy algorithm. These results provide the first tight runtime (within a small constant factor) solution to this problem.

关键词： Mobile sensor networks focused coverage self-deployment point of interest local algorithms runtime

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Exponential Speed-Up of local algorithms using Non-local Communication

Brief Announcement: Exponential Speed-Up of Local Algorithms...

引用

29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing

作者： Lenzen, Christoph Wattenhofer, Roger ETH Comp Engn & Networks Lab Zurich Switzerland

ISBN: (纸本)9781605588889

We demonstrate how to leverage a system's capability for all-to-all communication to achieve an exponential speed-up of local algorithms despite bandwidth and memory restrictions. More precisely, if a network comprises n nodes with all-to-all bandwidth n(epsilon) (epsilon > 0 constant) and nodes know their input and neighborhood with respect to a graph problem instance of polylogarithmic maximum degree, any local algorithm for this problem with running time r is an element of O(log n) and reasonably small states can be simulated within O(log r) rounds.

关键词： local algorithms simulation all-to-all communication

来源：评论

学校读者我要写书评

暂无评论

Estimation of Intrinsic Volumes from Digital Grey-Scale Images

引用

JOURNAL OF MATHEMATICAL IMAGING AND VISION 2014年第2期49卷 352-376页

作者： Svane, Anne Marie Aarhus Univ Dept Math DK-8000 Aarhus C Denmark

local algorithms are common tools for estimating intrinsic volumes from black-and-white digital images. However, these algorithms are typically biased in the design based setting, even when the resolution tends to infinity. Moreover, images recorded in practice are most often blurred grey-scale images rather than black-and-white. In this paper, an extended definition of local algorithms, applying directly to grey-scale images without thresholding, is suggested. We investigate the asymptotics of these new algorithms when the resolution tends to infinity and apply this to construct estimators for surface area and integrated mean curvature that are asymptotically unbiased in certain natural settings.

关键词： Digital grey-scale images local algorithms Design based set-up Surface area Integrated mean curvature

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Super-Fast t-Ruling Sets 14

Brief Announcement: Super-Fast t-Ruling Sets

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Bisht, Tushar Kothapalli, Kishore Pemmaraju, Sriram, V Int Inst Informat Technol Hyderabad 500032 India Univ Iowa Dept Comp Sci Iowa City IA 52242 USA

ISBN: (纸本)9781450329446

A t-ruling set of a graph G = (V;E) is a vertex-subset S subset of V that is independent and satisfies the property that every vertex v is an element of V is at a distance of at most t hops from some vertex in S. A maximal independent set (MIS) is a 1-ruling set. Extending results from Kothapalli et al. (FSTTCS 2012) this note presents a randomized algorithm for computing, with high probability, a t-ruling set in O(t . log(1/t-1) n) rounds for 2 <= t <= root log log n and in exp(O(root log log n)) rounds for t > root log log n.

关键词： Distributed algorithms local algorithms Maximal Independent Sets Ruling Sets Symmetry Breaking

来源：评论

学校读者我要写书评

暂无评论

Anomaly Characterization in Large Scale Networks 44

Anomaly Characterization in Large Scale Networks

引用

44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)

作者： Anceaume, Emmanuelle Busnel, Yann Le Merrer, Erwan Ludinard, Romaric Marchand, Jean-Louis Sericola, Bruno CNRS IRISA Paris France Univ Nantes LINA F-44035 Nantes France Technicolor Rennes Rennes France Inria Yvelines France Ecole Normale Super Rennes Rennes France

ISBN: (纸本)9781479922338

The context of this work is the online characterization of errors in large scale systems. In particular, we address the following question: Given two successive configurations of the system, can we distinguish massive errors from isolated ones, the former ones impacting a large number of nodes while the second ones affect solely a small number of them, or even a single one? The rationale of this question is twofold. First, from a theoretical point of view, we characterize errors with respect to their neighbourhood, and we show that there are error scenarios for which isolated and massive errors are indistinguishable from an omniscient observer point of view. We then relax the definition of this problem by introducing unresolved configurations, and exhibit necessary and sufficient conditions that allow any node to determine the type of errors it has been impacted by. These conditions only depend on the close neighbourhood of each node and thus are locally computable. We present algorithms that implement these conditions, and show through extensive simulations, thier performances. Now from a practical point of view, distinguishing isolated errors from massive ones is of utmost importance for networks providers. For instance, for Internet service providers that operate millions of home gateways, it would be very interesting to have procedures that allow gateways to self distinguish whether their dysfunction is caused by network-level errors or by their own hardware or software, and to notify the service provider only in the latter case.

关键词： Bismuth Measurement Monitoring Observers Peer-to-peer computing Quality of service Trajectory Error detection large scale systems local algorithms large-scale systems Peer to peer computing Error detection Quality of service bismuth trajectory Observers Gateways doorways internet service providers point of view

来源：评论

学校读者我要写书评

暂无评论

A local CLUSTERING ALGORITHM FOR MASSIVE GRAPHS AND ITS APPLICATION TO NEARLY LINEAR TIME GRAPH PARTITIONING

引用

SIAM JOURNAL ON COMPUTING 2013年第1期42卷 1-26页

作者： Spielman, Daniel A. Teng, Shang-Hua Yale Univ Dept Comp Sci Program Appl Math New Haven CT 06520 USA Univ So Calif Dept Comp Sci Viterbi Sch Engn Los Angeles CA 90089 USA

We study the design of local algorithms for massive graphs. A local graph algorithm is one that finds a solution containing or near a given vertex without looking at the whole graph. We present a local clustering algorithm. Our algorithm finds a good cluster-a subset of vertices whose internal connections are significantly richer than its external connections-near a given vertex. The running time of our algorithm, when it finds a nonempty local cluster, is nearly linear in the size of the cluster it outputs. The running time of our algorithm also depends polylogarithmically on the size of the graph and polynomially on the conductance of the cluster it produces. Our clustering algorithm could be a useful primitive for handling massive graphs, such as social networks and web-graphs. As an application of this clustering algorithm, we present a partitioning algorithm that finds an approximate sparsest cut with nearly optimal balance. Our algorithm takes time nearly linear in the number edges of the graph. Using the partitioning algorithm of this paper, we have designed a nearly linear time algorithm for constructing spectral sparsifiers of graphs, which we in turn use in a nearly linear time algorithm for solving linear systems in symmetric, diagonally dominant matrices. The linear system solver also leads to a nearly linear time algorithm for approximating the second-smallest eigenvalue and corresponding eigenvector of the Laplacian matrix of a graph. These other results are presented in two companion papers.

关键词： graph clustering graph partitioning local algorithms sparsest cut approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable, Optimal Flow Routing in Datacenters via local Link Balancing 13

Scalable, Optimal Flow Routing in Datacenters via Local Link...

引用

ACM International Conference on Emerging Networking Experiments and Technologies (CoNEXT)

作者： Sen, Siddhartha Shue, David Ihm, Sunghwan Freedman, Michael J. Princeton Univ Princeton NJ 08544 USA

ISBN: (纸本)9781450321013

Datacenter networks should support high network utilization. Yet today's routing is typically load agnostic, so large flows can starve other flows if routed through overutilized links. Even recent proposals like centralized scheduling or end-host multi-pathing give suboptimal throughput, and they suffer from poor scalability and other limitations. We present a simple, switch-local algorithm called localFlow that is optimal (under standard assumptions), scalable, and practical. Although localFlow may split an individual flow (this is necessary for optimality), it does so infrequently by considering the aggregate flow per destination and allowing slack in distributing this flow. We use an optimization decomposition to prove localFlow's optimality when combined with unmodified end hosts' TCP. Splitting flows presents several new technical challenges that must be overcome in order to interact efficiently with TCP and work on emerging standards for programmable, commodity switches. Since localFlow acts independently on each switch, it is highly scalable, adapts quickly to dynamic workloads, and admits flexible deployment strategies. We present detailed packet-level simulations comparing localFlow to a variety of alternative schemes, on real datacenter workloads.

关键词： Flow routing Datacenter networks local algorithms Optimization decomposition

来源：评论

学校读者我要写书评

暂无评论

algorithms Using First-Order Neighborhoods for Minimization of Boolean Functions

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2013年第9期53卷 1410-1420页

作者： Panov, A. V. Moscow MV Lomonosov State Univ Fac Computat Math & Cybernet Moscow 119991 Russia

A class of minimization algorithms for Boolean functions that involve conjunctions from a reduced disjunctive normal form and first-order neighborhoods of such conjunctions is investigated. A particular algorithm is s... 详细信息

关键词： minimization of Boolean functions local algorithms information-computing algorithms majorant algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：