HashTrie:a space-efficient multiple string matching algorithm
The famous multiple string matching algorithm AC consumed huge memory when the string signatures were massive,thus unable to process high speed network traffic efficiently.To solve this problem,a space-efficient multiple string matching algorithm-HashTrie was proposed.This algorithm adopted recursiv...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2015-10-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015215/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539566692990976 |
|---|---|
| author | Ping ZHANG Yan-bing LIU Jing YU Jian-long TAN |
| author_facet | Ping ZHANG Yan-bing LIU Jing YU Jian-long TAN |
| author_sort | Ping ZHANG |
| collection | DOAJ |
| description | The famous multiple string matching algorithm AC consumed huge memory when the string signatures were massive,thus unable to process high speed network traffic efficiently.To solve this problem,a space-efficient multiple string matching algorithm-HashTrie was proposed.This algorithm adopted recursive hash function to store the patterns in bit-vectors in place of the state transition table in order to reduce space consumption.Further more it made use of the rank operation for fast verification.Theoretic analysis shows that the space complexity of HashTrie is O(|P|),which is linear with the size of pattern set |P|and is independent of the alphabetsize σ.The space complexity is superior to the complexity O(|P|σlog|P|)of AC.Experiments on synthetic datasets and real-world datasets(such as Snort,ClamAV and URL)show that HashTrie saves up to 99.6% storage cost compared with AC,and in the meanwhile it runs at a matching speed that is about half of AC.HashTrie is a space-efficient multiple string matching algorithm that is appropriate to search large scale pattern strings with short lengths. |
| format | Article |
| id | doaj-art-3df6993c9c0e42dfb5f7f3c753ade622 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2015-10-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-3df6993c9c0e42dfb5f7f3c753ade6222025-01-14T06:53:55ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2015-10-013617218059696478HashTrie:a space-efficient multiple string matching algorithmPing ZHANGYan-bing LIUJing YUJian-long TANThe famous multiple string matching algorithm AC consumed huge memory when the string signatures were massive,thus unable to process high speed network traffic efficiently.To solve this problem,a space-efficient multiple string matching algorithm-HashTrie was proposed.This algorithm adopted recursive hash function to store the patterns in bit-vectors in place of the state transition table in order to reduce space consumption.Further more it made use of the rank operation for fast verification.Theoretic analysis shows that the space complexity of HashTrie is O(|P|),which is linear with the size of pattern set |P|and is independent of the alphabetsize σ.The space complexity is superior to the complexity O(|P|σlog|P|)of AC.Experiments on synthetic datasets and real-world datasets(such as Snort,ClamAV and URL)show that HashTrie saves up to 99.6% storage cost compared with AC,and in the meanwhile it runs at a matching speed that is about half of AC.HashTrie is a space-efficient multiple string matching algorithm that is appropriate to search large scale pattern strings with short lengths.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015215/intrusion detectionmultiple string matchingbit-vector recursive hash functionspace-efficient |
| spellingShingle | Ping ZHANG Yan-bing LIU Jing YU Jian-long TAN HashTrie:a space-efficient multiple string matching algorithm Tongxin xuebao intrusion detection multiple string matching bit-vector recursive hash function space-efficient |
| title | HashTrie:a space-efficient multiple string matching algorithm |
| title_full | HashTrie:a space-efficient multiple string matching algorithm |
| title_fullStr | HashTrie:a space-efficient multiple string matching algorithm |
| title_full_unstemmed | HashTrie:a space-efficient multiple string matching algorithm |
| title_short | HashTrie:a space-efficient multiple string matching algorithm |
| title_sort | hashtrie a space efficient multiple string matching algorithm |
| topic | intrusion detection multiple string matching bit-vector recursive hash function space-efficient |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015215/ |
| work_keys_str_mv | AT pingzhang hashtrieaspaceefficientmultiplestringmatchingalgorithm AT yanbingliu hashtrieaspaceefficientmultiplestringmatchingalgorithm AT jingyu hashtrieaspaceefficientmultiplestringmatchingalgorithm AT jianlongtan hashtrieaspaceefficientmultiplestringmatchingalgorithm |