Pattern matching

Details Pattern matching Pattern matching

2011-01-25

2011-01-25

Wu, Yicun (Department: 2159)

Data processing: database and file management or data structures

Database and file access

Record, file, and data search and comparisons

C712S017000

Reexamination Certificate

active

07877401

ABSTRACT:
A method for processing data for pattern matching includes: receiving a first sequence of data values; and generating a second sequence of data values based on the first sequence and one or more patterns and history of data values in the first sequence, wherein the second sequence has fewer data values than the first sequence and all subsequences in the first sequence that match at least one of the one or more patterns are represented in the second sequence.

REFERENCES:
patent: 5329405 (1994-07-01), Hou et al.
patent: 5815096 (1998-09-01), Smith
patent: 5831883 (1998-11-01), Suter et al.
patent: 5956724 (1999-09-01), Griffiths
patent: 5990899 (1999-11-01), Whitten
patent: 6012057 (2000-01-01), Mayer et al.
patent: 7394288 (2008-07-01), Agarwal
patent: 7411418 (2008-08-01), Gould et al.
patent: 7461236 (2008-12-01), Wentzlaff
patent: 2003/0051043 (2003-03-01), Wyschogrod et al.
patent: 2003/0110154 (2003-06-01), Ishihara et al.
patent: 2004/0162826 (2004-08-01), Wyschogrod et al.
patent: 2005/0125650 (2005-06-01), Chen et al.
patent: 2005/0132342 (2005-06-01), Van Lunteren
patent: 2005/0286742 (2005-12-01), Rasmussen et al.
patent: 2006/0020595 (2006-01-01), Norton et al.
patent: 2006/0085389 (2006-04-01), Flanagan et al.
patent: 2006/0193159 (2006-08-01), Tan et al.
patent: 2007/0005596 (2007-01-01), Brown et al.
patent: 2007/0124146 (2007-05-01), Van Lunteren
patent: WO 2004/072796 (2004-08-01), None
Wiklund et al, .SoCBUS: Switched network on chip for hard real time Systems, Apr. 22-26, 2003, Proceeds of the Int'l Parallel and Distributed Processing Symposium (IPDPS), pp. 78-85.
Norton, Marc, Optimizing Pattern matching for intrusion detection, 2004, Sourcefire Inc, White Paper.
Takeda et al., Pattern Matching Machine for Text Compressed Using Finite State Model, Oct. 1997, DOI Technical Report, DOI-TR-142.
Aho et al., Efficient String Matching: An Aid to Bibliographic Search, Jun. 1975, Communications of the ACM, vol. 18 No. 6 pp. 333-340.
Amir et al., Efficient Pattern Matching with Scaling, Mar. 1992, Journal of Algorithms, Volume, pp. 344-357.
Kida et al., Multiple Pattern Matching in LZW Compressed Text, Mar. 30-Apr. 1, 1998, Data Compression Conference, 1998, DCC 98 Proceedings, pp. 103-112.
Agarwal, Anant. “Raw Computation,”Scientific Americanvol. 281, No. 2: 44-47, Aug. 1999.
Taylor, Michael Bedford et. al., “Evaluation of the Raw Microprocessor: An Exposed-Wire-Delay Architecture for ILP and Streams,”Proceedings of International Symposium on Computer Architecture, Jun. 2004.
Taylor, Michael Bedford et. al., “Scalar Operand Networks: On-Chip Interconnect for ILP in Partitioned Architectures,”Proceedings of the International Symposium on High Performance Computer Architecture, Feb. 2003.
Taylor, Michael Bedford et. al., “A 16-Issue Multiple-Program-Counter Microprocessor with Point-to-Point Scalar Operand Network,”Proceedings of the IEEE International Solid-State Circuits Conference, Feb. 2003.
Taylor, Michael Bedford et. al., “The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs,”IEEE Micro, pp. 25-35, Mar.-Apr. 2002.
Lee, Walter et. al., “Space-Time Scheduling of Instruction-Level Parallelism on a Raw Machine,”Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS-VIII), San Jose, CA, Oct. 4-7, 1998.
Kim, Jason Sungtae et. al., “Energy Characterization of a Tiled Architecture Processor with On-Chip Networks,”International Symposium on Low Power Electronics and Design, Seoul, Korea, Aug. 25-27, 2003.
Barua, Rajeev et. al., “Compiler Support for Scalable and Efficient Memory Systems,”IEEE Transactions on Computers, Nov. 2001.
Waingold, Elliot et. al., “Baring it all to Software: Raw Machines,”IEEE Computer, pp. 86-93, Sep. 1997.
Lee, Walter et. al., “Convergent Scheduling,”Proceedings of the 35thInternational Symposium on Microarchitecture, Istanbul, Turkey, Nov. 2002.
Wentzlaff, David and Anant Agarwal, “A Quantitative Comparison of Reconfigurable, Tiled, and Conventional Architectures on Bit-Level Computation,”MIT/LCS Technical Report LCS-TR-944, Apr. 2004.
Suh, Jinwoo et. al., “A Performance Analysis of PIM, Stream Processing , and Tiled Processing on Memory-Intensive Signal Processing Kernels,”Proceedings of the International Symposium on Computer Architecture, Jun. 2003.
Barua, Rajeev et. al., “Maps: A Compiler-Managed Memory System for Raw Machines,”Proceedings of the Twenty-Sixth International Symposium on Computer Architecture(ISCA-26), Atlanta, GA, Jun. 1999.
Barua, Rajeev et. al., “Memory Bank Disambiguation using Modulo Unrolling for Raw Machines,”Proceedings of the Fifth International Conference on High Performance Computing, Chennai, India, Dec. 17-20, 1998.
Agarwal, A. et. al., “The Raw Compiler Project,”Proceedings of the Second SUIF Compiler Workshop, Stanford, CA, Aug. 21-23, 1997.
Taylor, Michael Bedford et. al., “Scalar Operand Networks,”IEEE Transactions on Parallel and Distributed Systems(Special Issue on On-Chip Networks), Feb. 2005.
Taylor, Michael. The Raw Prototype Design Document V5.01 [online]. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Sep. 6, 2004 [retrieved on Sep. 25, 2006]. Retrieved from the Internet: <flp://ftp.cag.lcs.mit.edu/pub/raw/documents/RawSpec99.pdf>.
Moritz, Csaba Andras et. al., “Hot Pages: Software Caching for Raw Microprocessors,”MIT/LCS Technical Memo LCS-TM-599, Aug. 1999.
Dharmapurikar, S. & J. Lockwood. “Fast and Scalable Pattern Matching for Content Filtering,”ANCS'05, Oct. 26-28, 2005, Princeton, New Jersey, USA.
Tan, L. & T. Sherwood., “Architectures for Bit-Split String Scanning in Intrusion Detection,”IEEE Computer Society, Jan.-Feb. 2006 (pp. 1-9).
Lin Tan; Sherwood, T., “A high throughput string matching architecture for intrusion detection and prevention”, International Symposium on Computer Architecture (ISCA'05), 2005.
Benjamin C. Brodie, David E. Taylor, Ron K. Cytron, “A Scalable Architecture for High-Throughput Regular-Expression Pattern Matching,” pp. 191-202, International Symposium on Computer Architecture (ISCA'06), 2006.
Fish & Richardson P.C., Unpublished U.S. Appl. No. 11/564,694, filed Nov. 29, 2006, 55 pages.

Affiliated with

Also associated with

Rating

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 Pattern matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2686969