一种无回溯的最长前缀匹配搜索算法

发布时间：2018-02-12 00:33

  本文关键词： 搜索算法 最长前缀匹配 Patricia树 搜索引擎　出处：《计算机工程》2008年10期 　论文类型：期刊论文

【摘要】：研究网络处理器中的搜索算法,提出一种基于Patricia树的无回溯搜索算法,并进行仿真和评估分析。该算法被用于中科院计算所的网络处理器的搜索引擎的设计中,该搜索引擎可以运行在155.9 MHz的XC2VP30 FPGA上,占用421个LUT,当频率为100 MHz时,每秒可以执行约7 000 000次搜索操作,实现了资源消耗和性能的折中。
[Abstract]:This paper studies the search algorithm in the network processor, proposes a non-backtracking search algorithm based on Patricia tree, and makes simulation and evaluation analysis. The algorithm is used in the design of the search engine of the network processor in the Institute of Computing of the Chinese Academy of Sciences. The search engine can run on 155.9 MHz XC2VP30 FPGA, occupying 421 LUTs. When the frequency is 100 MHz, it can perform about 7 million search operations per second, realizing the compromise of resource consumption and performance.
【作者单位】： 中国科学院计算机系统结构重点实验室 中国科学院计算机系统结构重点实验室 中国科学院计算机系统结构重点实验室
【基金】：国家自然科学基金资助项目(60606008)
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 杨艳;朱戈;范文彬;;一种基于文档拓扑的相似性搜索算法[J];计算机工程与应用;2011年26期

2 贾彦国;纪永峰;任富争;;差集偶搜索算法[J];燕山大学学报;2011年04期

3 马鸿旭;;基于变化步长的数字影像特征搜索算法[J];信息通信;2011年04期

4 叶漪;吴国文;罗辛;;一种带有时间域的证书链搜索算法[J];计算机应用与软件;2011年09期

5 王琳霖;唐晨;;基于梯度法的数字散斑图像相关亚像素搜索算法[J];光电技术应用;2011年03期

6 吴小洪;尧三品;刘金保;;基于差分多值的快速模板匹配算法[J];控制工程;2011年03期

7 李姣军;李恒;苏理云;李刚;;一种快速自适应最优小波包基搜索算法[J];现代电子技术;2011年11期

8 孙文胜;胡玲敏;;基于后退式搜索的自适应多叉树防碰撞算法[J];计算机应用;2011年08期

9 赖志柱;吴德宝;;一种改进的和声退火算法[J];毕节学院学报;2011年08期

10 张亚军;;汉语-维吾尔语机器翻译解码器研究[J];昌吉学院学报;2011年03期

相关会议论文 前10条

1 支成秀;梁正友;;融合粒子群优化算法与蚁群算法的随机搜索算法[A];广西计算机学会2006年年会论文集[C];2006年

2 张晓玲;钟诚;李智;李锦;张尊国;;基于反馈选择的P2P网络搜索算法[A];2007年全国开放式分布与并行计算机学术会议论文集(上册)[C];2007年

3 孙文彬;赵学胜;邹仁贵;;球面Quaternary编码的分解邻近搜索算法[A];第四届海峡两岸GIS发展研讨会暨中国GIS协会第十届年会论文集[C];2006年

4 王晓兰;郭玲;黄志同;周献中;;连续数字串识别的帧重叠搜索算法[A];第六届全国计算机应用联合学术会议论文集[C];2002年

5 吴丹;鲍玉斌;刘运涛;于戈;孙焕良;王大玲;;一种基于高效分形维计算的快速属性相关性搜索算法[A];第二十二届中国数据库学术会议论文集（研究报告篇）[C];2005年

6 刘国华;张颖;陈子军;陈子阳;;改进的CNN搜索算法[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年

7 郭玉堂;吕皖丽;罗斌;;一种基于P2P技术的Gnutella网络的资源定位搜索算法的研究[A];第二十六届中国控制会议论文集[C];2007年

8 黄显林;宋清南;班晓军;高晓智;;一种基于和声搜索算法的T-S模型辨识方法[A];第二十九届中国控制会议论文集[C];2010年

9 孙俊;王晓东;;一种改进的基于新一代Gnutella网络的动态搜索算法[A];2007年全国开放式分布与并行计算机学术会议论文集(上册)[C];2007年

10 蒋建国;彭兴邦;聂秋玉;;一种改进的等范数最近邻码本矢量搜索算法[A];计算机技术与应用进展——全国第17届计算机科学与技术应用（CACIS）学术会议论文集（上册）[C];2006年

相关重要报纸文章 前10条

1 本报记者　陈磊;2008奥运,实现语言交流无障碍[N];科技日报;2006年

2 熊德意邋何中军 刘群;机器翻译渐行渐近[N];计算机世界;2007年

3 ;强制性实时透明文件加解密系统选型[N];中国计算机报;2007年

4 ;微软展示搜索引擎新技术[N];人民邮电;2006年

5 吴加录;盖茨看中雅虎工程师[N];中国计算机报;2008年

6 中国科技大学计算机系　邢方亮;计算智能百花齐放[N];计算机世界;2003年

7 本报记者 于翔;搜索整合前路漫漫[N];网络世界;2010年

8 吴加录;三大搜索引擎仍未满足用户需求[N];中国计算机报;2006年

9 商报实习记者 李鹏;微软出Bing，，有求必应?[N];中国图书商报;2009年

10 冯卫东;美通过大规模计算寻找抗流感新药[N];科技日报;2009年

相关博士学位论文 前10条

1 张映玉;绝热量子搜索算法研究[D];华中科技大学;2011年

2 水超;常量度P2P系统中复杂搜索技术研究[D];国防科学技术大学;2006年

3 许建军;对结构化和半结构化数据的关键字搜索研究[D];复旦大学;2007年

4 贾兆庆;非结构化P2P中搜索算法及信任机制研究[D];上海交通大学;2008年

5 金文梁;三维复子空间中的量子搜索和多相位匹配研究[D];西南交通大学;2011年

6 许中卫;基于双向搜索的ILP算法构建汉语语义自动切分系统[D];安徽大学;2006年

7 蔡敦波;基于启发式搜索的智能规划方法研究[D];吉林大学;2009年

8 丁治国;RFID关键技术研究与实现[D];中国科学技术大学;2009年

9 陆平静;低开销的迭代编译优化关键技术研究[D];国防科学技术大学;2010年

10 姚国辉;若干组合优化问题的算法研究[D];山东大学;2009年

相关硕士学位论文 前10条

1 罗军珍;XML在关系数据库中存储方法的研究[D];重庆大学;2005年

2 彭煜;求解三维装箱问题的启发式分层搜索算法[D];厦门大学;2009年

3 王倩;一种改进的和声搜索算法及其应用[D];华东理工大学;2012年

4 王Pq华;参数协进化的改进和声搜索算法及其应用[D];华东理工大学;2012年

5 姚健;群搜索算法与二次插值法的混合算法及其应用研究[D];太原科技大学;2010年

6 徐遥;基于引力搜索算法的改进及应用研究[D];江南大学;2012年

7 郑小飞;城市公交多路径改进搜索算法的研究及应用[D];东华大学;2011年

8 吴永军;基于分带索引存储结构的高效XML搜索算法的研究与应用[D];中南大学;2010年

9 孙伟平;面向转化医学的生物信息学数据融合与搜索算法研究及应用[D];中南大学;2012年

10 贾莎莎;P2P中资源搜索算法及其在电子商务系统中的应用[D];华侨大学;2011年

本文编号：1504374