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

DHPV: a distributed algorithm for large-scale graph partitioning

JOURNAL OF BIG DATA 2020年第1期7卷 76页

作者： Adoni, Wilfried Yves Hamilton Nahhal, Tarik Krichen, Moez El byed, Abdeltif Assayad, Ismail Hassan II Univ Casablanca LIMSAD Lab Fac Casablanca Morocco Albaha Univ Fac CSIT Al Bahah Saudi Arabia Univ Sfax ReDCAD Lab Sfax Tunisia Hassan II Univ Casablanca ENSEM LIMSAD Lab Casablanca Morocco

Big graphs are part of the movement of "Not Only SQL" databases (also called NoSQL) focusing on the relationships between data, rather than the values themselves. The data is stored in vertices while the edges model the interactions or relationships between these data. They offer flexibility in handling data that is strongly connected to each other. The analysis of a big graph generally involves exploring all of its vertices. Thus, this operation is costly in time and resources because big graphs are generally composed of millions of vertices connected through billions of edges. Consequently, the graph algorithms are expansive compared to the size of the big graph, and are therefore ineffective for data exploration. Thus, partitioning the graph stands out as an efficient and less expensive alternative for exploring a big graph. This technique consists in partitioning the graph into a set of k sub-graphs in order to reduce the complexity of the queries. Nevertheless, it presents many challenges because it is an NP-complete problem. In this article, we present DPHV (Distributed Placement of Hub-Vertices) an efficient parallel and distributed heuristic for large-scale graph partitioning. An application on a real-world graphs demonstrates the feasibility and reliability of our method. The experiments carried on a 10-nodes Spark cluster proved that the proposed methodology achieves significant gain in term of time and outperforms JA-BE-JA, Greedy, DFEP.

关键词： Big graph Large-scale networks k-Partition graph partitioning algorithms Distributed computing graphX

来源：评论

学校读者我要写书评

暂无评论

VSCT algorithm for graph partitioning based on volume, size, cuts and time

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2023年第3期38卷 181-197页

作者： Sakouhi, Chayma Khaldi, Abir Ghezala, Henda Ben Univ Manouba Natl Sch Comp Sci RIADI Lab Manouba Tunisia Univ Manouba Comp Sci Natl Sch Comp Sci RIADI Lab Manouba 8100 Tunisia

Dealing with large-scale graphs requires an efficient graph partitioner that produces balanced partitions with fewer cut edges/vertices in a reasonable amount of time. Despite several algorithms that have been proposed, it is still insufficient. Even with the continuous growth of graph volume, they do not consider the graph volume during graph partitioning. Therefore, these algorithms generate an imbalanced workload. We propose a graph partitioner algorithm VSCT based essentially on four key metrics: Volume, Size, Cuts, and Time to maintain high-quality graph partitioning. Using real-world datasets, we show that VSCT performs an efficient partitioning quality against the existing graph partitioning algorithms.

关键词： graph partitioning algorithms distributed graph processing systems volume size cuts time

来源：评论

学校读者我要写书评

暂无评论

Binomial Distribution based K-means for graph partitioning Approach in Partially Reconfigurable Computing system 29

Binomial Distribution based K-means for Graph Partitioning A...

引用

29th Iranian Conference on Electrical Engineering (ICEE)

作者： Asgari, Zahra Mastoori, Maryam Sadat Iran Univ Sci & Technol Sch Elect Engn Tehran Iran

ISBN: (纸本)9781665433655

graph partitioning algorithms have been utilized to execute complex applications, where there is no enough space to run the whole application once, like in limited reconfigurable computing resources. If we have found an "optimal" clustering of a data set, it can be proved that optimal partitioning can be achieved. K-means based algorithms are widely used to partition subjects where there is no information about the number of clusters. A vital issue in the mentioned method is how to define a good centroid, which has the principal role in "good" clustering. In this paper, we introduced a new way to determine purposive centroids, based on Binomial Distribution to reduce the risk of randomly seeds selection, Elbow Diagram to achieve the optimum number of clusters, and finally, Bin Packing to classify nodes in defined clusters with considering Utilization Factor (UF) due to the limited area of Run Space. The proposed algorithm, called Binomial Distribution based K-means (BDK), is compared with common graph partitioning algorithms like Simulated Annealing Algorithm (SA), Density K-means (DK), and a link elimination partitioning with different scenarios such as simple and complex applications. The concluding results show that the proposed algorithm decreases the error of partitioning by 24% compared to the other clustering techniques. On the other hand, the Quality Factor (QF) is increased 41% in this way. Execution Time (EX.T) to achieve the required number of clusters is reduced significantly.

关键词： Reconfigurable computing graph partitioning algorithms Unsupervised clustering K-means algorithm Binomial Distribution based K-means Bin packing

来源：评论

学校读者我要写书评

暂无评论

A graph BASED DAVIDSON ALGORITHM FOR THE graph partitioning PROBLEM

引用

International Journal of Foundations of Computer Science 1999年第2期10卷 225-246页

作者： MICHAEL HOLZRICHTER SUELY OLIVEIRA Sandia National Laboratories Albuquerque NM 5800 USA Dept. of Computer Science The University of Iowa Iowa City IA 52242 USA

The problem of partitioning a graph such that the number of edges incident to vertices in different partitions is minimized, arises in many contexts. Some examples include its recursive application for minimizing fill-in in matrix factorizations and load-balancing for parallel algorithms. Spectral graph partitioning algorithms partition a graph using the eigenvector associated with the second smallest eigenvalue of a matrix called the graph Laplacian . The focus of this paper is the use graph theory to compute this eigenvector more quickly.

关键词： graph partitioning algorithms spectral algorithms Fiedler vector eigenvalue solvers

来源：评论

学校读者我要写书评

暂无评论

partitioning approach oriented to the decentralised predictive control of large-scale systems

引用

JOURNAL OF PROCESS CONTROL 2011年第5期21卷 775-786页

作者： Ocampo-Martinez, C. Bovo, S. Puig, V. Inst Robot & Informat Ind CSIC UPC Barcelona 08028 Spain

In this paper, a partitioning approach for large-scale systems based on graph-theory is presented. The algorithm starts with the translation of the system model into a graph representation. Once the system graph is obtained, the problem of graph partitioning is then solved. The resultant partition consists in a set of non-overlapping subgraphs whose number of vertices is as similar as possible and the number of interconnecting edges between them is minimal. To achieve this goal, the proposed algorithm applies a set of procedures based on identifying the highly connected subgraphs with balanced number of internal and external connections. In order to illustrate the use and application of the proposed partitioning approach, it is used to decompose a dynamical model of the Barcelona drinking water network (DWN). Moreover, a hierarchical-like DMPC strategy is designed and applied over the resultant set of partitions in order to assess the closed-loop performance. Results obtained when used several simulation scenarios show the effectiveness of both the partitioning approach and the DMPC strategy in terms of the reduced computational burden and, at the same time, of the admissible loss of performance in contrast to a centralised MPC strategy. (C) 2010 Elsevier Ltd. All rights reserved.

关键词： graph partitioning algorithms Decentralised MPC Large-scale networked systems Drinking water networks

来源：评论

学校读者我要写书评

暂无评论

Image segmentation with ratio cut

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2003年第6期25卷 675-690页

作者： Wang, S Siskind, JM Univ S Carolina Dept Comp Sci & Engn Columbia SC 29208 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA

This paper proposes anew cost function, cut ratio, for segmenting images using graph-based methods. The cut ratio is defined as the ratio of the corresponding sums of two different weights of edges along the cut boundary and models the mean affinity between the segments separated by the boundary per unit boundary length. This new cost function allows the image perimeter to be segmented, guarantees that the segments produced by bipartitioning are connected, and does not introduce a size, shape, smoothness, or boundary-length bias. The latter allows it to produce segmentations where boundaries are aligned with image edges. Furthermore, the cut-ratio cost function allows efficient iterated region-based segmentation as well as pixel-based segmentation. These properties may be useful for some image-segmentation applications. While the problem of finding a minimum ratio cut in an arbitrary graph is NP-hard, one can find a minimum ratio cut in the connected planar graphs that arise during image segmentation in polynomial time. While the cut ratio, alone, is not sufficient as a baseline method for image segmentation, it forms a good basis for an extended method of image segmentation when combined with a small number of standard techniques. We present an implemented algorithm for finding a minimum ratio cut, prove its correctness, discuss its application to image segmentation, and present the results of segmenting a number of medical and natural images using our techniques.

关键词： graph partitioning algorithms cut ratio cycle ratio perfect matching perceptual organization edge detection image segmentation machine vision

来源：评论

学校读者我要写书评

暂无评论

PANCODE: Multilevel partitioning of Neural Networks for Constrained Internet-of-Things Devices

引用

IEEE ACCESS 2023年 11卷 2058-2077页

作者： de Oliveira, Fabiola Martins Campos Bittencourt, Luiz Fernando Kamienski, Carlos Alberto Borin, Edson Fed Univ ABC Ctr Math Comp & Cognit BR-09210580 Santo Andre SP Brazil Univ Estadual Campinas Inst Comp BR-13083852 Campinas SP Brazil

The increasing number of Internet-of-Things (IoT) devices will generate unprecedented data in the upcoming years. Fog computing may prevent the saturation of the network infrastructure by processing data at the edge or within these devices. Consequently, the machine intelligence built almost exclusively on the cloud can be scattered to the edge devices. While deep learning techniques can adequately process IoT-massive data volumes, their high resource-demanding nature poses a trade-off for execution on resource-constrained devices. This paper proposes and evaluates the performance of the partitioning Networks for COnstrained DEvices (PANCODE), a novel algorithm that employs a multilevel approach to partition large convolutional neural networks for distributed execution on constrained IoT devices. Experimental results with the LeNet and AlexNet models show that our algorithm can produce partitionings that achieve up to 2173.53 times more inferences per second than the Best Fit algorithm and up to 1.37 times less communication than the second-best approach. We also show that the METIS state-of-the-art framework only produces invalid partitionings in more constrained setups. The results indicate that our algorithm achieves higher inference rates and low communication costs in convolutional neural networks distributed among constrained and exceptionally very constrained devices.

关键词： Convolutional neural networks distributed systems fog computing graph partitioning algorithms Internet of Things performance evaluation

来源：评论

学校读者我要写书评

暂无评论

2PSIM: Two Phase Service Identifying Method

2PSIM: Two Phase Service Identifying Method

引用

Confederated International Workshops and Posters: EI2N plus NSF ICE, ICSP plus INBAST, ISDE, ORM, OTMA, SWWS plus MONET plus SeDeS, and VADER

作者： Nikravesh, Ali Shams, Fereidoon Farokhi, Soodeh Ghaffari, Amir Shahid Beheshti Univ Elect & Comp Engn Fac Tehran Iran

ISBN: (纸本)9783642251054

Service identification - as the first step of service-oriented modeling holds the main emphasis on the modeling process and has a broad influence on the system development. Selecting appropriate service identification method is essential for prosperity of any service-oriented architecture project. Automation, utilizing middle-out strategy, and quality assess of services, are three important criteria in evaluation of service identification methods. Existing methods mostly ignore automation principles. Meanwhile a few automated and semi-automated methods use top-down strategy to identify services and ignore existing assets of enterprise. Moreover these methods do not take all the quality metrics into account. This paper proposes a novel semi-automated method called 2PSIM (Two-Phase Service Identification Method) which uses graph partitioning algorithm to identify services based on enterprise business processes as well business entity models. 2PSIM utilizes middle-out strategy and tries to identify reusable services with proper granularity and acceptable level of cohesion and coupling.

关键词： Service-Oriented Architecture Service-Oriented Modeling Service Identification graph partitioning algorithms

来源：评论

学校读者我要写书评

暂无评论

On partitioning two dimensional finite difference meshes for distributed memory parallel computers

On partitioning two dimensional finite difference meshes for...

引用

22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP)

作者： Grandjean, Anael Ucar, Bora Ecole Normale Super Lyon UMR CNRS INRIA UCBL F-69364 Lyon France Ecole Normale Super Lyon CNRS F-69364 Lyon France

ISBN: (纸本)9781479927289

We investigate the problem of partitioning finite difference meshes in two dimensions among the processors of a parallel computer. The objective is to achieve a perfect load balance while minimizing the communication cost. There are well-known graph, hypergraph, and geometry-based partitioning algorithms for this problem. The known geometric algorithms have linear running time and obtain the best results for very special mesh sizes and processor numbers. We propose another geometric algorithm. The proposed algorithm is linear;is applicable to much more cases than some well-known alternatives;obtains better results than the graph partitioning algorithms;obtains better results than the hypergraph partitioning algorithms almost always. Our algorithm also obtains better results than a known asymptotically-optimal algorithm for some small number of processors. We also catalog related theoretical results.

关键词： distributed processing finite difference methods graph theory mesh generation resource allocation distributed memory parallel computers geometry-based partitioning algorithms graph partitioning algorithms hypergraph partitioning algorithms linear running time perfect load balance two dimensional finite difference meshes Approximation algorithms Diamonds Measurement partitioning algorithms Program processors Shape Standards

来源：评论

学校读者我要写书评

暂无评论

Achieving Enhanced Performance Combining Checkpointing and Dynamic State partitioning 35

Achieving Enhanced Performance Combining Checkpointing and D...

引用

35th IEEE International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)

作者： Goulart, Henrique S. Trombeta, Joao Franco, Alvaro Mendizabal, Odorico M. Univ Fed Santa Catarina UFSC Programa Posgrad Computacio PPGCC Dept Informat & Estat Florianopolis SC Brazil

ISBN: (纸本)9798350305487

Fault-tolerant systems rely on recovery techniques to enhance system resilience. In this regard, checkpointing procedures periodically take snapshots of the system state during failure-free operation, enabling recovery processes to resume from a previously saved, consistent state. Saving checkpoints, however, is costly, as it must synchronize snapshots with the processing of incoming requests to avoid inconsistency. One way to speed up checkpointing is to partition the service state, allowing a parallel checkpoint procedure to operate independently on each partition. State partitioning can also improve throughput by increasing parallelism in request processing. However, variations in the data access pattern over time can result in unbalanced partitions, posing a challenge to achieving optimal performance. In this paper, aiming to improve both checkpointing and overall system performance, we combine parallel checkpointing with a dynamic graph-based repartitioning algorithm. This work formalizes the optimization problem and presents a detailed performance assessment of the proposed approach. The experimental evaluation highlights the benefits of parallel checkpointing and emphasizes the performance gains achieved with repartitioning under realistic workloads. Comparing a cost-effective round-robin partitioning approach with our dynamic method, we examine the degree of execution parallelism achieved by checkpointing threads and the influence of repartitioning strategies on checkpoint performance. Although the rebalancing of state partitions incurs a cost, it comes for free in our technique since it takes advantage of processing idleness during the snapshot-taking process.

关键词： fault tolerance checkpoint/restore state partitioning graph partitioning algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：