|
The ACM Journal of Experimental Algorithmics
|
Volume 8 Article 3, 2003
Fast Prefix Matching of Bounded Strings
by
and
a
nd
and
and
http://www.jea.acm.org/2003/BuchsbaumFast/
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 boundes 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 retries a fast
and compact data structure for LPM on general alphabets. Performance
results show that retires ofent outperform previously published data
structures for IP look-up. By extending LPM to general alphabets,
retries admit new applications that oculd not exploit prior LPM
solutions designed for IP look-ups.
Keywords: Algorithms, Experimentation, Measurement, Performance,
Theory, IP routing, prefix matching, table look-up, tries
Categories: D.2.8. [Software Engineering]: Metrix-Performance
Measures; E.1 [Data Structures]: Arrays; Recors; E.2 [Data Storage
Representations]: Linked Representations; F.2.2 [Analysis of Algorithms
and Problem Complexity]: Nonumerical Algorithms and Problems - Pattern
Matching.
G.4 Mathematical Software: Algorithm Design and Analysis
- Sources:
- The Postscript
version of the article;
note that you must be a subscriber (institutional or individual) to
access these files.