Method and apparatus for optimizing string search operations

Details Method and apparatus for optimizing string search operations Method and apparatus for optimizing string search operations

2007-03-21

2009-12-22

Jalil, Neveen Abel (Department: 2165)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

07636717

ABSTRACT:
A search tree embodying a plurality of signatures to be compared with an input string of characters and including a number of success transitions characterized by a success size parameter and including a number of failure transitions characterized by a failure size parameter is selectively modified to achieve a desired balance between processing speed and memory area requirements.

REFERENCES:
patent: 5051886 (1991-09-01), Kawaguchi et al.
patent: 5151697 (1992-09-01), Bunton
patent: 5278981 (1994-01-01), Kawaguchi et al.
patent: 5299206 (1994-03-01), Beaverson et al.
patent: 5386413 (1995-01-01), McAuley et al.
patent: 5414704 (1995-05-01), Spinney
patent: 5440715 (1995-08-01), Wyland
patent: 5440753 (1995-08-01), Hou et al.
patent: 5452451 (1995-09-01), Akizawa et al.
patent: 5469161 (1995-11-01), Bezek
patent: 5497488 (1996-03-01), Akizawa et al.
patent: 5615378 (1997-03-01), Nishino et al.
patent: 5712971 (1998-01-01), Stanfill et al.
patent: 5781431 (1998-07-01), Duret et al.
patent: 5963942 (1999-10-01), Igata
patent: 5995963 (1999-11-01), Nanba et al.
patent: 6011795 (2000-01-01), Varghese et al.
patent: 6012057 (2000-01-01), Mayer et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6067574 (2000-05-01), Tzeng
patent: 6115716 (2000-09-01), Tikkanen et al.
patent: 6185524 (2001-02-01), Carus et al.
patent: 6311183 (2001-10-01), Cohen
patent: 6377942 (2002-04-01), Hinsley et al.
patent: 6421660 (2002-07-01), Glaise
patent: 6425099 (2002-07-01), Lattmann et al.
patent: 6487566 (2002-11-01), Sundaresan
patent: 6505206 (2003-01-01), Tikkanen et al.
patent: 6538911 (2003-03-01), Allan et al.
patent: 6546391 (2003-04-01), Tsuruoka
patent: 6560610 (2003-05-01), Eatherton et al.
patent: 6785677 (2004-08-01), Fritchman
patent: 6856981 (2005-02-01), Wyschogrod et al.
patent: 6980992 (2005-12-01), Hursey et al.
patent: 7058821 (2006-06-01), Parekh et al.
patent: 7134143 (2006-11-01), Stellenberg et al.
patent: 7139753 (2006-11-01), Bass et al.
patent: 7139837 (2006-11-01), Parekh et al.
patent: 2003/0041163 (2003-02-01), Rhoades et al.
patent: 2003/0048785 (2003-03-01), Calvignac et al.
patent: 2003/0051043 (2003-03-01), Wyschogrod et al.
patent: 2003/0065774 (2003-04-01), Steiner et al.
patent: 2003/0065800 (2003-04-01), Wyschogrod et al.
patent: 2004/0177319 (2004-09-01), Horn
patent: 2004/0267732 (2004-12-01), Luk et al.
patent: 2005/0114306 (2005-05-01), Shu et al.
patent: 2006/0059196 (2006-03-01), Sato et al.
patent: 2006/0259508 (2006-11-01), Sikdar et al.
patent: 2007/0130140 (2007-06-01), Cytron et al.
patent: 2008/0071781 (2008-03-01), Ninan et al.
patent: 0408188 (1991-01-01), None
Hierons, Rob M., Optimizing the Length of Checking Seuences, May 2006, IEEE ransactions on Computers, vol. 55 Issue 5, pp. 618-629.
A Search Algorithm for Table Entries with Non-Contiguous Wildcarding, Paul F. Tsuchiya, Bellcore, 1991, pp. 1-10.
A Tree-Based Packet Routing Table for Berkeley Unix, Keith Sklower, Berkeley Technical Report, UC Berkeley, CA, USA, 1991, pp. 1-14.
Efficient String Matching: An Aid to Bibliographic Search, Aho, A. V. and Corasick, M. J., Communications of the Association of Computing Machinery (ACM) Jun. 1975, vol. 18, No. 6. pp. 333-340.
Fast Routing Table Lookup Using CAMs, Anthony J. McAuley and Paul Francis, 1993, pp. 1382-1391, IEEE.
Gigabit Rate Packet Pattern-Matching Using TCAM, Fang Yu, Randy H. Katz, and T.V. Lakshman, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), Oct. 5-8, 2004, pp. 174-183.
High Speed Pattern Matching for Network IDS/IPS, Alicherry, Muthuprasanna and Kumar, IEEE Sep. 2006, 1-4244-0596-9/06.
Memory Organization Scheme for the Implementation of Routing Tables in High Performance IP Routers, document dated Nov. 21, 2003, 6 pages.
Over 10Gbps String Matching Mechanism for Multi-stream Packet Scanning Systems, Yutaka Sugawara, Mary Inaba, and Kei Hiraki, FPL 2004, LNCS 3203, pp. 484-493, 2004, J. Becker, M. Platzner, S. Vernalde, Editors.
Putting Routing Tables in Silicon, Tong-Bi Pei and Charles Zukowski, IEEE Network Magazine, Jan. 1992, vol. 6, No. 1, pp. 42-50.
VLSI Implementation of Routing Tables: Tries and CAMs, Tong-Bi Pei and Charles Zukowski, 1991 IEEE Infocom'91, Proceedings vol. 2, pp. 515-524.

Affiliated with

Also associated with

Rating

Method and apparatus for optimizing string search operations does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for optimizing string search operations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for optimizing string search operations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4144995