A Hardware-Based PATRICIA Algorithm for Fixed-Length Match

Li Xin, Hu Mingzeng, and Ji Zhenzhou

Journal of Computer Research and Development > 2005 > 42(6): 951-957.

Li Xin, Hu Mingzeng, and Ji Zhenzhou. A Hardware-Based PATRICIA Algorithm for Fixed-Length Match[J]. Journal of Computer Research and Development, 2005, 42(6): 951-957.

Citation:

Li Xin, Hu Mingzeng, and Ji Zhenzhou. A Hardware-Based PATRICIA Algorithm for Fixed-Length Match[J]. Journal of Computer Research and Development, 2005, 42(6): 951-957.

Citation:

Li Xin, Hu Mingzeng, and Ji Zhenzhou. A Hardware-Based PATRICIA Algorithm for Fixed-Length Match[J]. Journal of Computer Research and Development, 2005, 42(6): 951-957.

PDF (409 KB)

A Hardware-Based PATRICIA Algorithm for Fixed-Length Match

Li Xin, Hu Mingzeng, and Ji Zhenzhou

(Department of Computer Science and Engineering, Harbin Institute of Technology, Harbin 150001)

More Information

Published Date: June 14, 2005

Graphical Abstract

Abstract

Abstract

PATRICIA algorithm has become a classic method for information retrieval. But PATRICIA insertion is time-consuming. By analyzing PATRICIA, it is discovered that not keeping the order of NBTs(next bit to test) in PATRICIA trie can improve the performance of PATRICIA insertion and decrease hardware design complexity. A new PATRICIA algorithm for fixed-length match is proposed. It is proved that this algorithm is an optimal binary trie-based algorithm. An ASIC (application specific integrated circuit) for this algorithm is implemented for the application of state table of stateful inspection. The theoretical and experimental results show that this algorithm can work very well for the application of state table in gigabit network.
- state table,
- fixed-length match,
- hardware design complexity,
- PATRICIA

FullText(HTML)

References (0)

[1]	Pan Xuan, Xu Sihan, Cai Xiangrui, Wen Yanlong, Yuan Xiaojie. Survey on Deep Learning Based Natural Language Interface to Database[J]. Journal of Computer Research and Development, 2021, 58(9): 1925-1950. DOI: 10.7544/issn1000-1239.2021.20200209
[2]	Li Yin. Test Suite Generating for Stateful Web Services Using Interface Contract[J]. Journal of Computer Research and Development, 2017, 54(3): 609-622. DOI: 10.7544/issn1000-1239.2017.20151045
[3]	Dong Yongquan, Li Qingzhong, Ding Yanhui, Peng Zhaohui. Constrained Conditional Random Fields for Semantic Annotation of Web Data[J]. Journal of Computer Research and Development, 2012, 49(2): 361-371.
[4]	Tian Jianwei and Li Shijun. Retrieving Deep Web Data Based on Hierarchy Tree Model[J]. Journal of Computer Research and Development, 2011, 48(1): 94-102.
[5]	Kou Yue, Li Dong, Shen Derong, Yu Ge, Nie Tiezheng. D-EEM: A DOM-Tree Based Entity Extraction Mechanism for Deep Web[J]. Journal of Computer Research and Development, 2010, 47(5): 858-865.
[6]	Ding Guohui, Wang Guoren, and Zhao Yuhai. Multi-Schema Integration Based on Usage and Clustering Approach[J]. Journal of Computer Research and Development, 2010, 47(5): 824-831.
[7]	Shen Derong, Ma Ye, Nie Tiezheng, Kou Yue, and Yu Ge. A Query Relaxation Strategy Applied in a Deep Web Data Integration System[J]. Journal of Computer Research and Development, 2010, 47(1): 88-95.
[8]	Ma Anxiang, Zhang Bin, Gao Kening, Qi Peng, and Zhang Yin. Deep Web Data Extraction Based on Result Pattern[J]. Journal of Computer Research and Development, 2009, 46(2): 280-288.
[9]	Qu Yuzhong, Hu Wei, Zheng Dongdong, and Zhong Xinyu. Mapping Between Relational Database Schemas and Ontologies: The State of the Art[J]. Journal of Computer Research and Development, 2008, 45(2): 300-309.
[10]	Zhang Weiming and Song Junfeng. Study on Domain Ontology Representation, Reasoning and Integration for the Semantic Web[J]. Journal of Computer Research and Development, 2006, 43(1): 101-108.