.png){kind=icon}
返回
NvPD: novel parallel edit distance algorithm, correctness, and performance evaluation
.png){kind=icon}
PRE
AI
DOI：10.1007/s10586-019-02962-w.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Edit distance has applications in many domains such as bioinformatics, spell checking, plagiarism checking, query optimization, speech recognition, and data mining. Traditionally, edit distance is computed by dynamic programming based sequential solution which becomes infeasible for large problems. In this paper, we introduce NvPD, a novel algorithm for parallel edit distance computation by resolving dependencies in the conventional dynamic programming based solution. We also establish the correctness of modified dependencies. NvPD exhibits certain characteristics such as balanced workload among processors, less synchronization overhead, maximum utilization of resources and it can exploit spatial locality. It requiresmin(m,n)steps to complete as compared to diagonal based approach that completes inmax(m,n) Experimental evaluation using variety of random and real life data sets over shared memory multi-core systems and graphic processing units (GPUs) show that NvPD outperforms state-of-the-art parallel edit distance algorithms.
Keyword:
Edit distance
Dynamic programming
Parallel algorithms
Performance evaluation
GPUs
OpenMP
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.1
论文数:
5.1K
被引数:
7.5K
机构
引用论文
.png){kind=icon}
Functional Morphology and Floral Odor of Ditassa burchellii (Apocynaceae, Asclepiadoideae), a Micromyiophilous Species from Southeastern Brazil功能形态学与花部气味：来自巴西东南部的微蚁传粉物种Ditassa burchellii (夹竹桃科，萝藦亚科)
PREAI
分享收藏
查看更多内容