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

1st International Conference on Advanced Computational and Communication Paradigms (ICACCP)

作者： Bhuyan, Bikram P. Karmakar, Arindam Hazarika, Shyamanta M. Asian Inst Management & Technol Gauhati Assam India Tezpur Univ Biomimet & Cognit Robot Lab Comp Sci & Engn Tezpur Assam India Indian Inst Technol Guwahati Dept Mech Engn Gauhati India

ISBN: (纸本)9789811082375;9789811082368

In Formal Concept Analysis, stability is an important utility measure to rank concepts. However, computation of stability is considered to be a hard problem. Efficient algorithms having good bounds to estimate stability holds promise. In this paper, an effective graph-based technique is proposed to estimate stability. Our estimation algorithm has a polynomial time complexity of O(vertical bar A vertical bar(2)) where vertical bar A vertical bar is the number of vertices.

关键词： Formal concept analysis algorithms graph algorithm Estimation algorithm Combinatorial problem

来源：评论

学校读者我要写书评

暂无评论

Fast Exact CoSimRank Search on Evolving and Static graphs 18

Fast Exact CoSimRank Search on Evolving and Static Graphs

引用

27th World Wide Web (WWW) Conference

作者： Yu, Weiren Wang, Fan Aston Univ Birmingham B4 7ET W Midlands England

ISBN: (纸本)9781450356398

In real Web applications, CoSimRank has been proposed as a powerful measure of node-pair similarity based on graph topologies. However, existing work on CoSimRank is restricted to static graphs. When the graph is updated with new edges arriving over time, it is cost-inhibitive to recompute all CoSimRank scores from scratch, which is impractical. In this study, we propose a fast dynamic scheme, D-CoSim, for accurate CoSimRank search over evolving graphs. Based on D-CoSim, we also propose a fast scheme, F-CoSim, that greatly accelerates CoSimRank search over static graphs. Our theoretical analysis shows that D-CoSim and F-CoSim guarantee the exactness of CoSimRank scores. On the static graph G, to efficiently retrieve CoSimRank scores S, F-CoSim is based on three ideas: (i) It first finds a "spanning polytree" T over G. (ii) On T, a fast algorithm is designed to compute the CoSimRank scores S(T) over the "spanning polytree" T. (iii) On G, D-CoSim is employed to compute the changes of S(T) in response to the delta graph (G circle minus T). Experimental evaluations verify the superiority of D-CoSim over evolving graphs, and the fast speedup of F-CoSim on large-scale static graphs against its competitors, without any loss of accuracy.

关键词： graph algorithm hyperlink analysis cosimrank similarity

来源：评论

学校读者我要写书评

暂无评论

A High-Performance Connected Components Implementation for GPUs 18

A High-Performance Connected Components Implementation for G...

引用

27th ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC)

作者： Jaiganesh, Jayadharini Burtscher, Martin Texas State Univ Dept Comp Sci San Marcos TX 78666 USA

ISBN: (纸本)9781450357852

Computing connected components is an important graph algorithm that is used, for example, in medicine, image processing, and biochemistry. This paper presents a fast connected-components implementation for GPUs called ECL-CC. It builds upon the best features of prior algorithms and augments them with GPU-specific optimizations. For example, it incorporates a parallelism-friendly version of pointer jumping to speed up union-find operations and uses several compute kernels to exploit the multiple levels of hardware parallelism. The resulting CUDA code is asynchronous and lock free, employs load balancing, visits each edge exactly once, and only processes edges in one direction. It is 1.8 times faster on average than the fastest prior GPU implementation running on a Titan X and faster on most of the eighteen real-world and synthetic graphs we tested.

关键词： connected components graph algorithm union-find parallelism GPU implementation

来源：评论

学校读者我要写书评

暂无评论

A dynamic programming algorithm for the maximum induced matching problem in permutation graphs 18

A dynamic programming algorithm for the maximum induced matc...

引用

9th International Symposium on Information and Communication Technology (SoICT)

作者： Viet-Dung Nguyen Ba-Thai Pham Viet-Hung Tran Phan-Thuan Do Korea Adv Inst Sci & Technol Daejeon South Korea Hanoi Univ Sci & Technol Hanoi Vietnam

ISBN: (纸本)9781450365390

For a finite undirected graph G = (V, E) and a positive integer k >= 1, an edge set M subset of E is a distance-k matching if the pairwise distance of edges in M is at least k in G. The special case k = 2 has been studied under the name maximum induced matching (MIM for short), i.e., a maximum matching which forms an induced subgraph in G. MIM arises in many applications, such as artificial intelligence, game theory, computer networks, VLSI design and marriage problems. In this paper, we design an O(n(2)) solution for finding MIM in permutation graphs based on a dynamic programming method on edges with the aid of the sweep line technique. Our result is better than the best known algorithm.

关键词： maximum induced matching permutation graph graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Workload prediction and balance for distributed reachability processing for large-scale attribute graphs

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2018年第6期30卷

作者： Ho, Li-Yung Wu, Jan-Jan Liu, Pangfeng Acad Sinica Inst Informat Sci 128Sect 2Acad Rd Taipei 11529 Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn 1Sect 4Roosevelt Rd Taipei 10617 Taiwan Acad Sinica Res Ctr Informat Technol 128Sect 2Acad Rd Taipei 11529 Taiwan Natl Taiwan Univ Grad Inst Networking & Multimedia 1Sect 4Roosevelt Rd Taipei 10617 Taiwan

Reachability query with label constraint in an attribute graph is one of the most fundamental and important operations in semantic network analysis. However, ever-growing graph size has resulted in intractable reachability problems on single machines. This work aims to devise efficient solutions for the reachability with label constraint problem in an attribute graph in a distributed environment. We focus on two issues in distributed processingdata locality and workload balancingsince data locality reduces communication overhead and workload balancing improves the efficiency of cluster use. We propose three novel techniques to address the two issues: (1) a partition replication method that improves data locality while conserving community property, (2) a workload-prediction method that accurately predicts machine workloads for a given quer, and (3) a workload balancing method that uses these predictions to shift partial workloads among machines to produce a balanced workload. Experimental results suggest that these techniques significantly improve performance and reduce total execution time by 40%.

关键词： attribute graph bulk synchronization distributed reachability graph algorithm workload balance workload prediction

来源：评论

学校读者我要写书评

暂无评论

Recommendation system in E-commerce websites: A graph Based Approached 7

Recommendation system in E-commerce websites: A Graph Based ...

引用

7th IEEE International Advance Computing Conference (IACC)

作者： Shaikh, Shakila Rathi, Sheetal Janrao, Prachi TCET Comp Engn Dept Bombay Maharashtra India

ISBN: (纸本)9781509015603

this paper is regarding the lack of semantic factor in recommendation systems and describes the different recommendation techniques that are being employed in the current e-commerce website. Recommendation system can be broadly classified into three categories: content-based, collaborative, and hybrid recommendation approaches. Content based systems consider the properties of the items to be recommended. For instance, if a Amazon user has purchased many romantic novels, then content based recommendation system recommends novels in the database as having the "romantic" genre. Collaborative filtering systems recommend items based on similarity measures between like minded users and/or items. The items recommended to a user are those preferred by similar users. This paper also emphasizes the need for semantics in current recommendation system to recommend products accurately. This also describes various limitations that are present in the current recommendation methods and suggests possible solutions that can improve current recommendation system used in e-commerce websites. It also includes a survey on popular e-commerce websites such as Amazon, Ebay, Flipkart Snapdeal and Paytm by rating them on different parameters and doing their comparative analyses This paper also focuses on how graph algorithm can be used to improve recommendation in e-commerce websites. The proposed system compares *** recommendation of images with the proposed method. The method incorporates semantic recommendation using overlap technique based in graph.

关键词： Content-based Collaborative filtering hybrid recommendation item recommendation Overlap graph algorithm

来源：评论

学校读者我要写书评

暂无评论

graph-theory Based Simplification Techniques for Efficient Biological Network Analysis 3

Graph-theory Based Simplification Techniques for Efficient B...

引用

3rd IEEE International Conference on Big Data Computing Service and Applications (BigDataService)

作者： Ko, Euiseong Kang, Mingon Chang, Hyung Jae Kim, Donghyun Kennesaw State Univ Dept Comp Sci Marietta GA 30060 USA Troy Univ Montgomery Dept Comp Sci Montgomery AL USA

ISBN: (纸本)9781509063185

The recent years have witnessed the remarkable expansion of publicly available biological data in the related research fields. Many researches in these fields often require massive data to be analyzed by utilizing high-throughput sequencing technologies. However, it is very challenging to interpret the data efficiently due to it high complexity. This paper introduces two new graph algorithms which aim to improve the efficiency of the existing methods for biological network data interpretation. In particular, the algorithms focus on the problem of how to simplify gene regulatory networks so that many existing algorithms can efficiently discover important connected components of a biological system in their own context as many times as they need. The performance of the proposed algorithms is compared with each other with gene expression data of glioblastoma brain tumor cancer.

关键词： Biological Network Analysis graph algorithm Greedy algorithm Optimization

来源：评论

学校读者我要写书评

暂无评论

Enumerating Trillion Subgraphs On Distributed Systems

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2018年第6期12卷 71-71页

作者： Park, Ha-Myung Silvestri, Francesco Pagh, Rasmus Chung, Chin-Wan Myaeng, Sung-Hyon Kang, U. Korea Adv Inst Sci & Technol Daejeon South Korea Univ Padua Padua Italy IT Univ Copenhagen Copenhagen Denmark Chongqing Univ Technol Chongqing Peoples R China Seoul Natl Univ Seoul South Korea

How can we find patterns from an enormous graph with billions of vertices and edges? The subgraph enumeration, which is to find patterns from a graph, is an important task for graph data analysis with many applications, including analyzing the social network evolution, measuring the significance of motifs in biological networks, observing the dynamics of Internet, and so on. Especially, the triangle enumeration, a special case of the subgraph enumeration, where the pattern is a triangle, has many applications such as identifying suspicious users in social networks, detecting web spams, and finding communities. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks;however, they suffer from the massive shuffled data resulting in a very long processing time. In this article, we propose scalable methods for enumerating trillion subgraphs on distributed systems. We first propose PTE (Pre-partitioned Triangle Enumeration), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read. We also propose PSE (Pre-partitioned Subgraph Enumeration), a generalized version of PTE for enumerating subgraphs that match an arbitrary query graph. Experimental results show that PTE provides 79 times faster performance than recent distributed algorithms on real-world graphs, and succeeds in enumerating more than 3 trillion triangles on the ClueWeb12 graph with 6.3 billion vertices and 72 billion edges. Furthermore, PSE successfully enumerates 265 trillion clique subgraphs with 4 vertices from a subdomain hyperlink network, showing 47 times faster performance than the state of the art distributed subgraph enumeration algor

关键词： Triangle enumeration subgraph enumeration big data graph algorithm scalable algorithm distributed algorithm network analysis

来源：评论

学校读者我要写书评

暂无评论

Maintaining balanced trees for structured distributed streaming systems

引用

DISCRETE APPLIED MATHEMATICS 2017年 232卷 176-188页

作者： Giroire, F. Modrzejewski, R. Nisse, N. Perennes, S. Univ Nice Sophia Antipolis CNRS I3S UMR 7271 F-06900 Sophia Antipolis France Google Dublin Ireland INRIA Rocquencourt France

In this paper, we propose and analyze a simple local algorithm to balance a tree. The motivation comes from live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. It is thus crucial to be able to repair the diffusion tree to allow an efficient data distribution. In particular, due to bandwidth limitations, an efficient diffusion tree must ensure that node degrees are bounded. Moreover, to minimize the delay of the streaming, the depth of the diffusion tree must also be controlled. We propose here a simple distributed repair algorithm in which each node carries out local operations based on its degree and on the subtree sizes of its children. In a synchronous setting, we first prove that starting from any n-node tree our process converges to a balanced binary tree in O(n(2)) rounds. We then describe a more restrictive model, adding a small extra information to each node, under which we adapt our algorithm to converge in circle minus(n log n) rounds. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Distributed live streaming system graph algorithm Balanced trees Peer-to-peer

来源：评论

学校读者我要写书评

暂无评论

Sigcon: Simplifying a graph Based on Degree Correlation and Clustering Coefficient 19

Sigcon: Simplifying a Graph Based on Degree Correlation and ...

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：