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

32nd Conference on Learning Theory (COLT) part of the ACM Federated Computing Research Conference

作者： Diakonikolas, Jelena Guzman, Cristobal Univ Calif Berkeley Berkeley CA 94720 USA Pontificia Univ Catolica Chile Millennium Nucleus Ctr Discovery Struct Complex D Santiago Chile

We study the question of whether parallelization in the exploration of the feasible set can be used to speed up convex optimization, in the local oracle model of computation. We show that the answer is negative for both deterministic and randomized algorithms applied to essentially any of the interesting geometries and nonsmooth, weakly-smooth, or smooth objective functions. In particular, we show that it is not possible to obtain a polylogarithmic (in the sequential complexity of the problem) number of parallel rounds with a polynomial (in the dimension) number of queries per round. In the majority of these settings and when the dimension of the space is polynomial in the inverse target accuracy, our lower bounds match the oracle complexity of sequential convex optimization, up to at most a logarithmic factor in the dimension, which makes them (nearly) tight. Prior to our work, lower bounds for parallel convex optimization algorithms were only known in a small fraction of the settings considered in this paper, mainly applying to Euclidean (l(2)) and l(infinity) spaces. Our work provides a more general and streamlined approach for proving lower bounds in the setting of parallel convex optimization.

关键词： Lower bounds convex optimization parallel algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

CUDA-DClust+: Revisiting Early GPU-Accelerated DBSCAN Clustering Designs

CUDA-DClust+: Revisiting Early GPU-Accelerated DBSCAN Cluste...

引用

International Conference on High Performance Computing

作者： Madhav Poudel Michael Gowanlock School of Informatics Computing and Cyber Systems Northern Arizona University Flagstaff AZ U.S.A.

ISBN: (纸本)9781665410175

Density-based clustering algorithms are widely used unsupervised data mining techniques to find the clusters of points in dense regions that are separated by low-density regions. This algorithm is inherently sequential and has limitations in its parallel implementation. There have been several parallel algorithms presented in the literature for multi-core CPUs and many-core GPUs. One such algorithm for the GPU is CUDA-DCLUST. In this paper, we propose a new GPU-accelerated DBSCAN algorithm with several optimizations. In comparison to prior work, our algorithm, Cuda-dclust+:(i) computes the indexing structure on the GPU, (ii) uses kernel fusion to combine the index search and cluster expansion kernels, which reduces communication and synchronization overhead with the host, and (iii) seed list management control is primarily given to the GPU rather than the CPU, which further decreases CPU-GPU communication overhead. We compare our algorithm to three state-of-the-art parallel algorithms in the literature on six real-world datasets. We find that our algorithm achieves a speedup of up to ~23x over the fastest GPU algorithm.

关键词： High performance computing Conferences Clustering algorithms Graphics processing units Synchronization Data mining parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A parallel Algorithm for Subgraph Isomorphism 1

引用

12th IAPR-TC15 Workshop on Graph-Based Representations in Pattern Recognition (GbRPR)

作者： Carletti, Vincenzo Foggia, Pasquale Ritrovato, Pierluigi Vento, Mario Vigilante, Vincenzo Univ Salerno Dept Informat Engn Elect Engn & Appl Math Fisciano Italy

ISBN: (数字)9783030200817

ISBN: (纸本)9783030200817;9783030200800

In different application fields, such as biology, databases, social networks and so on, graphs are a widely adopted structure to represent the data. In these fields, a relevant problem is the detection and the localization of structural patterns within very large graphs;such a problem, formalized as subgraph isomorphism, has been proven to be NP-Complete in the general case. Moreover, the continuously growing size of the graphs to face, actually of hundred thousands of nodes, is making the problem even more challenging also for the most efficient algorithms in the state of the art, requiring days or weeks of computational time. This huge amount of time is also consequence of the fact that most of the algorithms do not exploit any kind of parallelism, even if the problem is suitable to be solved adopting parallel approaches. In this paper we present a new parallel algorithm for subgraph isomorphism, namely VF3P, based on a redesign of the well known algorithm VF3. The effectiveness of VF3P has been experimentally proven on a publicly available dataset of very large graphs, confirming that the algorithm is able to efficiently scale w.r.t. the number of used CPUs without affecting the memory usage.

关键词： Exact graph matching Subgraph isomorphism parallel algorithms VF3

来源：评论

学校读者我要写书评

暂无评论

Scalable Sequence Clustering for Large-Scale Immune Repertoire Analysis

Scalable Sequence Clustering for Large-Scale Immune Repertoi...

引用

IEEE International Conference on Big Data

作者： Prem Bhusal A K M Mubashwir Alam Keke Chen Ning Jiang Jun Xiao Wright State University Dayton OH USA Marquette University Milwaukee WI USA University of Pennsylvania Philadelphia PA USA ImmuDX LLC Austin TX USA

ISBN: (纸本)9781665445993

The development of the next-generation sequencing technology has enabled systems immunology researchers to conduct detailed immune repertoire analysis at the molecular level that allows researchers to understand the healthiness of a patient’s immune system. Recent studies have shown that the single-linkage clustering algorithm can give the best results for B cell clonality analysis – a critical type of immune repertoire sequencing (IR-Seq) analysis. Large sequence datasets (e.g., millions of sequences) are being collected to comprehensively understand how a specific person’s immune system evolves over different stages of disease development. However, the classical single-linkage clustering algorithm does not scale well to such large sequence datasets. Surprisingly, no study has been done to address this scalability issue for immunology research and development. We study three different strategies to scale up the single-linkage algorithm for sequence data. They include (1) the approximate single-linkage algorithm enhanced with the non-Euclidean indexing methods, (2) the Spark-based single-linkage algorithm (SparkMST) that was originally designed for vector data and now modified for sequence data, and (3) a new tree-based sequence summarization approach – SCT that aims to reduce the data for single-linkage clustering with well-preserved clustering *** have implemented these approaches and experimented with real sequence datasets for B cell clonality analysis. (1) The index-enhanced hierarchical clustering algorithm (e.g., VPT-HC using the Vantage-Point tree for indexing) preserves the clustering quality very well while significantly reducing the time complexity. (2) The SCT approach serving as a preprocessing step can effectively reduce data size for clustering. The overall clustering, SCT followed by VPT-HC, is the fastest among the evaluated single-machine algorithms. However, this approach also slightly affects the clustering quality. (3) The SparkMST parall

关键词： Couplings Sequential analysis Scalability Clustering algorithms Big Data Approximation algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A High Performance Computing Method for Noise Cross-Correlation Functions of Seismic Data

A High Performance Computing Method for Noise Cross-Correlat...

引用

IEEE International Conference on Big Data and Cloud Computing (BdCloud)

作者： Junwei Zhou Qian Wei Chao Wu Guangzhong Sun School of Earth and Space Sciences University of Science and Technology of China School of Physical Sciences University of Science and Technology of China Network and Information Center University of Science and Technology of China School of Computer Science and Technology University of Science and Technology of China

Calculation of noise cross-correlation functions (NCF) plays an important role in ambient noise imaging which is a vital seismic method to obtain Earth inner structures. To raise the resolution of the imaging results, we need more seismic data for imaging. However, as the size of seismic data increases, the serial algorithm for NCF calculation becomes much more time-consuming. Thus, how to accelerate the NCF calculation becomes a key problem in ambient noise imaging. Based on the analysis of serial algorithm, we proposed a new parallel algorithm for NCF calculation using NVIDIA GPU platform. In addition, we improved reading and writing strategy to reduce I/O consumption. Experimental results on real seismic data show the effectiveness of our method. The parallel program achives about 1861 times speedup.

关键词： Earth Image resolution High performance computing Imaging Graphics processing units Writing parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Communication-efficient distributed cooperative learning with compressed beliefs

arXiv

引用

arXiv 2021年

作者： Toghani, Mohammad Taha Uribe, César A. Department of Electrical and Computer Engineering Rice University HoustonTX United States

We study the problem of distributed cooperative learning, where a group of agents seeks to agree on a set of hypotheses that best describes a sequence of private observations. In the scenario where the set of hypotheses is large, we propose a belief update rule where agents share compressed (either sparse or quantized) beliefs with an arbitrary positive compression rate. Our algorithm leverages a unified communication rule that enables agents to access wide-ranging compression operators as black-box modules. We prove the almost sure asymptotic exponential convergence of beliefs around the set of optimal hypotheses. Additionally, we show a non-asymptotic, explicit, and linear concentration rate in probability of the beliefs on the optimal hypothesis set. We provide numerical experiments to illustrate the communication benefits of our method. The simulation results show that the number of transmitted bits can be reduced to 5 − 10% of the non-compressed method in the studied scenarios. Copyright © 2021, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A Distributed Algorithm for Overlapped Community Detection in Large-Scale Networks

A Distributed Algorithm for Overlapped Community Detection i...

引用

International Communication Systems and Networks and Workshops, COMSNETS

作者： Dibakar Saha Partha Sarathi Mandal Indian Institute of Technology Guwahati

ISBN: (数字)9781728191270

ISBN: (纸本)9781728191287

Overlapped community detection in social networks has become an important research area with the increasing popularity and complexity of the networks. Most of the existing solutions are either centralized or parallel algorithms, which are computationally intensive - require complete knowledge of the entire network. But it isn't easy to collect entire network data because the size of the actual network may be prohibitively large. It may result from either privacy concerns (users of a social network may be unwilling to reveal their social links) or technological impediments (implementation of an efficient web crawler). Performing in-network computation solves both problems utilizing the computational capability of the individual nodes of the network. Simultaneously, nodes communicate and share data with their neighbours via message passing, which may go a long way toward mitigating individual nodes' privacy concerns in the network. All the concerns mentioned above motivated us to design a decentralized or distributed technique to detect overlapped communities in a large-scale network. It is desirable because this technique does not offer a single point of failure, and the system as a whole can continue to function even when many of the nodes fail. To overcome the disadvantages of the existing solutions, in this paper, we address the overlapped community detection problem for large-scale networks. We present an efficient distributed algorithm, named DOCD, to identify the overlapped communities in the network. The efficiency of DOCD algorithm is verified with extensive simulation study on some networks such as, Dolphin, Zachary karate club, Football club, and Facebook ego networks. We show that DOCD algorithm is capable of keeping the asymptotically same results with the existing classical centralized algorithms [1]-[5] in terms of community modularity and the number of identified communities. The DOCD algorithm can also efficiently identify the overlapped nodes and ove

关键词： Privacy Social networking (online) Heuristic algorithms Complexity theory Distributed algorithms parallel algorithms Sports

来源：评论

学校读者我要写书评

暂无评论

A Distributed Multifactorial Particle Swarm Optimization Approach

TechRxiv

引用

TechRxiv 2021年

作者： Aboud, Ahlem Rokbani, Nizar Mirjalili, Seyedali Qahtani, Abdulrahman M. Almutiry, Omar Dhahri, Habib Alimi, Adel M. University of Sousse ISITCom Sousse4011 Tunisia BP 1173 Sfax3038 Tunisia High Institute of Applied Science and technolgy of Sousse University of Sousse Tunisia Department of Electrical and Electronic Engineering Science Faculty of Engineering and the Built Environment University of Johannesburg South Africa Centre for Artificial Intelligence Research and Optimisation Torrens University Australia Brisbane Australia Yonsei Frontier Lab Yonsei University Korea Republic of Department of Computer Science College of Computers and Information Technology Taif University P.O.Box. 11099 Taif21944 Saudi Arabia College of Applied Computer Science King Saud University Riyadh Saudi Arabia

Multifactorial Optimization (MFO) and Evolutionary Transfer Optimization (ETO) are new optimization challenging paradigms for which the multi-Objective Particle Swarm Optimization system (MOPSO) may be interesting despite limitations. MOPSO has been widely used in static/dynamic multi-objective optimization problems, while its potentials for multi-task optimization are not completely unveiled. This paper proposes a new Distributed Multifactorial Particle Swarm Optimization algorithm (DMFPSO) for multi-task optimization. This new system has a distributed architecture on a set of sub-swarms that are dynamically constructed based on the number of optimization tasks affected by each particle skill factor. DMFPSO is designed to deal with the issues of handling convergence and diversity concepts separately. DMFPSO uses Beta function to provide two optimized profiles with a dynamic switching behaviour. The first profile, Beta-1, is used for the exploration which aims to explore the search space toward potential solutions, while the second Beta-2 function is used for convergence enhancement. This new system is tested on 36 benchmarks provided by the CEC’2021 Evolutionary Transfer Multi-Objective Optimization Competition. Comparatives with the state-of-the-art methods are done using the Inverted General Distance (IGD) and Mean Inverted General Distance (MIGD) metrics. Based on the MSS metric, this proposal has the best results on most tested problems. © 2021, CC BY.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Trade-Off Analysis Between parallelism and Accuracy of SLIC on Apache Spark

Trade-Off Analysis Between Parallelism and Accuracy of SLIC ...

引用

International Conference on Big Data and Smart Computing (BIGCOMP)

作者： Gang-Min Park Yong Seok Heo Hyuk-Yoon Kwon Seoul National University of Science and Technology Seoul Republic of Korea Ajou University Suwon Republic of Korea

ISBN: (数字)9781728189246

ISBN: (纸本)9781728189253

In this paper, we present a parallel algorithm for SLIC on Apache Spark, which we call PSLIC-on-Spark. To this purpose, we have extended the original SLIC algorithm to use the operations in Apache Spark, supporting its parallel processing on multiple executors in the Apache Spark cluster. Then, we analyze the trade-off relationship of PSLIC-on-Spark between its processing speed and accuracy due to partitioning of the original image data sets. Especially, we identify two limitations in PSLIC-on-Spark, which degrade the accuracy of the original SLIC. Through experiments, we verify the trade-off relationship. Specifically, we show that PSLIC-on-Spark using 8 CPU cores reduces the processing time of SLIC by 2. 24~2.93 times while it reduces the boundary recall (BR) of SLIC by 1. 54~6.32 % and increases under-segmentation error (UE) by 1. 79~6.2 %. In contrast, PSLIC-on-Spark using 2 CPU cores reduces the processing time of SLIC by 1.38~1.45 times while it reduces the BR of SLIC by 0. 28~1.5 %, and increases UE by 0. 25~1.77 %. We also verify the effectiveness of PSLIC-on-Spark to deal with a large-scale image by showing that the processing speed of PSLIC-on-Spark becomes much more efficient as the image size becomes large. Specifically, compared to the original SLIC, the proposed SLIC-on-Spark reduces its processing time by 2.23 times for the image of 480×320 pixels and by 5.59 times for the image of 2002×1335 pixels, respectively.

关键词： Scalability Conferences Clustering algorithms Memory Cluster computing Partitioning algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

BIPARTITE PERFECT MATCHING IS IN QUASI-NC

引用

SIAM JOURNAL ON COMPUTING 2021年第3期50卷 STOC16-218-STOC16-235页

作者： Fenner, Stephen Gurjar, Rohit Thierauf, Thomas Univ South Carolina Dept Comp Sci & Engn Columbia SC 29208 USA CALTECH Ctr Math Informat Pasadena CA 91125 USA Aalen Univ Dept Elect Engn & Comp Sci D-73430 Aalen Germany

We show that the bipartite perfect matching problem is in quasi-NC2. That is, it has uniform circuits of quasi-polynomial size n(O(log n)), and O(log(2) n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

关键词： graph matching parallel complexity derandomization quasi-NC perfect matching bipartite graphs parallel algorithms Isolation Lemma matching polytope

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：