Loading...
Please wait, while we are loading the content...
Similar Documents
Fast prefix matching of bounded strings
| Content Provider | ACM Digital Library |
|---|---|
| Author | Buchsbaum, Adam L. Fowler, Glenn S. Kirishnamurthy, Balachannder Vo, Kiem-Phong Wang, Jia |
| Copyright Year | 2003 |
| Abstract | Longest Prefix Matching (LPM) is the problem of finding which string from a given set is the longest prefix of another, given string. LPM is a core problem in many applications, including IP routing, network data clustering, and telephone network management. These applications typically require very fast matching of bounded strings, i.e., strings that are short and based on small alphabets. We note a simple correspondence between bounded strings and natural numbers that maps prefixes to nested intervals so that computing the longest prefix matching a string is equivalent to finding the shortest interval containing its corresponding integer value. We then present $\textit{retries},$ a fast and compact data structure for LPM on general alphabets. Performance results show that retries often outperform previously published data structures for IP look-up. By extending LPM to general alphabets, retries admit new applications that could not exploit prior LPM solutions designed for IP look-ups. |
| File Format | |
| ISSN | 10846654 |
| e-ISSN | 10846654 |
| DOI | 10.1145/996546.996550 |
| Journal | Journal of Experimental Algorithmics (JEA) |
| Volume Number | 8 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2003-12-01 |
| Publisher Place | New York |
| Access Restriction | One Nation One Subscription (ONOS) |
| Subject Keyword | IP routing Prefix matching Table look-up Tries |
| Content Type | Text |
| Resource Type | Article |
| Subject | Theoretical Computer Science |
