Yazdani et al., 2001 - Google Patents
Prefix trees: new efficient data structures for matching strings of different lengthsYazdani et al., 2001
- Document ID
- 16869531466980309572
- Author
- Yazdani N
- Min P
- Publication year
- Publication venue
- Proceedings 2001 International Database Engineering and Applications Symposium
External Links
Snippet
Prefix matching is an essential part of some applications. A well known application of prefix matching is layers 3 and 4 switching in TCP/IP protocols. It is assumed that there are strings of an alphabet/spl Sigma/which are ordered. The strings may have different lengths and …
- 230000003068 static 0 abstract description 9
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
- G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
- G06F17/30961—Trees
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
- G06F17/30613—Indexing
- G06F17/30619—Indexing indexing structures
- G06F17/30625—Trees
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
- G06F17/30964—Querying
- G06F17/30979—Query processing
- G06F17/30985—Query processing by using string matching techniques
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
- G06F17/30312—Storage and indexing structures; Management thereof
- G06F17/30321—Indexing structures
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING; COUNTING
- G06F—ELECTRICAL DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
- G06F17/30861—Retrieval from the Internet, e.g. browsers
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99933—Query processing, i.e. searching
- Y10S707/99936—Pattern matching access
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99941—Database schema or data structure
- Y10S707/99942—Manipulating data structure, e.g. compression, compaction, compilation
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99941—Database schema or data structure
- Y10S707/99943—Generating database or data structure, e.g. via user interface
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6614789B1 (en) | Method of and apparatus for matching strings of different lengths | |
| Woo | A modular approach to packet classification: Algorithms and results | |
| CN107153647B (en) | Method, apparatus, system and computer program product for data compression | |
| US6564211B1 (en) | Fast flexible search engine for longest prefix match | |
| Tsuchiya | A search algorithm for table entries with non-contiguous wildcarding | |
| US5627748A (en) | Method of identifying pattern matches in parameterized strings and square matrices | |
| Yazdani et al. | Fast and scalable schemes for the IP address lookup problem | |
| US5511159A (en) | Method of identifying parameterized matches in a string | |
| US6792423B1 (en) | Hybrid longest prefix match and fixed match searches | |
| Belazzougui et al. | Representing the suffix tree with the CDAWG | |
| US7756859B2 (en) | Multi-segment string search | |
| Yazdani et al. | Prefix trees: new efficient data structures for matching strings of different lengths | |
| Jansson et al. | Linked dynamic tries with applications to LZ-compression in sublinear time and space | |
| Amir et al. | Efficient randomized dictionary matching algorithms | |
| Chang et al. | Applying pattern mining to Web information extraction | |
| Luccio et al. | Exact rooted subtree matching in sublinear time | |
| Andersson et al. | Suffix trees on words | |
| KR100999408B1 (en) | 검색 ＲＬ search method using hatstry | |
| Ferragina et al. | Learned monotone minimal perfect hashing | |
| Yazdani et al. | DMP-tree: A dynamic M-way prefix tree data structure for strings matching | |
| Brisaboa et al. | A new approach for document indexing usingwavelet trees | |
| US20060059153A1 (en) | Computer constructions of a lexical tree | |
| KR100598341B1 (en) | How to manage Internet Protocol (IP) address information in database using binary notation string | |
| Belazzougui et al. | Compressed string dictionary search with edit distance one | |
| CN100531179C (en) | Method for storing character string matching rule and character string matching by storing rule |