Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2011-05-24
2011-05-24
Ly, Cheyne D (Department: 2168)
Data processing: database and file management or data structures
Database design
Data structure types
C709S224000, C709S227000, C709S228000, C709S231000
Reexamination Certificate
active
07949683
ABSTRACT:
An apparatus, and corresponding method, for traversing a compressed graph used in performing a search for a match of at least one expression in an input stream is presented. The compressed graph includes a number of interconnected nodes connected solely by valid arcs. A valid arc of a current node represents a character match in an expression of a character associated with the current node. Arcs which are not valid may be pruned. Non-valid arcs may include arcs which point back to a designated node(s), or arcs that point to the same next node as the designated node(s) for the same character. Each valid arc may comprise a next node pointer, a hash function, and a copy of an associated character. The hash function may be used to manage a retrieval process used by a walker traversing the compressed node. The walker may also use a comparison function to verify the correct arc has been retrieved.
REFERENCES:
patent: 5230061 (1993-07-01), Welch
patent: 6047283 (2000-04-01), Braun
patent: 6076087 (2000-06-01), Suciu
patent: 6192282 (2001-02-01), Smith et al.
patent: 6925641 (2005-08-01), Elabd
patent: 7028141 (2006-04-01), Ohba
patent: 7046848 (2006-05-01), Olcott
patent: 7085918 (2006-08-01), Sharangpani et al.
patent: 7093023 (2006-08-01), Lockwood et al.
patent: 7185081 (2007-02-01), Liao
patent: 7188168 (2007-03-01), Liao
patent: 7225188 (2007-05-01), Gai et al.
patent: 7301541 (2007-11-01), Hansen et al.
patent: 7305372 (2007-12-01), Bridges et al.
patent: 7454588 (2008-11-01), Greicar
patent: 7689530 (2010-03-01), Williams, Jr. et al.
patent: 2002/0099909 (2002-07-01), Meyer
patent: 2003/0051043 (2003-03-01), Wyschogrod et al.
patent: 2003/0065800 (2003-04-01), Wyschogrod et al.
patent: 2003/0110208 (2003-06-01), Wyschogrod et al.
patent: 2003/0195874 (2003-10-01), Akaboshi
patent: 2004/0049596 (2004-03-01), Schuehler et al.
patent: 2004/0059443 (2004-03-01), Sharangpani
patent: 2004/0071152 (2004-04-01), Wolrich et al.
patent: 2004/0083387 (2004-04-01), Dapp et al.
patent: 2004/0098384 (2004-05-01), Min et al.
patent: 2004/0162826 (2004-08-01), Wyschogrod et al.
patent: 2004/0172234 (2004-09-01), Dapp et al.
patent: 2004/0176945 (2004-09-01), Inagaki et al.
patent: 2004/0179477 (2004-09-01), Lincoln et al.
patent: 2004/0215593 (2004-10-01), Sharangpani et al.
patent: 2004/0225999 (2004-11-01), Nuss
patent: 2004/0267779 (2004-12-01), Carter et al.
patent: 2005/0012521 (2005-01-01), Sharangpani et al.
patent: 2005/0097514 (2005-05-01), Nuss
patent: 2005/0108518 (2005-05-01), Pandya
patent: 2005/0238010 (2005-10-01), Panigrahy et al.
patent: 2005/0238022 (2005-10-01), Panigrahy
patent: 2005/0240999 (2005-10-01), Rubin et al.
patent: 2005/0251509 (2005-11-01), Pontius
patent: 2006/0059165 (2006-03-01), Bosloy et al.
patent: 2006/0069872 (2006-03-01), Bouchard et al.
patent: 2006/0075206 (2006-04-01), Bouchard et al.
patent: 2006/0085533 (2006-04-01), Hussain et al.
patent: 2006/0242123 (2006-10-01), Williams
patent: 2007/0038798 (2007-02-01), Bouchard et al.
patent: 2007/0133593 (2007-06-01), Shankara
patent: 2007/0276788 (2007-11-01), Cohen
patent: 2008/0046423 (2008-02-01), Alicherry et al.
patent: 2009/0037379 (2009-02-01), Bou-Diab et al.
patent: 2009/0119399 (2009-05-01), Hussain et al.
patent: 2009/0138494 (2009-05-01), Goyal et al.
patent: 2010/0114973 (2010-05-01), Goyal
patent: 1 607 823 (2005-12-01), None
patent: WO 2004/013777 (2004-02-01), None
patent: WO 2006/031659 (2006-03-01), None
patent: WO 2009/070191 (2009-06-01), None
patent: WO 2009/070192 (2009-06-01), None
Tewari et al., A Parallel DFA Minimization Algorithm, S. Sahni et al. (Eds.) HiPC 2002, LNCS 2552, pp. 31-40, 2002.
Ciura et al., Software-Practice and Experience, 31:1007-1090, 2001.
Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom Filters, by Sarang Dharmapurikar, Michael Attig, John W. Lockwood, Washington University Dept. Of Computer Science and Engineering : Technical Report WUCS-2004-012, 2004.
Ramakrishnan et al., Proceedings of the 2006 Conference on Emperical Methods in Natural Language Processing (EMNLP 2006), pp. 492-500, Sydney, Jul. 2006.
Ciura et al., How to squeeze a lexicon, Software—Practice and Experience 2001; 31(11):1-11.
Alicherry et al., IEEE, pp. 187-196, 2006.
Candan et al., VLDB '06 Sep. 12-15, 2006, Seoul, Korea, pp. 559-570.
Deshpande, P.S. and Kakde, 0,G., “C & Data Structures,” Charles River Media: 217-221 [no. date available].
Anonymous, Graph (data structure) [online] Oct. 2007 [retrieved on Oct. 3, 2007] Retrieved from the Internet URL: http://en.wikipedia.org/w/index.php?title=graph—(data structure) &o...
Daciuk, J. “Experiments with Automata Compression,” Database Inspec [online] The Institution of Electrical Engineers, GB (2000) and Proceedings of Fifth International Conference on Implementation and Application of Automata: 113-119 (Jul. 24, 2000-Jul. 25, 2000).
International Search Report from PCT/US2008/011545 mailed on Mar. 2, 2009.
International Search Report from PCT/US2008/011543 mailed on Mar. 2, 2009.
Written Opinion for Int'l Application No. PCT/US2008/011545, mailed on Mar. 2, 2009.
Schuehler, David V., et al., “Architecture for a Hardware-Based, TCIP/IP Content-Processing System,”IEEE Computer Society, pp. 62-69 (Jan.-Feb. 2004).
Handout 1, “Regular Expressions and Finite Automata,” pp. 1-8 http://www.developer.com/tech/article.php.
Bradley, Tony, “Introduction to Intrusion Detection Systems(IDS),” http:/
etsecurity.about.com/cs/hackertools/a/aa030504.htm and http://searchsecurity.techtarget.com/sDefinition/0,,sid14—gci295031,00.html.
Mertz, David, “Learning to Use Regular Expressions, Introduction to the Tutorial,” Gnosis Software, http://gnosis.cx/publish/programming/regular—expressions.html, pp. 1-16, downloaded Jan. 11, 2005.
Melvin, S., et al., “A Massively Multithreaded Packet Processor,” Paper presented at NP2: Workshop on Network Processors, held in conjunction withThe 9thInternational Symposium on High-Performance Computer Architecture, Anaheim, CA (Feb, 2003).
Vahid, F., “The Softening of Hardware,” Computer, 36(4): 27-34 (Apr. 2003).
McConnell, S., “Who Needs Software Engineering?” IEEE Software, 18(1): 5-8 (Jan.-Feb. 2001).
Tanenbaum, A., “Structured computer organization” (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ (1984).
International Preliminary Report on Patentability and Written Opinion, PCT/US2008/011545, mailed Jun. 10, 2010 (3795.1030-001 PCT).
International Search Report, PCT/US2005/032236, mailed May 16, 2006 (3795.1011-003).
Written Opinion of the International Searching Authority, PCT/US2005/032236, mailed May 16, 2006 (3795.1011-003).
International Preliminary Report on Patentability and Written Opinion for PCT/US2008/011543, mailed Jun. 10, 2010.
European Examination Report for European Application No. 05812863.8, mailed May 14, 2008.
Cavium Networks, Inc.
Hamilton Brook Smith & Reynolds P.C.
Ly Cheyne D
LandOfFree
Method and apparatus for traversing a compressed... 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 traversing a compressed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for traversing a compressed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2668204