基本信息来源于合作网站,原文需代理用户跳转至来源网站获取       
摘要:
近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用((m+1)个处理器和O(n/(+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.
推荐文章
机群系统上基于Hashing的多目标串匹配并行算法
多目标串匹配
词典匹配
并行算法
Hashing
机群系统
异构机群系统上近似串匹配并行算法
近似串匹配
并行算法
异构机群系统
可分负载
分配策略
基于 GPU 加速的并行字符串匹配算法
GPU
CUDA
并行字符串匹配
模式匹配
基于分层存储理论模型的近似字符串匹配并行算法研究
近似字符串匹配
分层存储理论模型
并行算法
CUDA
内容分析
关键词云
关键词热度
相关文献总数  
(/次)
(/年)
文献信息
篇名 PRAM和LARPBS模型上的近似串匹配并行算法
来源期刊 软件学报 学科 工学
关键词 近似串匹配 并行算法 CREW-PRAM(parallel random access machine with concurrent read and exclusive write) 可重构光总线系统 编辑距离 汉明距离
年,卷(期) 2004,(2) 所属期刊栏目 算法设计与分析
研究方向 页码范围 159-169
页数 11页 分类号 TP301
字数 11930字 语种 中文
DOI
五维指标
作者信息
序号 姓名 单位 发文数 被引次数 H指数 G指数
1 陈国良 中国科学技术大学计算机科学与技术系 123 2142 20.0 43.0
5 钟诚 中国科学技术大学计算机科学与技术系 6 70 4.0 6.0
传播情况
(/次)
(/年)
引文网络
引文网络
二级参考文献  (0)
共引文献  (0)
参考文献  (5)
节点文献
引证文献  (42)
同被引文献  (21)
二级引证文献  (94)
1991(1)
  • 参考文献(1)
  • 二级参考文献(0)
1999(1)
  • 参考文献(1)
  • 二级参考文献(0)
2000(1)
  • 参考文献(1)
  • 二级参考文献(0)
2001(1)
  • 参考文献(1)
  • 二级参考文献(0)
2002(1)
  • 参考文献(1)
  • 二级参考文献(0)
2004(2)
  • 参考文献(0)
  • 二级参考文献(0)
  • 引证文献(2)
  • 二级引证文献(0)
2004(2)
  • 引证文献(2)
  • 二级引证文献(0)
2005(7)
  • 引证文献(6)
  • 二级引证文献(1)
2006(12)
  • 引证文献(5)
  • 二级引证文献(7)
2007(6)
  • 引证文献(4)
  • 二级引证文献(2)
2008(11)
  • 引证文献(6)
  • 二级引证文献(5)
2009(11)
  • 引证文献(5)
  • 二级引证文献(6)
2010(9)
  • 引证文献(1)
  • 二级引证文献(8)
2011(11)
  • 引证文献(1)
  • 二级引证文献(10)
2012(15)
  • 引证文献(2)
  • 二级引证文献(13)
2013(4)
  • 引证文献(1)
  • 二级引证文献(3)
2014(12)
  • 引证文献(3)
  • 二级引证文献(9)
2015(7)
  • 引证文献(3)
  • 二级引证文献(4)
2016(12)
  • 引证文献(2)
  • 二级引证文献(10)
2017(3)
  • 引证文献(1)
  • 二级引证文献(2)
2018(8)
  • 引证文献(0)
  • 二级引证文献(8)
2019(3)
  • 引证文献(0)
  • 二级引证文献(3)
2020(3)
  • 引证文献(0)
  • 二级引证文献(3)
研究主题发展历程
节点文献
近似串匹配
并行算法
CREW-PRAM(parallel random access machine with concurrent read and exclusive write)
可重构光总线系统
编辑距离
汉明距离
研究起点
研究来源
研究分支
研究去脉
引文网络交叉学科
相关学者/机构
期刊影响力
软件学报
月刊
1000-9825
11-2560/TP
16开
北京8718信箱
82-367
1990
chi
出版文献量(篇)
5820
总下载数(次)
36
相关基金
国家重点基础研究发展计划(973计划)
英文译名:National Basic Research Program of China
官方网址:http://www.973.gov.cn/
项目类型:
学科类型:农业
国家高技术研究发展计划(863计划)
英文译名:The National High Technology Research and Development Program of China
官方网址:http://www.863.org.cn
项目类型:重点项目
学科类型:信息技术
论文1v1指导