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

19th IEEE International Conference on High Performance Computing and Communications (HPCC) / 15th IEEE International Conference on Smart City (SmartCity) / 3rd IEEE International Conference on Data Science and Systems (DSS)

作者： Jung, Hojin Kim, Songkuk Yonsei Univ Yonsei Inst Convergence Technol Sch Integrated Technol Incheon South Korea

ISBN: (纸本)9781538625880

Depicting a complex system like social networks as a graph helps understand its structure and relation. As advances in technology increase the amount of data, simplifying a large-scale graph has attracted interests. Simplification reduces the size of a graph while preserving its important properties. In this paper, we propose the summarization algorithm to simplify a graph focusing on degree correlation and clustering coefficient. The degree correlation is a measure to assess the influence of each vertex and their connections. The clustering coefficient estimates latent connections between two distinct vertices. To this end, we first separate a graph into communities. Looking at groups instead of a graph itself allows us to extract important vertices and edges more easily. We then categorize communities into four cases and simplify them in different ways to preserve the innate characteristics. The quantitative and qualitative evaluations demonstrate how effectively our algorithm serves the goal. Overall, our contributions are as follows: (a) unique pattern: We found that hubs are connected indirectly via low-degree vertices. Sigcon preserves these vertices during simplification. (b) efficient algorithm: Sigcon identifies influential vertices and edges to simplify a graph on the basis of degree correlation and clustering coefficient connecting vertices effectively.

关键词： graph algorithm Simplification Degree Correlation Clustering Coefficient

来源：评论

学校读者我要写书评

暂无评论

Scalable Hybrid Implementation of graph Coloring using MPI and OpenMP

Scalable Hybrid Implementation of Graph Coloring using MPI a...

引用

26th IEEE International Parallel and Distributed Processing Symposium (IPDPS) / Workshop on High Performance Data Intensive Computing

作者： Sariyuece, Ahmet Erdem Saule, Erik Catalyuerek, Uemit V. Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA

ISBN: (纸本)9780769546766

graph coloring algorithms are commonly used in large scientific parallel computing either for identifying parallelism or as a tool to reduce computation, such as compressing Hessian matrices. Large scientific computations are nowadays either run on commodity clusters or on large computing platforms. In both cases, the current target platform is hierarchical with distributed memory at the node level and shared memory at the processor level. In this paper, we present a novel hybrid graph coloring algorithm and discuss how to obtain the best performance on such systems from algorithmic, system and engineering perspectives.

关键词： graph algorithm graph coloring Distributed Memory Shared Memory Hybrid programming

来源：评论

学校读者我要写书评

暂无评论

Ontology Reshaping for Knowledge graph Construction: Applied on Bosch Welding Case 21st

Ontology Reshaping for Knowledge Graph Construction: Applied...

引用

21st International Semantic Web Conference (ISWC)

作者： Zhou, Dongzhuoran Zhou, Baifan Zheng, Zhuoxun Soylu, Ahmet Cheng, Gong Jimenez-Ruiz, Ernesto Kostylev, Egor V. Kharlamov, Evgeny Bosch Ctr Artificial Intelligence Renningen Germany Univ Oslo Dept Informat Oslo Norway Oslo Metropolitan Univ Dept Comp Sci Oslo Norway Nanjing Univ State Key Lab Novel Software Technol Nanjing Peoples R China City Univ London Dept Comp Sci London England

ISBN: (纸本)9783031194320;9783031194337

Automatic knowledge graph (KG) construction is widely used in industry for data integration and access, and there are several approaches to enable (semi-)automatic construction of knowledge graphs. One important approach is to map the raw data to a given knowledge graph schema, often a domain ontology, and construct the entities and properties according to the ontology. However, the existing approaches to construct knowledge graphs are not always efficient enough and the resulting knowledge graphs are not sufficiently application-oriented and user-friendly. The challenge arises from the trade-off: the domain ontology should be knowledge-oriented, to reflect the general domain knowledge rather than data particularities;while a knowledge graph schema should be data-oriented, to cover all data features. If the former is directly used as the knowledge graph schema, this can cause issues like blank nodes created due to classes unmapped to data and deep knowledge graph structures. To this end, we propose a system for ontology reshaping, which generates knowledge graph schemata that fully cover the data while also covers domain knowledge well. We evaluated our approach extensively with a user study and three real manufacturing datasets from Bosch against four baselines, showing promising results.

关键词： Semantic data integration Knowledge graph Ontology reshaping graph algorithm Automatic knowledge graph construction

来源：评论

学校读者我要写书评

暂无评论

graph-BASED FOREGROUND EXTRACTION IN EXTENDED COLOR SPACE

GRAPH-BASED FOREGROUND EXTRACTION IN EXTENDED COLOR SPACE

引用

16th IEEE International Conference on Image Processing

作者： Kim, Hansung Hilton, Adrian Univ Surrey Ctr Vis Speech & Signal Proc Surrey GU2 7XH England

ISBN: (纸本)9781424456536

We propose a region-based method to extract semantic foreground regions from color video sequences with static backgrounds. First, we introduce a new distance measure for background subtraction which is robust against shadows. Then the foreground region is extracted with a graph-based region segmentation method considering background difference and spatial homogeneity. For efficient computation, the graph structure is optimized by the minimum spanning tree before segmentation. The main contribution is that the proposed algorithm improves on conventional approaches especially in strong shadow regions and does not require manual initialization. We have verified through experiments and comparison to state of the art methods that the proposed algorithm works well with various cameras and environment.

关键词： Background subtraction graph algorithm Minimum spanning tree

来源：评论

学校读者我要写书评

暂无评论

HAGP: A Hub-centric Asynchronous graph Processing Framework for Scale-free graph 15

HAGP: A Hub-centric Asynchronous Graph Processing Framework ...

引用

2015 15th IEEE ACM International Symposium on Cluster Cloud and Grid Computing (CCGrid 2015)

作者： Gao, Tao Lu, Yutong Zhang, Baida Natl Univ Def Technol Coll Comp Changsha Hunan Peoples R China

ISBN: (纸本)9781479980062

graph structure which is often used to model the relationship between the data items has drawn more and more attention. The graph datasets from many important domains have the property called scale-free. In the scale-free graphs, there exist the hubs, which have much larger degree than the average value. The hubs may cause the problems of load imbalance, poor scalability and high communication overhead when the graphs are processed in the distributed memory systems. In this paper, we design an asynchronous graph processing framework targeted for distributed memory by considering the hubs as a separate part of the vertexes, which we call it the hub-centric idea. Specifically speaking, a hub-duplicate graph partitioning method is proposed to balance the workload and reduce the communication overhead. At the same time, an efficient asynchronous state synchronization method for the duplicates is also proposed. In addition, a priority scheduling strategy is applied to further reduce the communication overhead.

关键词： graph processing graph algorithm parallel algorithm distributed computing

来源：评论

学校读者我要写书评

暂无评论

Scalable graph and mesh algorithms on distributed-memory systems

Scalable graph and mesh algorithms on distributed-memory sys...

引用

作者： Panitanarak, Thap PennState University Libraries

学位级别：Doctor of Philosophy

Big datasets are now becoming a standard quantity in large-scale data analysis; they involve social and information network, and scientific mesh computations. These datasets are commonly stored and processed across multiple machines due to limited capabilities (such as memory and CPU) of single machines. However, many available analysis tools are still lacking in terms of an ability to fully utilize existing distributed-memory architectures. As these datasets are usually processed and analyzed in the form of graphs or meshes, we propose scalable and efficient approaches for graph and mesh computations for distributed-memory systems in this dissertation. Although graph and mesh computations are closely related regarding their parallelization approaches, some of their unique characteristics still need to be addressed separately. Thus, we organize the dissertation into two parts. The first part is for distributed graph computations, and the second part is for distributed mesh *** the first part of the dissertation, we focus on graph computations. First, we study a problem of Single-Source Shortest Path (SSSP) by analyzing and evaluating three well-known SSSP algorithms, i.e, Dijkstra's, Bellman-Ford, and $\Delta$-stepping algorithms. We implement these algorithms to run on distributed-memory systems based on a bulk synchronous parallel model. Their performances are evaluated and compared. Next, we propose our SSSP algorithm by combining advantages of these SSSP algorithms and utilizing a two-dimensional (2D) graph layout for our graph data structures. Then, we extend our study of the 2D graph data structures and optimization approaches to other well-known graph algorithms including breadth-first search, approximate diameter, connected components, and PageRank on various real-world graphs. Our objective is to implement an efficient graph framework for distributed-memory systems that works efficiently for many graph algorithms on various graph types. Finally,

关键词： parallel computation graph algorithm distributed memory algorithm graph data structure linear solver mesh warping SSSP mesh partitioning

来源：评论

学校读者我要写书评

暂无评论

Parallel Subgraph Listing in a Large-Scale graph 14

Parallel Subgraph Listing in a Large-Scale Graph

引用

ACM SIGMOD International Conference on Management of Data

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

ISBN: (纸本)9781450323765

Subgraph listing is a fundamental operation to many graph and network analyses. The problem itself is computationally expensive and is well-studied in centralized processing algorithms. However, the centralized solutions cannot scale well to large graphs. Recently, several parallel approaches are introduced to handle the large graphs. Unfortunately, these parallel approaches still rely on the expensive join operations, thus cannot achieve high performance. In this paper, we design a novel parallel subgraph listing framework, named PSgL. The PSgL iteratively enumerates subgraph instances and solves the subgraph listing in a divide-and-conquer fashion. The framework completely relies on the graph traversal, and avoids the explicit join operation. Moreover, in order to improve its performance, we propose several solutions to balance the workload and reduce the size of intermediate results. Specially, we prove the problem of partial subgraph instance distribution for workload balance is NP-hard, and carefully design a set of heuristic strategies. To further reduce the enormous intermediate results, we introduce three independent mechanisms, which are automorphism breaking of the pattern graph, initial pattern vertex selection based on a cost model, and a pruning method based on a light-weight index. We have implemented the prototype of PSgL, and run comprehensive experiments of various graph listing operations on diverse large graphs. The experiments clearly demonstrate that PSgL is robust and can achieve performance gain over the state-of-the-art solutions up to 90%.

关键词： graph graph algorithm Subgraph Listing graph Enumeration

来源：评论

学校读者我要写书评

暂无评论

A Two-Player Coalition Cooperative Scheme for the Bodyguard Allocation Problem

引用

Journal of Computer Science & Technology 2018年第4期33卷 823-837页

作者： Jose Alberto Fernandez-Zepedu Daniel Brubeck-Salcedo Daniel Fajardo-Delgado Hector Zatarain-Aceves Department of Computer Science Center for Scientific Research and Higher Education of Ensenada Ensenada BC 22860 Mexico Department of Systems and Computation Instituto Technol6gico de Ciudad Guzmdn Guzmdn JAL 49100 Mexico

We address the bodyguard allocation problem （BAP）, an optimization problem that illustrates the conflict of interest between two classes of processes with contradictory preferences within a distributed system. While a class of processes prefers to minimize its distance to a particular process called the root, the other class prefers to maximize it; at the same time, all the processes seek to build a communication spanning tree with the maximum social welfare. The two state-of-the-art algorithms for this problem always guarantee the generation of a spanning tree that satisfies a condition of Nash equilibrium in the system; however, such a tree does not necessarily produce the maximum social welfare. In this paper, we propose a two-player coalition cooperative scheme for BAP, which allows some processes to perturb or break a Nash equilibrium to find another one with a better social welfare. By using this cooperative scheme, we propose a new algorithm called FFC-BAPs for BAP. We present both theoretical and empirical analyses which show that this algorithm produces better quality approximate solutions than former algorithms for BAP.

关键词： bodyguard allocation problem coalitional game graph algorithm Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

Greedy algorithms for generalized k-rankings of paths

引用

INFORMATION PROCESSING LETTERS 2010年第22期110卷 979-985页

作者： Zemke, Andrew James, Sandra Narayan, Darren A. Rochester Inst Technol Sch Math Sci Rochester NY 14623 USA Concordia Univ Dept Math St Paul MN 55104 USA

A k-ranking of a graph is a labeling of the vertices with positive integers 1,2, ..., k so that every path connecting two vertices with the same label contains a vertex of larger label. An optimal ranking is one in which k is minimized. Let P-n, be a path with n vertices. A greedy algorithm can be used to successively label each vertex with the smallest possible label that preserves the ranking property. We seek to show that when a greedy algorithm is used to label the vertices successively from left to right, we obtain an optimal ranking. A greedy algorithm of this type was given by Bodlaender et al. in 1998 [1] which generates an optimal k-ranking of P-n. In this paper we investigate two generalizations of rankings. We first consider bounded (k, s)-rankings in which the number of times a label can be used is bounded by a predetermined integer s. We then consider k(t)-rankings where any path connecting two vertices with the same label contains t vertices with larger labels. We show for both generalizations that when G is a path, the analogous greedy algorithms generate optimal k-rankings. We then proceed to quantify the minimum number of labels that can be used in these rankings. We define the bounded rank number (r,s)(G) to be the smallest number of labels that can be used in a (k, s)-ranking and show for n 2, (r,s)(P-n) = [ ((n (2 1))/s)] + i where i = [log(2)(s)] + 1. We define the k(t)-rank number, (t)(r)(G) to be the smallest number of labels that can be used in a k(t)-ranking. We present a recursive formula that gives the k(t)-rank numbers for paths, showing 1;.(P-j) n for all a(n-1) < j <= a(n) where {a(n)) is defined as follows: a(l) = 1 and a(n) = a(n) = [((t + 1)/t)a(n-1)] + 1. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Rank number Ordered coloring Minimal ranking Vertex coloring Greedy algorithm graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Low-cost heuristics for matrix bandwidth reduction combined with a Hill-Climbing strategy

引用

RAIRO-OPERATIONS RESEARCH 2021年第4期55卷 2247-2264页

作者： Gonzaga de Oliveira, Sanderson L. Silva, Liberio M. Univ Fed Lavras Lavras Brazil

This paper studies heuristics for the bandwidth reduction of large-scale matrices in serial computations. Bandwidth optimization is a demanding subject for a large number of scientific and engineering applications. A heuristic for bandwidth reduction labels the rows and columns of a given sparse matrix. The algorithm arranges entries with a nonzero coefficient as close to the main diagonal as possible. This paper modifies an ant colony hyper-heuristic approach to generate expert-level heuristics for bandwidth reduction combined with a Hill-Climbing strategy when applied to matrices arising from specific application areas. Specifically, this paper uses low-cost state-of-the-art heuristics for bandwidth reduction in tandem with a Hill-Climbing procedure. The results yielded on a wide-ranging set of standard benchmark matrices showed that the proposed strategy outperformed low-cost state-of-the-art heuristics for bandwidth reduction when applied to matrices with symmetric sparsity patterns.

关键词： Bandwidth reduction sparse matrix ant colony optimization hyper-heuristic reordering algorithms renumbering ordering graph labeling graph algorithm local search procedure Hill-Climbing procedure

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：