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

35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Castaneda, Armando Fraigniaud, Pierre Gafni, Eli Rajsbaum, Sergio Roy, Matthieu Univ Nacl Autonoma Mexico Inst Matemat Mexico City DF Mexico Univ Paris Diderot CNRS IRIF Paris France Univ Calif Los Angeles CS Dept Los Angeles CA USA Univ Toulouse CNRS LAAS Toulouse France

ISBN: (纸本)9781450339643

Adaptive renaming can be viewed as a coordination task involving a set of asynchronous agents, each aiming at grabbing a single resource out of a set of resources totally ordered by their desirability. We consider a generalization of adaptive renaming to take into account scenarios in which resources are not independent. We model constraints between resources as an undirected graph: nodes represent the ressources, and an edge between two ressources indicates that these two ressources cannot be used simultaneously. In such a setting, the sets of resources that processes may use simultaneously form independent sets. In this note, we focus on this task in a model where such independent sets are computed by wait-free processes.

关键词： graph algorithm task wait-free computing coordination distributed algorithm renaming adaptive algorithms

来源：评论

学校读者我要写书评

暂无评论

Performance Analysis of Spark/graphX on POWER8 Cluster

Performance Analysis of Spark/GraphX on POWER8 Cluster

引用

International Supercomputing Conference (ISC High Performance)

作者： Que, Xinyu Schneidenbach, Lars Checconi, Fabio Costa, Carlos H. A. Buono, Daniele IBM TJ Watson Yorktown Hts NY 10598 USA

ISBN: (纸本)9783319460796;9783319460789

POWER8, the latest RISC (Reduced Instruction Set Computer) microprocessor of the IBM Power architecture family, was designed to significantly benefit emerging workloads, including Business Analytics, Cloud Computing and High Performance Computing. In this paper, we provide a thorough performance evaluation on a widely used large-scale graph processing framework, Spark/graphX, on a POWER8 cluster. Note that we use Spark and Java versions out of the box without any optimization. We examine the performance with several important graph kernels such as Breadth-First Search, Connected Components, and PageRank using both large real-world social graphs and synthetic graphs of billions of edges. We study the Spark/graphX performance against some architectural aspects and perform the first Spark/graphX scalability test with up to 16 POWER8 nodes.

关键词： POWER8 Spark/graphX graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Application of Fuzzy Sections for Constructing Dynamic Routing in the Network DTN 16th

Application of Fuzzy Sections for Constructing Dynamic Routi...

引用

16th International Conference on Next Generation Teletraffic and Wired/Wireless Advanced Networks and Systems (NEW2AN) / 9th Conference on Internet of Things and Smart Spaces Are You Smart (ruSMART)

作者： Shichkina, Yulia Kupriyanov, Mikhail Plotnikova, Anastasia Domaratsky, Yaroslav St Petersburg Electrotech Univ LETI Dept Comp Sci & Engn St Petersburg Russia Motorola Solut Inc Technol Off Schaumburg IL USA

ISBN: (纸本)9783319463018;9783319463001

This article provides a methodology for construction of data transfer paths through DTN dynamic network, implemented with the devices mounted on moving objects and connected via WI-FI, Bluetooth and LTE D2D. The methodology covers all the five stages of the Knowledge Discovery in Databases technology. The stage of application of Data Mining tools was studied in more detail. It is based on the application of fuzzy logic instrument to select subset that meet the network parameters from a set of moving objects. Further application to the subset of related objects of Yen's algorithm of search for optimal paths on a weighted graph with weights of the grade of the selected subset ownership of the object allows to build the most credible data transfer path and several alternative paths, ranked by descending of data delivery probability.

关键词： Fuzzy sets Database query Delay tolerance network Route graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient graph computation on hybrid CPU and GPU systems

引用

JOURNAL OF SUPERCOMPUTING 2015年第4期71卷 1563-1586页

作者： Zhang, Tao Zhang, Jingjie Shu, Wei Wu, Min-You Liang, Xiaoyao Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200240 Peoples R China Fudan Univ Dept Elect Engn Shanghai 200433 Peoples R China

graphs are used to model many real objects such as social networks and web graphs. Many real applications in various fields require efficient and effective management of large-scale, graph-structured data. Although distributed graph engines such as GBase and Pregel handle billion-scale graphs, users need to be skilled at managing and tuning a distributed system in a cluster, which is a non-trivial job for ordinary users. Furthermore, these distributed systems need many machines in a cluster in order to provide reasonable performance. Several recent works proposed non-distributed graph processing platforms as complements to distributed platforms. In fact, efficient non-distributed platforms require less hardware resource and can achieve better energy efficiency than distributed ones. graphChi is a representative non-distributed platform that is disk-based and can process billions of edges on CPUs in a single PC. However, the design drawbacks of graphChi on I/O and computation model have limited its parallelism and performance. In this paper, we propose a general, disk-based graph engine called ggraph to process billion-scale graphs efficiently by utilizing both CPUs and GPUs in a single PC. Ggraph exploits full parallelism and full overlap of computation and I/O processing as much as possible. Experiment results show that ggraph outperforms graphChi and Powergraph. In addition, ggraph achieves the best energy efficiency among all evaluated platforms.

关键词： graph graph algorithm graph processing platform GPU

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal Placement of Secrets in graphs

引用

Open Journal of Discrete Mathematics 2016年第4期6卷 238-247页

作者： Werner Poguntke Fachbereich Technische Betriebwirtschaft Fachhochschule Südwestfalen Hagen Germany

We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minimal cuts, if the failure probabilities of vertices and edges are close to zero. As the main contribution of this paper, node separators are used to design a heuristic for the near-optimal placement of secrets sets on the vertices of the graph.

关键词： graph algorithm Cut Secret Sharing Approximation Network Design

来源：评论

学校读者我要写书评

暂无评论

Exploring Network Optimizations for Large-Scale graph Analytics 15

Exploring Network Optimizations for Large-Scale Graph Analyt...

引用

International Conference for High Performance Computing, Networking, Storage and Analysis (SC)

作者： Que, Xinyu Checconi, Fabio Petrini, Fabrizio Liu, Xing Buono, Daniele IBM Corp TJ Watson Res Ctr Yorktown Hts NY 10598 USA

ISBN: (纸本)9781450337236

graph analytics are arguably one of the most demanding workloads for high-performance systems and interconnection networks. graph applications often display all-to-all, fine-grained, high-rate communication patterns that expose the limits of the network protocol stacks. Load and communication imbalance generate hard-to-predict network hot-spots, and may require computational steering due to unpredictable data distributions. In this paper we present a lightweight communication library, implemented "on the metal" of BlueGene/Q and POWER7 IH that we have used to support large-scale graph algorithms up to 96K processing nodes and 6 million threads. With this library we have explored several optimization techniques, including overlapped communication, non-blocking collectives, message aggregation, and computation in the network for special collective communication patterns, such as parallel prefix. The experimental results show significant performance improvements, ranging from 5X to 10X, when compared to equally optimized MPI implementations.

关键词： Network Performance graph algorithm POWER7 IH BlueGene/Q

来源：评论

学校读者我要写书评

暂无评论

Strong minimum energy -hop rooted topology for hierarchical wireless sensor networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第4期30卷 1077-1094页

作者： Panda, B. S. Shetty, D. Pushparaj Indian Inst Technol Delhi Dept Math Comp Sci & Applicat Grp New Delhi 110016 India

Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraint that the resulting topology containing only bidirectional links is strongly connected. This problem is known to be NP-hard. However, most of the wireless sensor networks are hierarchical in nature, where shorter path lengths are preferred for communication between any two nodes. Given a set of sensors and a specified sensor, say , the strong minimum energy -hop rooted topology problem (h-SMERT) is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraints that the resulting topology containing only bidirectional links is strongly connected and the length of the path from to any other node is at most . We prove that the h-SMERT problem is NP-hard. We also prove that h-SMERT problem is APX-hard. We then show that h-SMERT problem is not approximable within a factor of 1/2 (1 - epsilon) unless NP subset of D T I M E (n(log log n)) On the positive side, we propose a -2(1 + ln n)-approximation algorithm for the h-SMERT problem. We also study two special cases of the h-SMERT problem, namely, the -rest-h-SMERT problem and the -int-h-SMERT problem. We propose a -approximation algorithm for the -rest-h-SMERT problem. The -int-h-SMERT problem is NP-hard for arbitrary . However, for fixed constant , we propose a -approximation algorithm for the -int-h-SMERT problem and obtain a polynomial time optimal algorithm for the -int-h-SMERT problem for k = 2.

关键词： Wireless sensor network Topology control problem Transmission power assignment graph algorithm NP-hard APX-hard Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Swapping labeled tokens on graphs

引用

THEORETICAL COMPUTER SCIENCE 2015年 586卷 81-94页

作者： Yamanaka, Katsuhisa Demaine, Erik D. Ito, Takehiro Kawahara, Jun Kiyomi, Masashi Okamoto, Yoshio Saitoh, Toshiki Suzuki, Akira Uchizawa, Kei Uno, Takeaki Iwate Univ Dept Elect Engn & Comp Sci Morioka Iwate 0208551 Japan MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Nara Inst Sci & Technol Grad Sch Informat Sci Ikoma Nara 6300192 Japan Yokohama City Univ Int Coll Arts & Sci Kanazawa Ku Yokohama Kanagawa 2360027 Japan Univ Electrocommun Dept Commun Engn & Informat Chofu Tokyo 1828585 Japan Kobe Univ Grad Sch Engn Nada Ku Kobe Hyogo 6578501 Japan Yamagata Univ Grad Sch Sci & Engn Yonezawa Yamagata 9928510 Japan Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan

Consider a puzzle consisting of n tokens on an n-vertex graph, where each token has a distinct starting vertex and a distinct target vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n(2)) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2 alpha-approximation algorithm for graphs whose tree a-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Approximation Complete bipartite graph graph algorithm Sorting network Tree

来源：评论

学校读者我要写书评

暂无评论

On the tractability of some natural packing, covering and partitioning problems

引用

DISCRETE APPLIED MATHEMATICS 2015年 180卷 25-35页

作者： Bernath, Attila Kiraly, Zoltan Hungarian Acad Sci Inst Comp Sci & Control MTA SZTAKI Budapest Hungary Eotvos Lorand Univ Dept Comp Sci Budapest Hungary Eotvos Lorand Univ Egervary Res Grp MTA ELTE Budapest Hungary

In this paper we fix 7 types of undirected graphs: paths, paths with prescribed endvertices, circuits, forests, spanning trees, (not necessarily spanning) trees and cuts. Given an undirected graph G = (V, E) and two "object types" A and B chosen from the alternatives above, we consider the following questions. Packing problem: can we find an object of type A and one of type Bin the edge set E of G, so that they are edge-disjoint? Partitioning problem: can we partition E into an object of type A and one of type B? Covering problem: can we cover E with an object of type A, and an object of type B? This framework includes 44 natural graph theoretic questions. Some of these problems were well-known before, for example covering the edge-set of a graph with two spanning trees, or finding an s-t path P and an s'-t' path P' that are edge-disjoint. However, many others were not, for example can we find an s-t path P subset of E and a spanning tree T subset of E that are edge-disjoint? Most of these previously unknown problems turned out to be NP-complete, many of them even in planar graphs. This paper determines the status of these 44 problems. For the NP-complete problems we also investigate the planar version, for the polynomial problems we consider the matroidal generalization (wherever this makes sense). (C) 2014 Elsevier B.V. All rights reserved.

关键词： graph algorithm Packing Covering Partitioning Path Circuit Tree Forest Cut

来源：评论

学校读者我要写书评

暂无评论

Finding a Friendly Community in Social Networks Considering Bad Relationships

引用

COMPUTER JOURNAL 2015年第6期58卷 1469-1481页

作者： Kim, Sang-Yeon Choi, Dong-Wan Chung, Chin-Wan Korea Adv Inst Sci & Technol Dept Comp Sci Taejon 305701 South Korea

Community detection in social networks is one of the most active problems with lots of applications. Most of the existing works on the problem have focused on detecting the community considering only the closeness between community members. In the real world, however, it is also important to consider bad relationships between members. In this paper, we propose a new variant of the community detection problem, called friendly community search. In the proposed problem, for a given graph, we aim to not only find a densely connected subgraph that contains a given set of query nodes but also minimizes the number of nodes involved in bad relationships in the subgraph. We prove that is Non-deterministic Polynomial-time hard (NP-hard), and develop two novel algorithms, called Greedy and SteinerSwap that return the near optimal solutions. Experimental results show that two proposed algorithms outperform the algorithm adapted from an existing algorithm for the optimal quasi-clique problem.

关键词： community detection social network graph algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：