| Presentation | 2023-03-25 Optimizing Hash Functions of Rabin-Karp Method for Multi-Pattern Matching with Multiple Pattern Lengths Soa Suzuki, Hayato Yamaki, Shinobu Miwa, Hiroki Honda, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In recent years, demand for multi-pattern matching, in which a large number of patterns are matched against input data, has increased, and improving processing speed has become an important issue. The Rabin-Karp method is a fast algorithm that can match multiple patterns at once as long as they have the same pattern length. In this report, we propose a new hash function that computes hash values for all patterns from a sequence of bytes of basic data length $n$ and a matching method using the hash function. This method makes it possible to match all patterns at once from the hash value of $n$ bytes of input data. Evaluation of the application of multi-pattern matching to English word search and intrusion detection systems shows that the proposed method improves the matching speed by a factor of 12.5 to 50 times compared to the conventional method. The proposed method can improve the matching speed by 12.5 to 50 times. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Pattern matching / Rabin-Karp method / hash function |
| Paper # | CPSY2022-54,DC2022-113 |
| Date of Issue | 2023-03-16 (CPSY, DC) |
| Conference Information | |
| Committee | DC / CPSY / IPSJ-SLDM / IPSJ-EMB / IPSJ-ARC |
|---|---|
| Conference Date | 2023/3/23(3days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Amagi Town Disaster Prevention Center (Tokunoshima) |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Tatsuhiro Tsuchiya(Osaka Univ.) / Michihiro Koibuchi(NII) / Hiroyuki Ochi(Ritsumeikan Univ.) / / Hiroshi Inoue(Nagoya Institute of Technology) |
| Vice Chair | Toshinori Hosokawa(Nihon Univ.) / Kota Nakajima(Fujitsu Lab.) / Tomoaki Tsumura(Nagoya Inst. of Tech.) |
| Secretary | Toshinori Hosokawa(Nihon Univ.) / Kota Nakajima(Chiba Univ.) / Tomoaki Tsumura(JAIST) / (Hitachi) / (Tokyo Inst. of Tech.) / (Meiji Univ.) |
| Assistant | / Ryohei Kobayashi(Tsukuba Univ.) / Takaaki Miyajima(Meiji Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Dependable Computing / Technical Committee on Computer Systems / Special Interest Group on System and LSI Design Methodology / Special Interest Group on Embedded Systems / Special Interest Group on System Architecture |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Optimizing Hash Functions of Rabin-Karp Method for Multi-Pattern Matching with Multiple Pattern Lengths |
| Sub Title (in English) | |
| Keyword(1) | Pattern matching |
| Keyword(2) | Rabin-Karp method |
| Keyword(3) | hash function |
| 1st Author's Name | Soa Suzuki |
| 1st Author's Affiliation | The University of Electro-Communications(UEC) |
| 2nd Author's Name | Hayato Yamaki |
| 2nd Author's Affiliation | The University of Electro-Communications(UEC) |
| 3rd Author's Name | Shinobu Miwa |
| 3rd Author's Affiliation | The University of Electro-Communications(UEC) |
| 4th Author's Name | Hiroki Honda |
| 4th Author's Affiliation | The University of Electro-Communications(UEC) |
| Date | 2023-03-25 |
| Paper # | CPSY2022-54,DC2022-113 |
| Volume (vol) | vol.122 |
| Number (no) | CPSY-451,DC-452 |
| Page | pp.pp.118-123(CPSY), pp.118-123(DC), |
| #Pages | 6 |
| Date of Issue | 2023-03-16 (CPSY, DC) |