• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >A New Progressive Algorithm for a Multiple Longest Common Subsequences Problem and Its Efficient Parallelization
【24h】

A New Progressive Algorithm for a Multiple Longest Common Subsequences Problem and Its Efficient Parallelization

机译：多重最长公共子序列问题的新渐进算法及其有效并行化

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The multiple longest common subsequence (MLCS) problem, which is related to the measurement of sequence similarity, is one of the fundamental problems in many fields. As an NP-hard problem, finding a good approximate solution within a reasonable time is important for solving large-size problems in practice. In this paper, we present a new progressive algorithm, Pro-MLCS, based on the dominant point approach. Pro-MLCS can find an approximate solution quickly and then progressively generate better solutions until obtaining the optimal one. Pro-MLCS employs three new techniques: 1) a new heuristic function for prioritizing candidate points; 2) a novel $(d)$-index-tree data structure for efficient computation of dominant points; and 3) a new pruning method using an upper bound function and approximate solutions. Experimental results show that Pro-MLCS can obtain the first approximate solution almost instantly and needs only a very small fraction, e.g., 3 percent, of the entire running time to get the optimal solution. Compared to existing state-of-the-art algorithms, Pro-MLCS can find better solutions in much shorter time, one to two orders of magnitude faster. In addition, two parallel versions of Pro-MLCS are developed: DPro-MLCS for distributed memory architecture and DSDPro-MLCS for hierarchical distributed shared memory architecture. Both parallel algorithms can efficiently utilize parallel computing resources and achieve nearly linear speedups. They also have a desirable progressiveness property—finding better solutions in shorter time when given more hardware resources.
机译：与序列相似性的度量有关的多重最长公共子序列（MLCS）问题是许多领域中的基本问题之一。作为NP难题，在合理的时间内找到良好的近似解对于解决实际中的大型问题很重要。在本文中，我们基于优势点方法提出了一种新的渐进算法Pro-MLCS。 Pro-MLCS可以快速找到一个近似解，然后逐步生成更好的解，直到获得最佳解。 Pro-MLCS采用了三种新技术：1）一种新的启发式函数，用于对候选点进行优先级排序； 2）一种新颖的$（d）$-索引树数据结构，用于有效计算优势点；和3）使用上限函数和近似解的新修剪方法。实验结果表明，Pro-MLCS几乎可以立即获得第一个近似解，并且仅需要很小的一部分，例如占整个运行时间的3％，即可获得最佳解。与现有的最新算法相比，Pro-MLCS可以在更短的时间内找到更好的解决方案，速度快一到两个数量级。此外，还开发了Pro-MLCS的两个并行版本：用于分布式内存体系结构的DPro-MLCS和用于分层分布式共享内存体系结构的DSDPro-MLCS。两种并行算法都可以有效利用并行计算资源，并实现近乎线性的加速。它们还具有理想的累进性-在给定更多硬件资源的情况下，可以在更短的时间内找到更好的解决方案。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号