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

International eConference on Computer and Knowledge Engineering (ICCKE)

作者： Rahele Mohammadi Mahmoud Naghibzadeh Abdorreza Savadi Dept. of Computer Engineering Ferdowsi University of Mashhad Mashhad Iran

ISBN: (数字)9798331511272

ISBN: (纸本)9798331511289

In today's rapidly advancing field of biomedical research, the demand for swift and accurate identification of mutations within biological sequences, including proteins and genomes, is essential for effective disease diagnosis and treatment. Within the realm of protein sequence analysis, recurring patterns known as motifs play a crucial role. These motifs, whether of fixed or variable lengths, often signify essential structural or functional features such as transcription factor binding sites or protein-protein interaction interfaces. Over time, several methods have emerged for detecting motifs within protein datasets. Among these, our previous work introduced the Tree-based Fast Exact Motif (TFEM) algorithm. Unlike some contemporary techniques like Sensitive Thorough Rapid Enriched Motif Elicitation (STREME), Multiple EM for Motif Elicitation (MEME), and Discriminative Regular Expression Motif Elicitation (DREME), TFEM demonstrated superior efficiency in accurately identifying motifs. However, the computational complexity of TFEM presents challenges. With a time complexity of O (n20 k ), where ‘n’ denotes the number of sequences in the input set and ‘k’ signifies the length of the motif under investigation, the algorithm's performance is heavily influenced by the size of the input set. To address this challenge, we propose leveraging CPU parallelization techniques, specifically Open-MP programming, to optimize the execution time of the TFEM algorithm. The evaluation results showed that parallelization in large datasets can reduce execution time up to approximately half compared to the serial algorithm.

关键词： Knowledge engineering Protein engineering Accuracy Genomics Programming Parallel processing approximation algorithms Protein sequence Medical diagnosis Time complexity

来源：评论

学校读者我要写书评

暂无评论

On ML Decoding of Binary Cyclic-gap Constant Weight Codes

On ML Decoding of Binary Cyclic-gap Constant Weight Codes

引用

IEEE International Symposium on Information Theory

作者： Birenjith Sasidharan Emanuele Viterbo Son Hoang Dau Monash University RMIT University

ISBN: (数字)9798350382846

ISBN: (纸本)9798350382853

A family of $(n=2^{\ell}.M=2^{k_{\ell}}\ . \ d=2)$ , binary constant-weight codes for any positive integer $\ell > 3, k_{\ell}= \displaystyle \frac{\ell(\ell+1)}{9}-1$ was recently proposed in literature [1]. As infor-mation is encoded in the gaps (cyclically counted) between successive 1 's, we refer to these codes as cyclic-gap constant weight codes denoted by $C_{G}[\ell$ . These codes admit very low-complexity algorithms for mapping and demapping between message and codeword vectors, fully eliminating the need for costly computations of binomial coefficients. In this paper, we study maximum-likelihood (ML) decoding of these codes under additive white Gaussian noise channels. Since the minimum distance of the code $d=2$ , hard-decision decoders can not correct errors. Motivated by the error-correcting capability of soft-decision Wagner-rule decoder for single-parity-check codes, we derive an ML decoder for $C_{G}[\ell$ . We also derive a low-complexity approximation of the ML decoder with a time-complexity of $O(n\log n^{\backslash },$ . The algorithm is based on a novel technique of traversal through the Hasse diagram of a partially ordered set of all ℓ-subsets of $\{1, 2, \ldots, n\}$ in a breadth-first manner. Our approach is applicable to decoding of any binary constant-weight code and therefore is of general interest. We simulate the performance of the low-complexity decoder for the $(8, 32, 2)$ code $C_{G}$ [3] and show that it performs almost similar to ML when a parameter $\lambda_{\mathrm{m}\mathrm{m}}$ (that determines how far to traverse in the Hasse diagram) is taken to be 3. We also show by simulation that it performs better than a comparable $[8, 5, 2]$ linear code under ML decoding.

关键词： Codes Linear codes approximation algorithms Vectors Maximum likelihood decoding

来源：评论

学校读者我要写书评

暂无评论

FPGA-Based Accelerator Implementation for Naive String Matching Algorithm

FPGA-Based Accelerator Implementation for Naive String Match...

引用

IEEE International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)

作者： Yun-Cheng Wu Sun-Ting Lin Department of Electronic Engineering National Kaohsiung Normal University Kaohsiung Taiwan

ISBN: (数字)9798350389210

ISBN: (纸本)9798350389227

String matching is time-consuming in data search applications, especially with extensive data and many users. This paper demonstrates the performance of hardware acceleration by showcasing the processing speed of the Naive string match algorithm on a hardware platform. We design an algorithm accelerator on the Altera DE2-115 FPGA development board. The results indicate that executing computations on an FPGA yields more than 78 times faster than performing the same functions using the Python language on a CPU.

关键词： Data integrity Signal processing algorithms Signal processing approximation algorithms Throughput Data models Service-oriented architecture Time complexity Field programmable gate arrays Hardware acceleration

来源：评论

学校读者我要写书评

暂无评论

Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions

arXiv

引用

arXiv 2024年

作者： Grandoni, Fabrizio Husić, Edin Mari, Mathieu Tinguely, Antoine IDSIA USI-SUPSI Switzerland LIRMM University of Montpellier CNRS Montpellier France

In the maximum independent set of convex polygons problem, we are given a set of n convex polygons in the plane with the objective of selecting a maximum cardinality subset of non-overlapping polygons. Here we study a special case of the problem where the edges of the polygons can take at most d fixed directions. We present an 8d/3-approximation algorithm for this problem running in time O((nd)O(d4d)). The previous-best polynomial-time approximation (for constant d) was a classical nΕ approximation by Fox and Pach [SODA’11] that has recently been improved to a OPTΕ-approximation algorithm by Cslovjecsek, Pilipczuk and Węgrzycki [SODA’24], which also extends to an arbitrary set of convex polygons. Our result builds on, and generalizes the recent constant factor approximation algorithms for the maximum independent set of axis-parallel rectangles problem (which is a special case of our problem with d = 2) by Mitchell [FOCS’21] and Gálvez, Khan, Mari, Mömke, Reddy, and Wiese [SODA’22]. © 2024, CC BY.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Quasi-Linear Size PCPs with Small Soundness from HDX

arXiv

引用

arXiv 2024年

作者： Bafna, Mitali Minzer, Dor Vyas, Nikhil Department of Mathematics Massachusetts Institute of Technology United States SEAS Harvard University United States

We construct 2-query, quasi-linear sized probabilistically checkable proofs (PCPs) with arbitrarily small constant soundness, improving upon Dinur's 2-query quasi-linear size PCPs with soundness 1 − Ω(1). As an immediate corollary, we get that under the exponential time hypothesis, for all Ε > 0 no approximation algorithm for 3-SAT can obtain an approximation ratio of 7/8 + Ε in time 2n/logC n, where C is a constant depending on Ε. Our result builds on a recent line of works showing the existence of linear sized direct product testers with small soundness [BM24, DD24a, BLM24, DD24b, DDL24]. The main new ingredient in our proof is a technique that embeds a given PCP construction into a PCP on a prescribed graph, provided that the latter is a graph underlying a sufficiently good high-dimensional expander. Towards this end, we use ideas from fault-tolerant distributed computing, and more precisely from the literature of the almost everywhere agreement problem [DPPU86, Upf92, CGO10, CGO12, JRV20]. We show that graphs underlying HDXs admit routing protocols that are tolerant to adversarial edge corruptions, and in doing so we also improve the state of the art in this line of work. Our PCP construction requires variants of the aforementioned direct product testers with polylogarithmic degree. The existence and constructability of these variants is shown in an appendix by Zhiwei Yun. Copyright © 2024, The Authors. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Towards Distributed 2-approximation Steiner Minimal Trees in Billion-edge Graphs

Towards Distributed 2-Approximation Steiner Minimal Trees in...

引用

International Symposium on Parallel and Distributed Processing (IPDPS)

作者： Tahsin Reza Geoffrey Sanders Roger Pearce Lawrence Livermore National Laboratory (LLNL) Center for Applied Scientific Computing (CASC)

Given an edge-weighted graph and a set of known seed vertices of interest, a network scientist often desires to understand the graph relationships to explain connections between the seed vertices. If the size of the seed set is 2, shortest path calculations are an attractive computational kernel to explore the connections between the two vertices. When the seed set is 3 or larger (say up to 1,000s) Steiner minimal tree – min-weight acyclic connected subgraph (of the input graph) that contains all the seed vertices – is an attractive generalization of shortest weighted paths. In general, computing a Steiner minimal tree is NP-hard, but decades ago several polynomial-time algorithms were designed and proven to yield Steiner trees whose total weight is bounded within 2 times the minimal Steiner tree. Despite its rich theoretical literature, works related to parallel Steiner minimal tree computation and their scalable implementations are rather scarce. In this paper, we present a parallel 2-approximation Steiner minimal tree algorithm (with theoretical guarantees) and its MPI-based distributed implementation. In place of distance computation between all pairs of seed vertices, an expensive phase in many approximation algorithms, the solution we employ, exploits Voronoi cell computation. Also, this approach has higher parallel efficiency than others that involve minimum spanning tree computation on the entire graph. Furthermore, our distributed design exploits asynchronous processing and a message prioritization scheme to accelerate convergence of distance computation, employs techniques to avoid inefficient distributed spanning tree computation on the entire graph, and harnesses a combination of vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance of our solution using real-world graphs with up to 128 billion edges and 512 compute nodes (8K processes), show the ability to find Steiner trees with up to 10K seed ver

关键词： Steiner trees Distributed processing Scalability approximation algorithms Computational efficiency Kernel Convergence

来源：评论

学校读者我要写书评

暂无评论

Online Federated Composite Optimization with Multiple Kernels

Online Federated Composite Optimization with Multiple Kernel...

引用

Asian Control Conference

作者： Haibao Tian Xiuxian Li Min Meng Zhen DONG Shanghai Research Institute for Intelligent Autonomous Systems Tongji University Shanghai China College of Electronics and Information Engineering Tongji University Shanghai China Suzhou SEEExTECH Co. Ltd SEEExTECH Suzhou China

ISBN: (数字)9789887581598

ISBN: (纸本)9798331540845

This paper focuses on Online Federated Composite Optimization (OFCO) problem, where the loss function con-tains a non-smooth regularizer and the network environment is time-varying. This problem is prevalent in various real-world applications, spanning from wireless sensor networks to signal processing. To address the challenge posed by OFCO, we propose a novel federated learning algorithm, named FedOE, which draws inspiration from approximate composite mirror descent. Furthermore, FedOE incorporates a multi-kernel strategy to enhance accuracy and flexibility, emphasizing a comprehensive and effective solution to the OFCO problem. Through theoretical analysis, FedOE achieves a regularized regret on the order of O(VT) with the total number of rounds T. Finally, the numerical experiments validate the efficacy of the proposed algorithm.

关键词： Wireless sensor networks Accuracy Federated learning Signal processing algorithms Signal processing approximation algorithms Mirrors

来源：评论

学校读者我要写书评

暂无评论

Fully Privacy-Preserving and Efficient Clustering Scheme based on Fully Homomorphic Encryption

Fully Privacy-Preserving and Efficient Clustering Scheme bas...

引用

IEEE International Conference on Communications (ICC)

作者： Mengyu Zhang Long Wang Xiaoping Zhang Yisong Wang Wenhou Sun Institute for Network Sciences and Cyberspace Tsinghua University Beijing China Department of Computer Science and Technology Tsinghua University Beijing China

ISBN: (数字)9781728190549

ISBN: (纸本)9781728190556

Fully Homomorphic Encryption is a cryptographic scheme to prevent the privacy leakage of sensitive data. However, one challenge with FHE is the ciphertext comparison widely used in clustering, an important scheme used for data mining and analysis. In this paper, we create a series of ciphertext comparison functions by rewriting the comparison in HE-friendly operations and the Heaviside step function approximated by Chebyshev Polynomials. Furthermore, we solve the challenging ciphertext division through constructing a function whose root is the reciprocal of the divisor and applying Newton's method to ap-proximate the root. Then, we propose a fully privacy-preserving, effective and efficient clustering scheme based on our ciphertext comparison and division. Tests on various datasets show that our algorithm maintains nearly the same classification accuracy as vanilla k-means and significantly outperforms the baseline in terms of accuracy. We then optimize our scheme by batching over multiple records and multithreading, and the results show that our approach has a significant efficiency advantage. Compared with the state-of-the-art FHE-based privacy-preserving clustering scheme (SAC 2018), our algorithm is four orders of magnitude faster than theirs.

关键词： Data privacy Accuracy Multithreading Clustering algorithms Chebyshev approximation approximation algorithms Classification algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic Computing Power Wavelength Allocation Based on Deep Q-Learning for WDM-PON

Dynamic Computing Power Wavelength Allocation Based on Deep ...

引用

OptoElectronics and Communications Conference, OECC

作者： Wenbo Lin Tiankuo Yu Hui Yang Qiuyan Yao Chen Zhang Jie Zhang StateKey Laboratory of Information Photonics and Optical Communications Beijing University of Posts and Telecommunications Beijing China

This paper proposes a dynamic computing power wavelength allocation scheme based on deep Q-learning for WDM-PON, which can reduce spectrum fragmentation during massive computing power requests. Without introducing del... 详细信息

ISBN: (数字)9798350308396

ISBN: (纸本)9798350308402

关键词： Q-learning Processor scheduling Heuristic algorithms Computational modeling Wavelength division multiplexing Dynamic scheduling approximation algorithms Delays Resource management

来源：评论

学校读者我要写书评

暂无评论

Noise-Aware Distributed Quantum Approximate Optimization Algorithm on Near-Term Quantum Hardware

Noise-Aware Distributed Quantum Approximate Optimization Alg...

引用

Quantum Computing and Engineering (QCE), IEEE International Conference on

作者： Kuan-Cheng Chen Xiaotian Xu Felix Burt Chen-Yu Liu Shang Yu Kin K. Leung QuEST Imperial College London London United Kingdom Graduate Institute of Applied Physics National Taiwan University Taipei Taiwan Department of Physics Imperial College London London United Kingdom Department of EEE Imperial College London London UK

ISBN: (数字)9798331541378

ISBN: (纸本)9798331541385

This paper introduces a noise-aware distributed Quantum Approximate Optimization Algorithm (QAOA) tailored for execution on near-term quantum hardware. Leveraging a distributed framework, we address the limitations of current Noisy Intermediate-Scale Quantum (NISQ) devices, which are hindered by limited qubit counts and high error rates. Our approach decomposes large QAOA problems into smaller subproblems, distributing them across multiple Quantum Processing Units (QPUs) to enhance scalability and performance. The noise-aware strategy incorporates error mitigation techniques to optimize qubit fidelity and gate operations, ensuring reliable quantum computations. We evaluate the efficacy of our framework using the HamilToniQ Benchmarking Toolkit, which quantifies the performance across various quantum hardware configurations. The results demonstrate that our distributed QAOA framework achieves significant improvements in computational speed and accuracy, showcasing its potential to solve complex optimization problems efficiently in the NISQ era. This work sets the stage for advanced algorithmic strategies and practical quantum system enhancements, contributing to the broader goal of achieving quantum advantage.

关键词： Quantum system Quantum computing Quantum advantage Prevention and mitigation Scalability Qubit approximation algorithms Hardware Reliability Optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：