Fast prefix matching of bounded strings
US7191168B1 · kind B1 · utility
19Cited by
52References
25Claims
0Family size
Assignee
Inventors
Key dates
| Filing date | Sep 25, 2002 |
| Grant date | Mar 13, 2007 |
| Priority date | — |
| Expiry date | Jan 23, 2025 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99932
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
The present invention increases the efficiency of performing longest prefix matching operations by selecting a radix-encoded trie structure optimized with respect to memory cost. The structure is optimized by determining memory costs for retrie structures indexed on different numbers of high-order characters, and then selecting the structure corresponding to the lowest memory cost. The optimization improves performance in IP look-up operations as well as longest-prefix matching operations performed on general alphabets.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.