Data processing: database and file management or data structures – Database and file access – Search engines
Reexamination Certificate
2006-11-30
2010-12-14
Ali, Mohammad (Department: 2158)
Data processing: database and file management or data structures
Database and file access
Search engines
C707S776000, C707S999006, C711S108000
Reexamination Certificate
active
07853578
ABSTRACT:
Apparatus having corresponding methods and computer programs, to detect a pattern in a string, comprises a memory circuit to store W-character segments of the pattern, where each segment comprises a fragment of the pattern; a key circuit to generate W-character keys each including a fragment of the string; a comparison circuit to compare the keys and the segments; where, when a segment matches a key, the comparison circuit indicates an initial match between the pattern and the string; and where, when one of the segments matches only a L-character fragment of one of the keys, wherein L<W, the key circuit generates a new key including the L-character fragment and a K-character fragment of the string including K=W−L consecutive characters from the string that are adjacent to the L matching characters in the string.
REFERENCES:
patent: 6081440 (2000-06-01), Washburn et al.
patent: 6874016 (2005-03-01), Gai et al.
patent: 7134143 (2006-11-01), Stellenberg et al.
patent: 7185017 (2007-02-01), Cauvin et al.
patent: 7225188 (2007-05-01), Gai et al.
patent: 7492763 (2009-02-01), Alexander, Jr.
patent: 7602785 (2009-10-01), Dharmapurikar et al.
patent: 7613822 (2009-11-01), Joy et al.
patent: 2005/0021491 (2005-01-01), Horgan
patent: 2007/0115986 (2007-05-01), Shankara
Tatsuya Akutsu, “Approximate String Matching With Don't Care Characters”, Jun. 19, 1995, Informarmation Processing Letters 55 (19950, pp. 235-239.
Rong-Tai Liu; Nen-Fu Huang; Chih-Hao Chen and Chia-Nan Kao, “A Fast String-Matching Algorithm for Network Processor-Based Intrusion Detection System” ACM Transactions on Embedded Computing Systems, vol. 3, No. 3, Aug. 2004, p. 614-633.
Long Bu, John A. Chandy, “A Keyword Match Processor Architecture using Content Addressable Memory” GLSVLSI'04 , Apr. 26-28, 2004, ACM, pp. 372-376.
ANSI/IEEE Std 802.11, 1999 Edition; Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications; LAN/MAN Standards Committee of the IEEE Computer Society; 528 pages.
IEEE Std 802.11a-1999 (Supplement to IEEE Std 802.11-1999) [Adopted by ISO/IEC and redesignated as ISO/IEC 8802-11: 1999/Amd 1:2000(E)]; Supplement to IEEE Standard for Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications High-speed Physical Layer in the 5 GHz Band; LAN/MAN Standards Committee of the IEEE Computer Society; 91 pages.
IEEE Std 802.11b-1999 (Supplement to IEEE Std 802.11-1999 Edition); Supplement to IEEE Standard for Information technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Higher-Speed Physical Layer Extension in the 2.4 GHz Band; LAN/MAN Standards Committee of the IEEE Computer Society; Sep. 16, 1999 IEEE-SA Standards Board; 96 pages.
IEEE P802.11g/D8.2, Apr. 2003 (Supplement to ANSI/IEEE Std 802.11-1999(Reaff 2003)); DRAFT Supplement to STANDARD [for] Information Technology—Telecommunications and information exchange between systems—Local and metropolitan area networks—Specific requirements—Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Further Higher Data Rate Extension in the 2.4 GHz Band; LAN/MAN Standards Committee of the IEEE Computer Society; 69 pages.
802.11n; IEEE P802.11-04/0889r6; Wireless LANs, TGn Sync Proposal Technical Specification; 131 pages.
IEEE Std 802.16-2004 (Revision of IEEE Std 802.16-2001) IEE Standard for Local and metropolitan area networks; Part 16: Air Interface for Fixed Broadband Wireless Access Systems; IEEE Computer Society and the IEEE Microwave Theory and Techniquest Society; Oct. 1, 2004; 893 pages.
IEEE 802.20-PD-06, IEEE p. 802.20 V14, Jul. 16, 2004, Draft 802.20 Permanent Document, System Requirements for IEEE 802.20 Mobile Broadband Wireless Access Systems—Version 14, 23 pages.
A Network Intrusion Prevention System (NIPS) for High-Speed Networks; by Shimrit Tzur-David; Sep. 2005; 89 pages.
A taxonomy of keyword pattern matching algorithms; by B.W. Watson and G. Zwaan; Computing Science Note 92/27; Eindhoven, Dec. 1992; 51 pages.
A Fast Generic Sequence Matching Algorithm; by David R. Musser and Gor V. Nishanov; Feb. 2, 2001; 64 pages.
A Fast String Searching Algorithm; by Robert S. Boyer (Stanford Research Institute) and J. Strother Moore; (Xerox Palo Research Center); Copyright 1977; pp. 762-772.
Anker Tal
Dolev Danny
Tzur-David Shimrit
Weinsberg Yaron
Ali Mohammad
Marvell International Ltd.
Ruiz Angelica
Yissum Research Development Company of The Hebrew University of
LandOfFree
High-performance pattern matching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-performance pattern matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-performance pattern matching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4164775