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

ACM SIGMOD International Conference on Management of Data

作者： Shao, Yingxia Chen, Lei Cui, Bin Peking Univ Sch EECS MOE Key Lab High Confidence Software Technol Beijing Peoples R China HKUST Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781450323765

A cohesive subgraph is a primary vehicle for massive graph analysis, and a newly introduced cohesive subgraph, k-truss, which is motivated by a natural observation of social cohesion, has attracted more and more attention. However, the existing parallel solutions to identify the k-truss are inefficient for very large graphs, as they still suffer from huge communication cost and large number of iterations during the computation. In this paper, we propose a novel parallel and efficient truss detection algorithm, called PETA. The PETA produces a triangle complete subgraph (TC-subgraph) for every computing node. Based on the TC-subgraphs, PETA can detect the local k-truss in parallel within a few iterations. We theoretically prove, within this new paradigm, the communication cost of PETA is bounded by three times of the number of triangles, the total computation complexity of PETA is the same order as the best known serial algorithm and the number of iterations for a given partition scheme is minimized as well. Furthermore, we present a subgraph-oriented model to efficiently express PETA in parallel graph computing systems. The results of comprehensive experiments demonstrate, compared with the existing solutions, PETA saves 2X to 19X in communication cost, reduces 80% to 95% number of iterations and improves the overall performance by 80% across various real-world graphs.

关键词： graph algorithm Cohesive Subgraph Truss Subgraph-Oriented

来源：评论

学校读者我要写书评

暂无评论

Designing a Heuristic Cross-Architecture Combination for Breadth-First Search 43

Designing a Heuristic Cross-Architecture Combination for Bre...

引用

43rd Annual International Conference on Parallel Processing (ICPP)

作者： You, Yang Bader, David A. Dehnavi, Maryam Mehri Tsinghua Univ Dept Comp Sci & Technol Beijing Peoples R China Georgia Inst Technol Sch Computat Sci & Engn Atlanta GA 30332 USA MIT Comp Sci & Artificial Intelligence Lab Boston MA USA

ISBN: (纸本)9781479956180

Breadth-First Search (BFS) is widely used in real-world applications including computational biology, social networks, and electronic design automation. The most effective BFS approach has been shown to be a combination of top-down and bottom-up approaches. Such hybrid techniques need to identify a switching point which is conventionally found through expensive trial-and-error and exhaustive search routines. We present an adaptive method based on regression analysis that enables dynamic switching at runtime with little overhead. We improve the performance of our method by exploiting popular heterogeneous platforms and efficiently design the approach for a given architecture. An 155x speedup is achieved over the standard top-down approach on GPUs. Our approach is the first to combine top-down and bottom-up across different architectures. Unlike combination on a single architecture, a mistuned switching point may significantly decrease the performance of cross-architecture combination. Our adaptive method can predict the switching point with high accuracy, leading to an 695x speedup compared the worst switching point.

关键词： graph algorithm Data-intensive Cross-architecture Optimization Knights Corner MIC Kepler K20x GPU Combination Regression Analysis

来源：评论

学校读者我要写书评

暂无评论

A practical approach to generating route sketches 2

A practical approach to generating route sketches

引用

2nd ACM SIGSPATIAL International Workshop on MapInteraction, MapInteract 2014

作者： Luxen, Dennis Niklaus, Patrick Mapbox Inc. 1714 14th St NW Rear Entrance WashingtonDC20009 United States Karlsruhe Institute of Technology Am Fasanengarten 5 Karlsruhe76128 Germany

ISBN: (纸本)9781450331418

Online mapping and navigation services are a corner stone of the World Wide Web. While automatically generated car directions have gone from static data to user-specific customizations, automatically generated route guidance has stayed very much the same. And as such, it doesn't necessarily reflect the complexity of turns and may also be hard to use while traveling. We report on a practical and efficient technique for computing and presenting generalizations of routes, so-called sketches that compress a route and its guidance into an easy to comprehend and usable form by non-uniformly scaling and generalizing certain parts of the route. Our work draws from a sound theoretical foundation, is easy to implement, and gives very good results in practice.

关键词： algorithm engineering graph algorithm Route sketches

来源：评论

学校读者我要写书评

暂无评论

Computing the rooted triplet distance between galled trees by counting triangles

引用

JOURNAL OF DISCRETE algorithmS 2014年 25卷 66-78页

作者： Jansson, Jesper Lingas, Andrzej Kyoto Univ Inst Chem Res Lab Math Bioinformat Uji Kyoto 6110011 Japan Lund Univ Dept Comp Sci S-22100 Lund Sweden

We consider a generalization of the rooted triplet distance between two phylogenetic trees to two phylogenetic networks. We show that if each of the two given phylogenetic networks is a so-called galled tree with n leaves then the rooted triplet distance can be computed in O(n(2.687)) time. Our upper bound is obtained by reducing the problem of computing the rooted triplet distance between two galled trees to that of counting monochromatic and almost-monochromatic triangles in an undirected, edge-colored graph. To count different types of colored triangles in a graph efficiently, we extend an existing technique based on matrix multiplication and obtain several new algorithmic results that may be of independent interest: (i) the number of triangles in a connected, undirected, uncolored graph with m edges can be computed in o(m(1.408)), time;(ii) if G is a connected, undirected, edge-colored graph with n vertices and C is a subset of the set of edge colors then the number of monochromatic triangles of G with colors in C can be computed in o(n(2.687)) time;and (iii) if G is a connected, undirected, edge-colored graph with n vertices and R is a binary relation on the colors that is computable in O(1) time then the number of R-chromatic triangles in G can be computed in o(n(2.687)) time. (C) 2013 Elsevier B.V. All rights reserved.

关键词： graph algorithm Rooted triplet distance Phylogenetic network comparison Triangle counting Matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

A graph-Based Approach to Find Teleconnections in Climate Data

引用

STATISTICAL ANALYSIS AND DATA MINING 2013年第3期6卷 158-179页

作者： Kawale, Jaya Liess, Stefan Kumar, Arjun Steinbach, Michael Snyder, Peter Kumar, Vipin Ganguly, Auroop R. Samatova, Nagiza F. Semazzi, Fredrick Univ Minnesota Dept Comp Sci Minneapolis MN 55455 USA Univ Minnesota Dept Soil Water & Climate St Paul MN 55108 USA Northeastern Univ Civil & Environm Engn Boston MA 02115 USA N Carolina State Univ Dept Comp Sci Raleigh NC 27695 USA N Carolina State Univ Dept Marine Earth & Atmospher Sci Raleigh NC 27695 USA

Pressure dipoles are important long distance climate phenomena (teleconnection) characterized by pressure anomalies of the opposite polarity appearing at two different locations at the same time. Such dipoles have been proven important for understanding and explaining the variability in climate in many regions of the world, e.g. the El Nino Southern Oscillation (ENSO) climate phenomenon, which is described by opposite pressure anomalies between the west and east Pacific and is known to be responsible for precipitation and temperature anomalies worldwide. This paper presents a graph-based approach called shared reciprocal nearest neighbor approach that considers only reciprocal positive and negative edges in the shared nearest neighbor graph to find the dipoles. One crucial aspect of our approach to the analysis of such networks is a careful treatment of negative correlations, whose proper consideration is critical for finding the dipoles. Further, our work shows the importance of modeling the time-dependent patterns of the dipoles in a changing climate in order to better capture the impact of important climate phenomena on the globe. To show the utility of finding dipoles using our approach, we show that the data driven dynamic climate indices generated from our algorithm generally perform better than static indices formed from the fixed locations used by climate scientists in terms of capturing impact on global temperature and precipitation. Our approach can generate a single snapshot picture of all the dipole interconnections on the globe in a given dataset and thus makes it possible to study the changes in dipole interactions and movements. As teleconnections are crucial in the understanding of the global climate system, there is a pressing need to better understand the behavior and interactions of these atmospheric processes as well as to capture them precisely. Our systematic graph-based approach to find the teleconnections in climate data is an attempt in that

关键词： graph algorithm teleconnections dipole discovery

来源：评论

学校读者我要写书评

暂无评论

A Linear Time algorithm for L(2,1)-Labeling of Trees

引用

algorithmICA 2013年第3期66卷 654-681页

作者： Hasunuma, Toru Ishii, Toshimasa Ono, Hirotaka Uno, Yushi Univ Tokushima Dept Math & Nat Sci Tokushima 7708502 Japan Hokkaido Univ Grad Sch Econ Div Modern Econ & Business Adm Sapporo Hokkaido 0600809 Japan Kyushu Univ Dept Econ Engn Fukuoka 8128581 Japan Osaka Prefecture Univ Grad Sch Sci Dept Math & Informat Sci Sakai Osaka 5998531 Japan

An L(2,1)-labeling of a graph G is an assignment f from the vertex set V(G) to the set of nonnegative integers such that |f(x)-f(y)|a parts per thousand yen2 if x and y are adjacent and |f(x)-f(y)|a parts per thousand yen1 if x and y are at distance 2, for all x and y in V(G). A k-L(2,1)-labeling is an L(2,1)-labeling f:V(G)->{0,aEuro broken vertical bar,k}, and the L(2,1)-labeling problem asks the minimum k, which we denote by lambda(G), among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2, and tree is one of very few classes for which the problem is polynomially solvable. The running time of the best known algorithm for trees had been O(Delta (4.5) n) for more than a decade, and an O(min{n (1.75),Delta (1.5) n})-time algorithm has appeared recently, where Delta and n are the maximum degree and the number of vertices of an input tree, however, it has been open if it is solvable in linear time. In this paper, we finally settle this problem by establishing a linear time algorithm for L(2,1)-labeling of trees. Furthermore, we show that it can be extended to a linear time algorithm for L(p,1)-labeling with a constant p.

关键词： Frequency/channel assignment graph algorithm L(2,1)-Labeling Vertex coloring

来源：评论

学校读者我要写书评

暂无评论

Fast Invisible Triangle Culling Mechanism for 3D Rendering Hardware

引用

SENSOR LETTERS 2013年第11期11卷 2086-2093页

作者： Chu, Slo-Li Hsiao, Chih-Chieh Chung Yuan Christian Univ Dept Informat & Comp Engn Chungli 32023 Taiwan

Current 3D graphics computing systems rely on a massive number of triangles to generate realistic images in embedded systems, on personal computers, and on high-performance workstations. Although the number of triangles increases, no specific order for their input sequence exists;thus, many triangles that do not contribute to a final image must still be rasterized and shaded. This study culls invisible triangles using a novel technique that focuses on the depth relationships among triangles before they are shaded and rasterized. The proposed technique can identify overlapped triangles exactly and eliminate these triangles to eliminate unnecessary triangular rasterizing and pixel shading. The simulation result shows this algorithm can eliminate 18-46% of triangles before rasterizing of given benchmarks in a typical 3D graphics hardware pipeline.

关键词： graph algorithm Invisible Triangle Culling GPU

来源：评论

学校读者我要写书评

暂无评论

Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel Floyd-Warshall and Parallel Dijkstra algorithms

引用

JOURNAL OF COMPUTING IN CIVIL ENGINEERING 2013年第3期27卷 263-273页

作者： Pradhan, Anu Mahinthakumar, G. (Kumar) Drexel Univ Dept Civil Architectural & Environm Engn Philadelphia PA 19104 USA N Carolina State Univ Dept Civil Construct & Environm Engn Raleigh NC 27695 USA

Parallel computing has become a powerful approach for solving real-time decisions about large-scale, computing-intensive transportation problems. A frequently encountered transportation problem is the "shortest path problem;" that is, finding the shortest path between any two nodes in a transportation network. For the large transportation networks encountered in major metropolitan areas, this problem can be computationally demanding, especially if shortest paths between all the nodes in the network need to be dynamically updated (e. g., evolving traffic conditions). In such a situation, one may wish to harness parallel computing to solve this problem. However, the parallel implementations of commonly used shortest-path algorithms are computationally demanding because of the inherent sequential nature of the search process used by the algorithms. This paper describes parallel implementations and includes performance analyses of two prominent graph algorithms (i.e., Floyd-Warshall and Dijkstra) used for finding the all-pairs shortest path for a large-scale transportation network. The results indicate that a multilevel parallel implementation that combines message passing interface (MPI) with shared memory threads [e. g., Open Multiprocessing (OpenMP) or POSIX Threads (pthreads)] is effective for solving these problems on a moderate number of symmetric multiprocessor (SMP) nodes. This paper also includes the derivation of the computational time for the different parallel implementations of these two graph algorithms. DOI: 10.1061/(ASCE)CP.1943-5487.0000220. (C) 2013 American Society of Civil Engineers.

关键词： Parallel computing graph algorithm Transportation Computing

来源：评论

学校读者我要写书评

暂无评论

Liar's domination in graphs: Complexity and algorithm

引用

DISCRETE APPLIED MATHEMATICS 2013年第7-8期161卷 1085-1092页

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

A set L subset of V (G) of a graph G = (V, E) is a liar's dominating set if (1) for all v is an element of V (G), vertical bar N-G[v]boolean AND L vertical bar >= 2 and (2) for every pair u, v is an element of V (G) of distinct vertices, vertical bar(N-G[u] boolean OR N-G[v]) boolean AND L vertical bar >= 3. A graph G = (V, E) admits a liar's dominating set if each of its connected component has at least three vertices. Given a graph G = (V, E) and an integer K, the liar's domination decision problem (LR-DOMDP) is to decide whether G has a liar's dominating set of cardinality at most K. Slater [P.J. Slater, Liar's Domination, Networks, 54(2) (2009) 70-74] proved that the LR-DOMDP is NP-complete for general graphs. Subsequently, Roden and Slater [M.L. Roden and P.J. Slater, Liar's domination in graphs, Discrete Math., 309(19) (2009) 5884-5890] showed a more general family of problems to each be NP-complete for bipartite graphs. Besides this result, no other algorithmic result for the liar's dominating set problem is available in the literature. In this paper, we first strengthen the complexity result of the LR-DOMDP by showing that this problem remains NP-complete for split graphs and hence for chordal graphs. Finally, we propose a linear time algorithm for computing a minimum cardinality liar's dominating set in a tree. (C) 2012 Elsevier B.V. All rights reserved.

关键词： graph algorithm NP-completeness Domination Liar's domination

来源：评论

学校读者我要写书评

暂无评论

Shortest paths avoiding forbidden subpaths

引用

NETWORKS 2013年第4期61卷 322-334页

作者： Ahmed, Mustaq Lubiw, Anna Google Inc Mountain View CA USA Univ Waterloo DRC Sch Comp Sci Waterloo ON N2L 3G1 Canada

We study a variant of the shortest path problem in graphs: given a weighted graph Gand vertices sand t, and given a set Xof forbidden paths in G, find a shortest s- tpath Psuch that no path in Xis a subpath of P. Path Pis allowed to repeat vertices and edges. We call each path in Xan exception, and our desired path a shortest exception avoiding path. We formulate a new version of the problem where the algorithm has no a priori knowledge of X, and finds out about an exception xXonly when a path containing xfails. This situation arises in computing shortest paths in optical networks. We give an algorithm that finds a shortest exception avoiding path in time polynomial in |G| and |X|. The main idea is to use a shortest path algorithm incrementally after replicating vertices when an exception is discovered. (c) 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013

关键词： graph algorithm Dijkstra optical network road network exception avoiding path

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：