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

parallel algorithms for enumerating closed patterns from multi-relational data

DISCRETE APPLIED MATHEMATICS 2018年 249卷 120-134页

作者： Seki, Hirohisa Nagao, Masahiro Nagoya Inst Technol Dept Comp Sci Showa Ku Nagoya Aichi 4668555 Japan

This paper presents parallel algorithms for enumerating closed patterns from multi relational data. In multi-relational data mining (MRDM), patterns are represented in logical formulae, and involve multiple tables (relations) from a relational database. Since the expressive framework of MRDM makes the task of pattern mining costly compared with the conventional itemset mining, we propose parallel algorithms for computing closed patterns on multi-core processors. In particular, we present new load-balancing strategies which try to fully exploit the task-parallelism intrinsic in the search process of the problem, and give some experimental results, which show the effectiveness of the proposed methods. We then apply our proposed methods to compute closed patterns, a.k.a. concept intents, for binary object-attribute relational data, and show by experiments that the performance of our method is comparable to the existing method. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Multi-relational data mining Formal concept analysis Closed patterns parallel algorithm Load-balancing

来源：评论

学校读者我要写书评

暂无评论

A Fast parallelizable algorithm for Constructing Balanced Binary Search Trees

引用

SN Computer Science 2022年第5期3卷 1-5页

作者： Ruzankin, Pavel S. Sobolev Institute of Mathematics Novosibirsk Russian Federation

We suggest a new non-recursive algorithm for constructing a balanced binary search tree given an array of numbers. The algorithm has O(N) time and O(1) auxiliary memory complexity if the given array of N numbers is sorted. The resulting tree is of minimal height and can be transformed into a complete binary search tree while retaining minimal height with O(log N) time and O(1) auxiliary memory. The algorithm allows simple and effective parallelization resulting in time complexity O((N/ s) + s+ log N) , where s is the number of parallel threads. © 2022, The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd.

关键词： Binary search tree parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Towards Efficient Short-Range Pair Interaction on Sunway Many-Core Architecture

引用

Journal of Computer Science & Technology 2021年第1期36卷 123-139页

作者： Jun-Shi Chen Hong An Wen-Ting Han Zeng Lin Xin Liu School of Computer Science and Technology University of Science and Technology of ChinaHefei 230026China National Research Center of Parallel Computer Engineering and Technology Beijing 100080China

The short-range pair interaction consumes most of the CPU time in molecular dynamics(MD)*** inherent computation sparsity makes it challenging to achieve high-performance kernel on the emerging many-core *** this paper,we present a highly efficient short-range force kernel on the Sunway,a novel many-core architecture with many unique *** parallel efficiency of this algorithm on the Sunway many-core processor is strongly limited by the poor data locality and write *** enhance the data locality,we adopt a super cluster based neighbor list with an appropriate granularity that fits in the local memory of computing *** the absence of a low overhead locking mechanism,using data-privatization force array is a more feasible method to avoid write conflicts,but results in the large overhead of data *** adopt a dual-slice partitioning scheme for both hardware resources and computing tasks,which utilizes the on-chip data communication to reduce data reduction overhead and provide load ***,we exploit the single instruction multiple data(SIMD)parallelism and perform instruction reordering of the force kernel on this many-core *** experimental results show that the optimized force kernel obtains a performance speedup of 226x compared with the reference implementation and achieves 20%of peak flop rate on the Sunway many-core processor.

关键词： molecular dynamics sunway many-core pair interaction parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Sorting of Homomorphic Encrypted Data With k-Way Sorting Network

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2021年 16卷 4389-4404页

作者： Hong, Seungwan Kim, Seunghong Choi, Jiheon Lee, Younho Cheon, Jung Hee Seoul Natl Univ Dept Math Sci Seoul 08826 South Korea Sogang Univ Dept Math Seoul 04107 South Korea SeoulTech ITM Div Dept Ind Engn Seoul 01811 South Korea Seoul Natl Univ CryptoLab Seoul 08826 South Korea

In this study, we propose an efficient sorting method for encrypted data using fully homomorphic encryption (FHE). The proposed method extends the existing 2-way sorting method by applying the k-way sorting network for any prime k to reduce the depth in terms of comparison operation from O(log(2)(2) n) to O(k log(k)(2) n), thereby improving performance for k slightly larger than 2, such as k = 5. We apply this method to approximate FHE which is widely used due to its efficiency of homomorphic arithmetic operations. In order to build up the k-way sorting network, the k-sorter, which sorts k-numbers with a minimal comparison depth, is used as a building block. The approximate homomorphic comparison, which is the only type of comparison working on approximate HIE, cannot he used for the construction of the k-sorter as it is because the result of the comparison is not binary, unlike the comparison in conventional bit-wise FHEs. To overcome this problem, we propose an efficient k-sorter construction utilizing the features of approximate homomorphic comparison. Also, we propose an efficient construction of a k-way sorting network using cryptographic SIMD operations. To use the proposed method most efficiently, we propose an estimation formula that finds the appropriate k that is expected to reduce the total time cost when the parameters of the approximating comparisons and the performance of the operations provided by the approximate FHE are given. We also show the implementation results of the proposed method, and it shows that sorting 5(6) = 15625 data using 5-way sorting network can be about 23.3% faster than sorting 2(14) = 16384 data using 2-way.

关键词： Approximate homomorphic encryption sorting network parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Convergence theorems for solving a system of pseudomonotone variational inequalities using Bregman distance in Banach spaces

引用

BOLLETTINO DELLA UNIONE MATEMATICA ITALIANA 2022年第4期15卷 561-588页

作者： Jolaoso, Lateef Olakunle Aphane, Maggie Raji, Musiliu Tayo Osinuga, Idowu Ademola Olajuwon, Bakai Ishola Sefako Makgatho Hlth Sci Univ Dept Math & Appl Math POB 94 ZA-0204 Pretoria South Africa Fed Univ Agr Dept Math Abeokuta Ogun Nigeria

In this paper, we present two new parallel Bregman projection algorithms for finding a common solution of a system of pseudomonotone variational inequality problems in a real reflexive Banach space. The first algorithm combines a parallel Bregman subgradient extragradient method with the Halpern iterative method for approximating a common solution of variational inequalities in reflexive Banach spaces. The second algorithm involves a parallel Bregman subgradient extragradient method, Halpern iterative method and a line search procedure which aims to avoid the condition of finding prior estimate of the Lipschitz constant of each cost operator. Two strong convergence results were proved under standard assumptions imposed on the cost operators and control sequences. Finally, we provide some numerical experiments to illustrate the behaviour of the sequences generated by the proposed algorithms.

关键词： parallel algorithm Variational inequalities Extragradient method Pseudomonotone Bregman distance Banach space

来源：评论

学校读者我要写书评

暂无评论

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

引用

JOURNAL OF THE ACM 2021年第3期68卷 1–41页

作者： Boroujeni, Mahdi Ehsani, Soheil Ghodsi, Mohammad Hajiaghayi, Mohammadtaghi Seddighin, Saeed Sharif Univ Technol Azadi St Tehran Iran Univ Maryland College Pk MD 20742 USA Toyota Technol Inst Chicago Chicago IL USA Inst Res Fundamental Sci IPM Tehran Iran

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is "one of the biggest unsolved problems in the field of combinatorial pattern matching" [37]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n(1.810)) quantum algorithm that approximates the edit distance within a factor of 3. We further extend this result to an O(n(1.708)) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 1 + epsilon, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

关键词： Edit distance approximation algorithm subquadratic time algorithm quantum algorithm parallel algorithm MapReduce

来源：评论

学校读者我要写书评

暂无评论

CPP11sort: A parallel quicksort based on C plus plus threading

引用

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE 2022年第4期34卷

作者： Langr, Daniel Schovankova, Klara Czech Tech Univ Fac Informat Technol Thakurova 9 Prague 16000 Czech Republic

A new efficient implementation of the multithreaded quicksort algorithm called CPP11sort is presented. This implementation is built exclusively upon the threading primitives of the C++ programming language itself. The performance of CPP11sort is evaluated and compared with its mainstream competitors provided by GNU, Intel, and Microsoft. It is shown that out of the considered implementations, CPP11sort mostly yields the shortest sorting times and is the only one that is portable to any conforming C++ implementation without a need of external libraries or nonstandard compiler extensions. The experimental evaluation with various input data distributions resulted in parallel speedup between 16.1 and 44.2 on a 56-core server and between 6.8 and 14.5 on a 10-core workstation with enabled hyperthreading.

关键词： C plus plus in-place sorting multithreading parallel algorithm parallel sorting quicksort shared memory

来源：评论

学校读者我要写书评

暂无评论

High-Performance Truss Analytics in Arkouda 29

High-Performance Truss Analytics in Arkouda

引用

29th Annual IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC)

作者： Du, Zhihui Patchett, Joseph Rodriguez, Oliver Alvarado Li, Fuhuan Bader, David A. New Jersey Inst Technol Dept Data Sci Newark NJ 07102 USA

ISBN: (纸本)9781665494236

In graph analytics, a truss is a cohesive subgraph based on the number of triangles supporting each edge. It is widely used for community detection applications such as social networks and security analysis, and the performance of truss analytics highly depends on its triangle counting method. This paper proposes a novel triangle counting kernel named Minimum Search (MS). Minimum Search can select two smaller adjacency lists out of three and uses fine-grained parallelism to improve the performance of triangle counting. Then, two basic algorithms, MS-based triangle counting, and MS-based support updating are developed. Based on the novel triangle counting kernel and the two basic algorithms above, three fundamental parallel truss analytics algorithms are designed and implemented to enable different kinds of graph truss analysis. These truss algorithms include an optimized K-Truss algorithm, a Max-Truss algorithm, and a Truss Decomposition algorithm. Moreover, all proposed algorithms have been implemented in the parallel language Chapel and integrated into an open-source framework, Arkouda. Through Arkouda, data scientists can efficiently conduct graph analysis through an easy-to-use Python interface and handle large-scale graph data in powerful back-end computing resources. Experimental results show that the proposed methods can significantly improve the performance of truss analysis on real-world graphs compared with the existing and widely adopted list intersection-based method. The implemented code is publicly available from GitHub (https://***/Bears-R-Us/arkoudanjit).

关键词： K-Truss Triangle Counting Graph Analytics parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

A parallel Symmetric Successive Overrelaxation Method for OVERFLOW

A Parallel Symmetric Successive Overrelaxation Method for OV...

引用

AIAA Aviation Forum and Exposition

作者： Derlaga, Joseph M. Jackson, Charles W. Buning, Pieter G. NASA Langley Res Ctr Computat AeroSci Branch 15 Langley BlvdMS 128 Hampton VA 23681 USA

ISBN: (数字)9781624106101

ISBN: (纸本)9781624106101

The block Jacobi symmetric successive overrelaxation (SSOR) algorithm has been reformulated as a parallelized algorithm for the OVERFLOWstructured, overset grid, computational fluid dynamics flow solver. Simple changes to the flow solver required to implement the algorithm are discussed. A series of test cases are presented that demonstrate how the addition of implicit overset boundaries has improved the robustness and nonlinear convergence characteristics of the flow solver.

关键词： Computational Fluid Dynamics Freestream Conditions Turbulence Models Convection parallel algorithm NACA 0015 Eddy Viscosity Fuselages Boeing

来源：评论

学校读者我要写书评

暂无评论

GPU-Accelerated Fock Matrix Computation with Efficient Reduction

引用

APPLIED SCIENCES-BASEL 2025年第9期15卷 4779-4779页

作者： Tsuji, Satoki Ito, Yasuaki Fujii, Haruto Yokogawa, Nobuya Suzuki, Kanta Nakano, Koji Parque, Victor Kasagi, Akihiko Hiroshima Univ Sch Adv Sci & Engn Higashihiroshima 7398527 Japan Fujitsu Ltd Comp Lab Kawasaki 2118588 Japan

In quantum chemistry, constructing the Fock matrix is essential to compute Coulomb interactions among atoms and electrons and, thus, to determine electron orbitals and densities. In the fundamental framework of quantum chemistry such as the Hartree-Fock method, the iterative computation of the Fock matrix is a dominant process, constituting a critical computational bottleneck. Although the Fock matrix computation has been accelerated by parallel processing using GPUs, the issue of performance degradation due to memory contention remains unresolved. This is due to frequent conflicts of atomic operations accessing the same memory addresses when multiple threads update the Fock matrix elements concurrently. To address this issue, we propose a parallel algorithm that efficiently and suitably distributes the atomic operations;and significantly reduces the memory contention by decomposing the Fock matrix into multiple replicas, allowing each GPU thread to contribute to different replicas. Experimental results using a relevant set/configuration of molecules on an NVIDIA A100 GPU show that our approach achieves up to a 3.75x speedup in Fock matrix computation compared to conventional high-contention approaches. Furthermore, our proposed method can also be readily combined with existing implementations that reduce the number of atomic operations, leading to a 1.98x improvement.

关键词： GPU Fock matrix two-electron repulsion integrals Hartree-Fock method quantum chemistry parallel algorithm memory contention atomic operations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：