Source: http://www.google.com/patents/US7917299?dq=%22Meaning-based+advertising+and+document+relevance+determination%22
Timestamp: 2015-07-31 06:32:47
Document Index: 69785368

Matched Legal Cases: ['art) 512', 'art 1', 'art 2', 'art 3', 'art 4', 'art 1', 'art 2', 'art 3', 'art 4']

Patent US7917299 - Method and apparatus for performing similarity searching on a data stream ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsAn apparatus and method for performing similarity searching on a data stream with respect to a query string are disclosed, where the data stream comprises a plurality of data substrings, and where the query string comprises a plurality of query substrings. A programmable logic device is used to filter...http://www.google.com/patents/US7917299?utm_source=gb-gplus-sharePatent US7917299 - Method and apparatus for performing similarity searching on a data stream with respect to a query stringAdvanced Patent SearchPublication numberUS7917299 B2Publication typeGrantApplication numberUS 11/359,285Publication dateMar 29, 2011Filing dateFeb 22, 2006Priority dateMar 3, 2005Fee statusPaidAlso published asCA2599382A1, EP1859378A2, US8515682, US20070067108, US20110231446, US20140067830, WO2006096324A2, WO2006096324A3Publication number11359285, 359285, US 7917299 B2, US 7917299B2, US-B2-7917299, US7917299 B2, US7917299B2InventorsJeremy Daniel Buhler, Roger Dean Chamberlain, Mark Allen Franklin, Kwame Gyang, Arpith Chacko Jacob, Praveen Krishnamurthy, Joseph Marion LancasterOriginal AssigneeWashington UniversityExport CitationBiBTeX, EndNote, RefManPatent Citations (99), Non-Patent Citations (158), Referenced by (22), Classifications (12), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetMethod and apparatus for performing similarity searching on a data stream with respect to a query string
A computer readable form of the Sequence Listing is provided herein, contained in the file named “60346_Seq ListingST25.txt”, which is 2822 bytes (as measured in MS-DOS), and is herein incorporated by reference. This Sequence Listing consists of SEQ ID Nos: 1-13.
Examples of this type of searching can be found in a paper entitled Biosequence Similarity Search On The Mercury System, P. Krishnamurthy, J. Buhler, R. D. Chamberlain, M. A. Franklin, K. Gyang, and J. Lancaster, In Proceedings of the 15th IEEE International Conference on Application-Specific Systems, Architectures, and Processors (ASAP04), Sep. 2004, Pages 365-375 (2004). Another example is a paper entitled: NCBI BLASTN STAGE 1 IN RECONFIGURABLE HARDWARE, by Kwame Gyang, Department of Computer Science and Engineering, Washington University, Aug. 2004, Technical Report WUCSE-2005-30. Another example is a paper entitled “BLASTN Redundancy Filter in Reprogrammable Hardware”, by C. Behrens, J. Lancaster, and B. Wun, Department of Computer Science and Engineering, Washington University, Final Project Submission, Fall 2003. These papers are each incorporated by reference, in their entirety.
BLAST includes a pipeline of computations that filter a stream of characters from a database to identify meaningful matches to a query. To keep pace with growing databases and queries, this stream must be filtered at increasingly higher rates. One path to higher performance is to develop a specialized processor that offloads part of BLAST's computation from a general-purpose processor, e.g., CPU. Illustrative, but nonlimiting, examples of processors that are known to accelerate or replace BLAST include the ASIC-based Paracel GeneMatcher™ and the FPGA-based TimeLogic DecypherBLAST™ engine.
FIG. 1 shows a block diagram of a high level overview of a three (3) stage pipeline that is generally indicated by numeral 50. The database sequences 52 are shown entering the pipeline 50. The first stage (Stage 1) 54 provides a word matching function that detects substrings of fixed length “w” in the stream that perfectly match a substring of the query, e.g., w=11, for DNA. These short matches are also known as “w-mers.” Each matching w-mer is forwarded to a second stage (Stage 2), which is an ungapped extension 56, which extends the w-mer on either side to identify a longer pair of sequences around the w-mer that match with at most a small number of mismatched characters. These longer matches are identified as high-scoring segment pairs (“HSP”s) or ungapped alignments.
A preferred hardware platform for pipeline 100 is that disclosed in FIG. 3 and is generally indicated by numeral 800. Additional details about this hardware platform are disclosed in: (1) U.S. Pat. No. 6,711,558 entitled “Associative Database Scanning and Information Retrieval”; (2) pending U.S. patent application Ser. No. 10/153,151, filed May 21, 2002 and entitled “Associative Database Scanning and Information Retrieval Using FPGA Devices” (published as U.S. patent application publication 2003/0018630); (3) pending PCT application PCT/US04/16398 filed May 21, 2004 and entitled “Intelligent Storage and Processing Using FPGA Devices”; and (4) a paper on “Achieving Real Data Throughput for an FPGA Co-Processor on Commodity Server Platforms” by Chamberlain et al., published in Proc. of 1st Workshop on Building Block Engine Architectures for Computers and Networks, Boston, Mass., Oct. 2004; and a paper on “Acceleration of Ungapped Extension in Mercury BLAST” by Lancaster et al., was published on Nov. 12, 2005 for the Seventh (7th) Workshop on Media and Streaming Processors held in conjunction with the Thirty-Eighth (38th) International Symposium on Microarchitecture (MICRO-38) in Barcelona, Spain, the entire disclosures of all of which are incorporated herein by reference.
The input processing unit 104 is preferably configured to receive a biological sequence data stream 120 as an input from a sequence database, which is shown in FIG. 2. This database stream 120 represents a database sequence that can be broken down into a plurality of substrings, each substring having a base length “w.” Such substrings are referred to herein as database w-mers. The input processing unit 104 preferably outputs a parallel stream of q database w-mers (or sequence w-mers) 122 i, wherein q represents the total number of database w-mers that can be simultaneously processed by the Bloom filter stage 106.
The Bloom filter stage 106, as shown in FIG. 2, operates to process each database w-mer to determine whether it is a possible match with a query w-mer. A query w-mer being a substring of base length “w” derived from a query sequence. By definition, Bloom filters will not produce any false negatives between the database w-mers and the query w-mers, but Bloom filters are highly likely to produce some number of false positive matches between the database w-mers and the query w-mers. Because of the presence of these false positives, the “yes” responses of the Bloom filter to database w-mers are best referred to as possible matches.
A preferred Bloom filter architecture within the Bloom filter stage 106 is shown in FIGS. 6( a)-6(c). FIG. 6( a) depicts an exemplary Bloom filter 400. Within the Bloom filter 400, a database w-mer is processed by “k” hash functions 402, each hash function “i” operating to map the database w-mer to a bit in the 1�m dual port block RAM (BRAM) unit 404 i that corresponds to that hash function i. If all of the bits to which that database w-mer maps within BRAMs 4041 through 404 k are set (e.g., equal to 1), then logic unit 406, e.g., AND logic unit, will receive all 1's on its input lines, thereby producing a “yes” response as to whether that database w-mer is a possible match with a query w-mer.
In a second alternative embodiment, there is a need to reduce the number of hash table look-ups so that near perfect hashing functions are used to build the hash table 112 and perform the mapping of hashing stage 110. Near perfect hashing can be defined as hashing that operates to provide a decreased likelihood of collisions relative to the likelihood of collisions provided by ordinary hashing functions, and wherein the hashing approaches a perfect hash the longer that it executes. Near perfect hashing functions are explained in greater detail in some of the publications incorporated by reference. The preferred near perfect hashing functions are those in the family H3 chosen to be of full rank. The family of hashing functions that is designated as “H3” as well as the concept of “full rank” are fully described and disclosed in numerous publications in this area. More generally, the near-perfect hashing algorithm described herein may be used to generate a mapping of a set of binary strings of common length equal to n, referred to as keys, to indices into a hash table, so that few or no pairs of keys map to the same location in the table. The hashing logic of hashing stage 110 is preferably implemented on the programmable logic device 102, e.g., FPGA, to map possibly matching database w-mers to their respective positions in the query sequence.
Also, it is worth noting that the implementation on an FPGA of the FPGA pipeline stages for the programmable logic device 102 described herein is within the skill of a person having ordinary skill in the art following the teachings herein and the teachings of (1) U.S. Pat. No. 6,711,558 entitled “Associative Database Scanning and Information Retrieval”; (2) pending U.S. patent application Ser. No. 10/153,151, filed May 21, 2002 and entitled “Associative Database Scanning and Information Retrieval Using FPGA Devices” (published as U.S. patent application publication 2003/0018630); and (3) pending PCT application PCT/US04/16398 filed May 21, 2004 and entitled “Intelligent Storage and Processing Using FPGA Devices”; the entire disclosures of all of which have been incorporated herein by reference. For example, see the description for FIG. 8 in PCT application PCT/US04/16398.
The ungapped extension analysis with a preferred software program, i.e., NCBI BLAST, is generally indicated by numeral 62 and begins at the end of the w-mer and extends left. The extension stops when the running score drops 10 below the maximum score (as indicated by the arrows). This is also indicated as the user modifiable “X-drop” parameter. The same computation is then performed in the other direction. The final substring is the concatenation of the best substrings from the left and right extensions.
This prefilter extension algorithm implements a dynamic programming recurrence that simultaneously computes the start and end of the best high-scoring segment pair (HSP) in a predetermined window. The first step 502 is to calculate predetermined window boundaries. The current position within a window is indicated by a variable “i”′. There is then a reset of the score “γ” of the best high-scoring segment pair (HSP) that terminates at position i of the window and the score “Γ” of the best high-scoring segment pair (HSP) ending at or before i to zero (0). This is followed by a reset of the variable “B” as well as the two endpoints Bmax and Emax of the best high scoring segment pair (HSP) ending at or before i to the value of zero (0).
Then, the algorithm determines if the score γ of the best high-scoring segment pair (HSP) is greater than zero (0) 510. If this determination is positive, then there is a determination if the score “γ” of the best high-scoring segment pair (HSP) that terminates at position i of the window is greater than the score “Γ” of the best high-scoring segment pair (HSP) ending at or before i and if i (position in the window) is greater than the end of a short word match w-mer (WmerEnd) 511.
If this determination in step 510 is negative, then there is a determination of whether i is less than the start of the short word match w-mer (WmerStart) 512. If i is less than the start of the short word match w-mer, then the variable B is set to the current position within a window i incremented by one (1) and the score “γ” of the best high-scoring segment pair (HSP) is set to (0) zero 516. The next step is then a determination if i is equal to the length of the window Lw 519. If the determination in step 511 is positive, then the score “Γ” of the best high-scoring segment pair (HSP) ending at or before i is set to the score “γ” of the best high-scoring segment pair (HSP) that terminates at i, the endpoint Bmax of the best high-scoring segment pair (HSP) “Γ” ending at or before i is set to the variable B and the endpoint Emax of the best high-scoring segment pair (HSP) is set to i (position in the window) 514. The next step is then a determination if i is equal to the length of the window Lw 519. Moreover, if the determination in step 511 is negative, then there is also a determination if i is equal to the length of the window Lw 519.
If the determination in step 519 is negative, then the variable i is incremented by one (1) in step 517 and the process is returned to step 504. If this determination in step 519 is positive, then the software program proceeds to the next program step 518, which is a determination whether the score of the best high-scoring segment pair (HSP) “Γ” is greater than the variable T in step 518. If this determination is positive, then a value of “true” is returned 520 and the software program ends 527.
If the determination in step 518 is negative, this is followed by a determination of whether the position of the endpoint Bmax of the best high-scoring segment pair (HSP) is equal to zero 522. If this determination is positive, then a value of “true” is returned 526 and the software program ends 527.
Finally, if the determination in step 522 is negative, there is a determination of whether the endpoint Emax of the best high-scoring segment pair (HSP) is equal to the length of the window Lw 524. If this determination is positive, then a value of “true” is returned 526 and the algorithm ends 527 and if this determination is negative, then a value of “false” is returned 528 and the algorithm will again end 527.
The scoring module 98 is preferably, but not necessarily, arranged as a classic systolic array. The data from the previous stage are read on each clock pulse and results are output to the following stage on the next clock pulse. Storage for comparison scores in successive pipeline stages 97 decrease in every successive stage and is shown in FIG. 13. This decrease is possible because the comparison score for window position “i” is consumed in the ith pipeline stage and may then be discarded, since later stages inspect only window positions that are greater than i.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3601808Jul 18, 1968Aug 24, 1971Bell Telephone Labor IncAdvanced keyword associative access memory systemUS3611314Sep 9, 1969Oct 5, 1971Texas Instruments IncDynamic associative data processing systemUS3729712Feb 26, 1971Apr 24, 1973Eastman Kodak CoInformation storage and retrieval systemUS3824375Aug 28, 1970Jul 16, 1974Financial Security Syst IncMemory systemUS3848235Oct 24, 1973Nov 12, 1974IbmScan and read control apparatus for a disk storage drive in a computer systemUS3906455Mar 15, 1974Sep 16, 1975Boeing Computer Services IncAssociative memory deviceUS4081607Nov 1, 1976Mar 28, 1978Rockwell International CorporationKeyword detection in continuous speech using continuous asynchronous correlationUS4314356Oct 24, 1979Feb 2, 1982Bunker Ramo CorporationHigh-speed term searcherUS4464718Jul 30, 1982Aug 7, 1984International Business Machines CorporationAssociative file processing method and apparatusUS4550436Jul 26, 1983Oct 29, 1985At&T Bell LaboratoriesParallel text matching methods and apparatusUS4823306Aug 14, 1987Apr 18, 1989International Business Machines CorporationText search systemUS5050075Oct 4, 1988Sep 17, 1991Bell Communications Research, Inc.High performance VLSI data filterUS5101424Sep 28, 1990Mar 31, 1992Northern Telecom LimitedMethod for generating a monitor program for monitoring text streams and executing actions when pre-defined patterns, are matched using an English to AWK language translatorUS5140692Jun 6, 1990Aug 18, 1992Ricoh Company, Ltd.Document retrieval system using analog signal comparisons for retrieval conditions including relevant keywordsUS5226165Jul 24, 1991Jul 6, 1993International Computers LimitedDatabase search processor for real-time adaptive searching based on request and data structureUS5243655Mar 16, 1992Sep 7, 1993Symbol Technologies Inc.System for encoding and decoding data in machine readable graphic formUS5249292Mar 10, 1992Sep 28, 1993Chiappa J NoelData packet switch using a primary processing unit to designate one of a plurality of data stream control circuits to selectively handle the header processing of incoming packets in one data packet streamUS5265065Oct 8, 1991Nov 23, 1993West Publishing CompanyMethod and apparatus for information retrieval from a database by replacing domain specific stemmed phases in a natural language to create a search queryUS5319776Sep 29, 1992Jun 7, 1994Hilgraeve CorporationIn transit detection of computer virus with safeguardUS5339411Oct 22, 1993Aug 16, 1994Pitney Bowes Inc.Method for managing allocation of memory spaceUS5347634Mar 15, 1990Sep 13, 1994Hewlett-Packard CompanySystem and method for directly executing user DMA instruction from user controlled process by employing processor privileged work buffer pointersUS5371794Nov 2, 1993Dec 6, 1994Sun Microsystems, Inc.Method and apparatus for privacy and authentication in wireless networksUS5388259May 15, 1992Feb 7, 1995Bell Communications Research, Inc.System for accessing a database with an iterated fuzzy query notified by retrieval responseUS5404411Dec 27, 1990Apr 4, 1995Xerox CorporationBitmap-image pattern matching apparatus for correcting bitmap errors in a printing systemUS5418951Sep 30, 1994May 23, 1995The United States Of America As Represented By The Director Of National Security AgencyMethod of retrieving documents that concern the same topicUS5421028Mar 31, 1994May 30, 1995Hewlett-Packard CompanyProcessing commands and data in a common pipeline path in a high-speed computer graphics systemUS5440723Jan 19, 1993Aug 8, 1995International Business Machines CorporationAutomatic immune system for computers and computer networksUS5461712Apr 18, 1994Oct 24, 1995International Business Machines CorporationQuadrant-based two-dimensional memory managerUS5463701Jan 18, 1994Oct 31, 1995International Business Machines CorporationSystem and method for pattern-matching with error control for image and video compressionUS5465353Apr 1, 1994Nov 7, 1995Ricoh Company, Ltd.Image matching and retrieval by multi-access redundant hashingUS5481735Dec 28, 1992Jan 2, 1996Apple Computer, Inc.Method for modifying packets that meet a particular criteria as the packets pass between two layers in a networkUS5497488Mar 13, 1995Mar 5, 1996Hitachi, Ltd.System for parallel string search with a function-directed parallel collation of a first partition of each string followed by matching of second partitionsUS5544352Jun 14, 1993Aug 6, 1996Libertech, Inc.Method and apparatus for indexing, searching and displaying dataUS5546578Jun 6, 1995Aug 13, 1996Nippon Steel CorporationData base retrieval system utilizing stored vicinity feature valuesUS5596569Oct 10, 1995Jan 21, 1997Excel, Inc.Telecommunications switch with improved redundancyUS5687297Jun 29, 1995Nov 11, 1997Xerox CorporationMultifunctional apparatus for appearance tuning and resolution reconstruction of digital imagesUS5701464Sep 15, 1995Dec 23, 1997Intel CorporationParameterized bloom filtersUS5712942May 13, 1996Jan 27, 1998Lucent Technologies Inc.Optical communications system having distributed intelligenceUS5721898Sep 2, 1992Feb 24, 1998International Business Machines CorporationMethod and system for data search in a data processing systemUS5781772May 15, 1995Jul 14, 1998Digital Equipment CorporationCompressed prefix matching database searchingUS5805832Jun 2, 1995Sep 8, 1998International Business Machines CorporationSystem for parametric text to text language translationUS5813000Mar 14, 1996Sep 22, 1998Sun Micro SystemsB tree structure and methodUS5819273Apr 30, 1997Oct 6, 1998Apple Computer, Inc.Method and apparatus for searching for information in a network and for controlling the display of searchable information on display devices in the networkUS5826075Nov 27, 1991Oct 20, 1998International Business Machines CorporationAutomated programmable fireware store for a personal computer systemUS5886701Jun 27, 1996Mar 23, 1999Microsoft CorporationGraphics rendering device and method for operating sameUS5913211Jun 26, 1996Jun 15, 1999Fujitsu LimitedDatabase searching method and system using retrieval data set display screenUS5930753Mar 20, 1997Jul 27, 1999At&T CorpCombining frequency warping and spectral shaping in HMM based speech recognitionUS5978801Nov 18, 1997Nov 2, 1999Sharp Kabushiki KaishaCharacter and/or character-string retrieving method and storage medium for use for this methodUS5991881Nov 8, 1996Nov 23, 1999Harris CorporationNetwork surveillance systemUS5995963Mar 4, 1997Nov 30, 1999Fujitsu LimitedApparatus and method of multi-string matching based on sparse state transition listUS6006264Mar 30, 1998Dec 21, 1999Arrowpoint Communications, Inc.Method and system for directing a flow between a client and a serverUS6023760May 16, 1997Feb 8, 2000Xerox CorporationModifying an input string partitioned in accordance with directionality and length constraintsUS6028939Jan 3, 1997Feb 22, 2000Redcreek Communications, Inc.Data security system and methodUS6044407Oct 22, 1993Mar 28, 2000British Telecommunications Public Limited CompanyInterface for translating an information message from one protocol to anotherUS6067569Jul 10, 1997May 23, 2000Microsoft CorporationFast-forwarding and filtering of network packets in a computer systemUS6073160Dec 18, 1996Jun 6, 2000Xerox CorporationDocument communications controllerUS6105067Jun 5, 1998Aug 15, 2000International Business Machines Corp.Connection pool management for backend servers using common interfaceUS6134551Jan 8, 1996Oct 17, 2000Intel CorporationMethod of caching digital certificate revocation listsUS6147976Jun 24, 1996Nov 14, 2000Cabletron Systems, Inc.Fast network layer packet filterUS6169969Feb 10, 1999Jan 2, 2001The United States Of America As Represented By The Director Of The National Security AgencyDevice and method for full-text large-dictionary string matching using n-gram hashingUS6175874Feb 9, 1998Jan 16, 2001Fujitsu LimitedPacket relay control method packet relay device and program memory mediumUS6226676Oct 7, 1998May 1, 2001Nortel Networks CorporationConnection establishment and termination in a mixed protocol networkUS6279113Jun 4, 1998Aug 21, 2001Internet Tools, Inc.Dynamic signature inspection-based network intrusion detectionUS6317795Jul 22, 1997Nov 13, 2001International Business Machines CorporationDynamic modification of multimedia contentUS6339819May 3, 2000Jan 15, 2002Src Computers, Inc.Multiprocessor with each processor element accessing operands in loaded input buffer and forwarding results to FIFO output bufferUS6377942Jul 22, 1999Apr 23, 2002International Computers LimitedMultiple string search methodUS6381242Aug 29, 2000Apr 30, 2002Netrake CorporationContent processorUS6389532Apr 20, 1998May 14, 2002Sun Microsystems, Inc.Method and apparatus for using digital signatures to filter packets in a networkUS6397259May 29, 1998May 28, 2002Palm, Inc.Method, system and apparatus for packet minimized communicationsUS6397335Aug 26, 1999May 28, 2002Ameritech CorporationComputer virus screening methods and systemsUS6412000Nov 23, 1998Jun 25, 2002Packeteer, Inc.Method for automatically classifying traffic in a packet communications networkUS6430272Apr 30, 1998Aug 6, 2002Matsushita Electric Industrial Co., Ltd.Message switching apparatus for processing message according to message processing procedureUS6463474Jul 2, 1999Oct 8, 2002Cisco Technology, Inc.Local authentication of a client at a network deviceUS6499107Dec 29, 1998Dec 24, 2002Cisco Technology, Inc.Method and system for adaptive network security using intelligent packet analysisUS6578147Jan 15, 1999Jun 10, 2003Cisco Technology, Inc.Parallel intrusion detection sensors with load balancing for high speed networksUS6625150Dec 16, 1999Sep 23, 2003Watchguard Technologies, Inc.Policy engine architectureUS6704816Jul 25, 2000Mar 9, 2004Sun Microsystems, Inc.Method and apparatus for executing standard functions in a computer system using a field programmable gate arrayUS6711558Apr 7, 2000Mar 23, 2004Washington UniversityAssociative database scanning and information retrievalUS6765918Jun 16, 1999Jul 20, 2004Teledata Networks, Ltd.Client/server based architecture for a telecommunications networkUS6772345Feb 8, 2002Aug 3, 2004Networks Associates Technology, Inc.Protocol-level malware scannerUS6785677May 2, 2001Aug 31, 2004Unisys CorporationMethod for execution of query to search strings of characters that match pattern with a target string utilizing bit vectorUS6804667Nov 30, 1999Oct 12, 2004Ncr CorporationFilter for checking for duplicate entries in databaseUS6807156Nov 7, 2000Oct 19, 2004Telefonaktiebolaget Lm Ericsson (Publ)Scalable real-time quality of service monitoring and analysis of service dependent subscriber satisfaction in IP networksUS6886103Oct 27, 2000Apr 26, 2005Lucent Technologies Inc.Method and apparatus for extending network address translation for unsupported protocolsUS6931408Aug 24, 2001Aug 16, 2005E.C. Outlook, Inc.Method of storing, maintaining and distributing computer intelligible electronic dataUS6931545Aug 28, 2000Aug 16, 2005Contentguard Holdings, Inc.Systems and methods for integrity certification and verification of content consumption environmentsUS6944168May 4, 2001Sep 13, 2005Slt Logic LlcSystem and method for providing transformation of multi-protocol packets in a data streamUS6978223Sep 4, 2002Dec 20, 2005Bbnt Solutions LlcSystems and methods for network performance measurement using packet signature collectionUS6980976Aug 13, 2001Dec 27, 2005Oracle International Corp.Combined database index of unstructured and structured columnsUS6981054Jul 18, 2000Dec 27, 2005Advanced Micro Devices, Inc.Flow control arrangement in a network switch based on priority trafficUS7019674Aug 2, 2004Mar 28, 2006Nec Laboratories America, Inc.Content-based information retrieval architectureUS7046848Aug 21, 2002May 16, 2006Olcott Peter LMethod and system for recognizing machine generated character glyphs and icons in graphic imagesUS7065482May 17, 2001Jun 20, 2006International Business Machines CorporationInternet traffic analysis toolUS7093023May 21, 2002Aug 15, 2006Washington UniversityMethods, systems, and devices using reprogrammable hardware for high-speed processing of streaming data to find a redefinable pattern and respond theretoUS7127510Jan 26, 2001Oct 24, 2006International Business Machines CorporationAccess chain tracing system, network system, and storage mediumUS7139743May 21, 2002Nov 21, 2006Washington UniversityAssociative database scanning and information retrieval using FPGA devicesUS7167980May 30, 2002Jan 23, 2007Intel CorporationData comparison processUS7181437Nov 24, 2003Feb 20, 2007Washington UniversityAssociative database scanning and information retrievalUSRE36946Dec 5, 1996Nov 7, 2000Sun Microsystems, Inc.Method and apparatus for privacy and authentication in wireless networksNon-Patent CitationsReference1"Lucent Technologies Delivers "PayloadPlus" Network Processors for Programmable, MultiProtocol, OC-48c Processing", Lucent Technologies Press Release, downloaded from http://www.lucent.com/press/1000/0010320.meb.html on Mar. 21, 2002.2"Overview, Field Programmable Port Extender", Jan. 2002 Gigabit Workshop Tutorial, Washington University, St. Louis, MO, Jan. 3-4, 2002, pp. 1-4.3"Payload PlusO Agere System Interface", Agere Systems Product Brief, Jun. 2001, downloaded from Internet, Jan. 2002, pp. 1-6.4"RFC793: Transmission Control Protocol, Darpa Internet Program, Protocol Specification", Sep. 1981.5"The Field-Programmable Port Extender (FPX)", downloaded from http://www.arl.wustl.edu/arl/ in Mar. 2002.6"A Reconfigurable Computing Model for Biological Research Application of Smith-Waterman Analysis to Bacterial Genomes", A White Paper Prepared by Star Bridge Systems, Inc. [retrieved Dec. 12, 2006]. Retrieved from the Internet: <URL: http://www.starbridgesystems.com/resources/whitepapers/Smith%20 Waterman%20Whitepaper.pdf.7"Technology Overview", Data Search Systems Incorporated, downloaded from the http://www.datasearchsystems.com/tech.htm on Apr. 19, 2004.8Aldwairi et al., "Configurable String Matching Hardware for Speeding up Intrusion Detection", SIRARCH Comput. Archit. News, vol. 33, No. 1, pp. 99-107, Mar. 2005.9Altschul et al., "Basic Local Alignment Search Tool", J. Mol. Biol., Oct. 5, 1990, 215, pp. 403-410.10Amanuma et al., "A FPGA Architectures For High Speed Computation", Proceedings of 60th Convention Architecture, Software Science, Engineering, Mar. 14, 2000, pp. 1-163-1-164, Information Processing Society, Japan.11Amer-Yahia et al., "XQuery 1.0 and XPath 2.0 Full-Text 1.0", W3C Working Draft, http://www.w3.org/TR/query-full-text/, May 18, 2007-part 1.12Amer-Yahia et al., "XQuery 1.0 and XPath 2.0 Full-Text 1.0", W3C Working Draft, http://www.w3.org/TR/query-full-text/, May 18, 2007-part 2.13Amer-Yahia et al., "XQuery 1.0 and XPath 2.0 Full-Text 1.0", W3C Working Draft, http://www.w3.org/TR/query-full-text/, May 18, 2007-part 3.14Amer-Yahia et al., "XQuery 1.0 and XPath 2.0 Full-Text 1.0", W3C Working Draft, http://www.w3.org/TR/query-full-text/, May 18, 2007-part 4.15Amer-Yahia et al., "XQuery 1.0 and XPath 2.0 Full-Text 1.0", W3C Working Draft, http://www.w3.org/TR/query-full-text/, May 18, 2007—part 1.16Amer-Yahia et al., "XQuery 1.0 and XPath 2.0 Full-Text 1.0", W3C Working Draft, http://www.w3.org/TR/query-full-text/, May 18, 2007—part 2.17Amer-Yahia et al., "XQuery 1.0 and XPath 2.0 Full-Text 1.0", W3C Working Draft, http://www.w3.org/TR/query-full-text/, May 18, 2007—part 3.18Amer-Yahia et al., "XQuery 1.0 and XPath 2.0 Full-Text 1.0", W3C Working Draft, http://www.w3.org/TR/query-full-text/, May 18, 2007—part 4.19Anerousis et al., "Using the AT&T Labs PacketScope for Internet Measurement, Design, and Performance Analysis", Network and Distributed Systems Research Laboratory, AT&T Labs-Research, Florham, Park, NJ, Oct. 1997.20Arnold et al., "The Splash 2 Processor and Applications", Proceedings 1993 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD '93), Oct. 3, 1993, pp. 482-485, IEEE Computer Society, Cambridge, MA USA.21Artan et al., "Multi-packet Signature Detection using Prefix Bloom Filters", 2005, IEEE, pp. 1811-1816.22Asami et al., "Improvement of DES Key Search on FPGA-Based Parallel Machine "RASH"", Proceedings of Information Processing Society, Aug. 15, 2000, pp. 50-57, vol. 41, No. SIG5 (HPS1), Japan.23Baer, "Computer Systems Architecture", 1980, pp. 262-265; Computer Science Press, Potomac, Maryland.24Baeza-Yates et al., "New and Faster Filters for Multiple Approximate String Matching", Random Structures and Algorithms (RSA), Jan. 2002, pp. 23-49, vol. 20, No. 1.25Baker et al., "High-throughput Linked-Pattern Matching for Intrusion Detection Systems", ANCS 2005: Proceedings of the 2005 Symposium on Architecture for Networking and Communications Systems, pp. 193-202, ACM Press, 2005.26Behrens et al., "BLASTN Redundancy Filter in Reprogrammable Hardware", Final Project Submission, Fall 2003, Department of Computer Science and Engineering, Washington University.27Berk, "JLex: A lexical analyzer generator for JavaO", downloaded from http://www.cs.princeton.edu/~appel/modern/java/Jlex/ in Jan. 2002, pp. 1-18.28Berk, "JLex: A lexical analyzer generator for JavaO", downloaded from http://www.cs.princeton.edu/˜appel/modern/java/Jlex/ in Jan. 2002, pp. 1-18.29Bloom, "Space/Time Trade-offs in Hash Coding With Allowable Errors", Communications of the ACM, Jul. 1970, pp. 422-426, vol. 13, No. 7, Computer Usage Company, Newton Upper Falls, Massachusetts, USA.30Braun et al., "Layered Protocol Wrappers for Internet Packet Processing in Reconfigurable Hardware", Proceedings of Hot Interconnects 9 (Hotl-9) Stanford, CA, Aug. 22-24, 2001, pp. 93-98.31Braun et al., "Protocol Wrappers for Layered Network Packet Processing in Reconfigurable Hardware", IEEE Micro, Jan.-Feb. 2002, pp. 66-74.32Cavnar et al., "N-Gram-Based Text Categorization", Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval, Las Vegas, pp. 161-175, 1994.33Chamberlain et al., "Achieving Real Data Throughput for an FPGA Co-Processor on Commodity Server Platforms", Proc. of 1st Workshop on Building Block Engine Architectures for Computers and Networks, Oct. 2004, Boston, MA.34Chamberlain et al., "The Mercury System: Embedding Computation Into Disk Drives", 7th High Performance Embedded Computing Workshop, Sep. 2003, Boston, MA.35Chamberlain et al., "The Mercury System: Exploiting Truly Fast Hardware for Data Search", Proc. of Workshop on Storage Network Architecture and Parallel I/Os, Sep. 2003, New Orleans, LA.36Chenna et al., "Multiple Sequence Alignment with the Clustal Series of Programs", Nucleic Acids Research, 2003, vol. 31, No. 13, pp. 3497-3500.37Cho et al., "Deep Packet Filter with Dedicated Logic and Read Only Memories", 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Apr. 2004.38Chodowiec et al., "Fast Implementations of Secret-Key Block Ciphers Using Mixed Inter- and Outer-Round Pipelining", Proceedings of International Symposium on FPGAs, pp. 94-102 (Feb. 2001).39Choi et al., "Design of a Flexible Open Platform for High Performance Active Networks", Allerton Conference, 1999, Champaign, IL.40Clark et al., "Scalable Pattern Matching for High Speed Networks", Proceedings of the 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2004; FCCM 2004, Apr. 20-23, 2004; pp. 249-257; IEEE Computer Society; Cambridge, MA USA.41Cloutier et al., "VIP: An FPGA-Based Processor for Image Processing and Neural Networks", Proceedings of Fifth International Conference on Microelectronics for Neural Networks, Feb. 12, 1996, pp. 330-336, Los Alamitos, California.42Compton et al., "Configurable Computing: A Survey of Systems and Software", Technical Report, Northwestern University, Dept. of ECE, 1999g.43Compton et al., "Reconfigurable Computing: A Survey of Systems and Software", Technical Report, Northwestern University, Dept. of ECE, 1999, presented by Yi-Gang Tai.44Cong et al., "An Optional Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs", IEEE, 1992, pp. 48-53.45Cuppu and Jacob, "Organizational Design Trade-Offs at the DRAM, Memory Bus and Memory Controller Level: Initial Results," Technical Report UMB-SCA-1999-2, Univ. of Maryland Systems & Computer Architecture Group, Nov. 1999, pp. 1-10.46Denoyer et al., "HMM-based Passage Models for Document Classification and Ranking", Proceedings of ECIR-01, 23rd European Colloquim Information Retrieval Research, Darmstatd, DE, pp. 126-135, 2001.47Dharmapurikar et al., "Deep Packet Inspection Using Parallel Bloom Filters," Symposium on High Performance Interconnects (Hotl), Stanford, California, 2003, pp. 44-51.48Dharmapurikar et al., "Longest Prefix Matching Using Bloom Filters," SIGCOMM, 2003, pp. 201-212.49Dharmapurikar et al., "Robust TCP Stream Reassembly in the Presence of Adversaries", Proc. of the 14th Conference on USENIX Security Symposium-vol. 14, 16 pages, Baltimore, MD, 2005; http://www.icir.org/vern/papers/TcpReassembly/TCPReassembly.pdf.50Dharmapurikar et al., "Deep Packet Inspection Using Parallel Bloom Filters", IEEE Micro, Jan.Feb., 2004, vol. 24, Issue: 1, pp. 52-61.51Dharmapurikar et al., "Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom Filters", Proc. of 12th Annual IEEE Symposium on Field Programmable Custom Computing Machines, 2004, pp. 1-10.52Dharmapurikar et al., "Robust TCP Stream Reassembly in the Presence of Adversaries", Proc. of the 14th Conference on USENIX Security Symposium—vol. 14, 16 pages, Baltimore, MD, 2005; http://www.icir.org/vern/papers/TcpReassembly/TCPReassembly.pdf.53Dharmapurikar, "Fast and Scalable Pattern Matching for Content Filtering", ACM, ANCS 05, 2005, pp. 183-192.54Ebeling et al., "RaPiD-Reconfigurable Pipelined Datapath", University of Washington, Dept. of Computer Science and Engineering, Sep. 23, 1996, Seattle, WA.55Ebeling et al., "RaPiD—Reconfigurable Pipelined Datapath", University of Washington, Dept. of Computer Science and Engineering, Sep. 23, 1996, Seattle, WA.56Edgar, "MUSCLE: Multiple Sequence Alignment with High Accuracy and High Throughput", Nucleic Acids Research, 2004, vol. 32, No. 5, pp. 1792-1797.57Fernandez, "Template Matching of Binary Targets in Grey-Scale Images: A Nonparametric Approach", Pattern Recognition, 1997, pp. 1175-1182, vol. 30, No. 7.58Forgy, "Rete: A fast algorithm for the many pattern/many object pattern matching problem", Artificial Intelligence, 19, pp. 17-37, 1982.59Franklin et al., "Assisting Network Intrusion Detection with Reconfigurable Hardware", Symposium on Field-Programmable Custom Computing Machines (FCCM 2002), Apr. 2002, Napa, California.60Franklin et al., "An Architecture for Fast Processing of Large Unstructured Data Sets", Proc. of 22nd Int'l Conf. on Computer Design, Oct. 2004, pp. 280-287.61Fu et al., "The FPX KCPSM Module: An Embedded, Reconfigurable Active Processing Module for the Field Programmable Port Extender (FPX)", Washington University, Department of Computer Science, Technical Report WUCS-01-14, Jul. 2001.62Gavrila et al., "Multi-feature Hierarchical Template Matching Using Distance Transforms", IEEE, Aug. 16-20, 1998, vol. 1, pp. 439-444.63Guerdoux-Jamet et al., Systolic Filter for Fast DNA Similarity Search, IEEE, 1995, pp. 145-156.64Gunther et al., "Assessing Document Relevance with Run-Time Reconfigurable Machines", FPGAs for Custom Computing Machines, 1996, Proceedings, IEEE Symposium on, pp. 10-17, Napa Valley, CA, Apr. 17, 1996.65Gyang, "NCBI BLASTN Stage 1 in Reconfigurable Hardware", Technical Report WUCSE-2005-30, Aug. 2004, Department of Computer Science and Engineering, Washington University, St. Louis, MO.66Halaas et al., "A Recursive MISD Architecture for Pattern Matching", IEEE Transactions on Very Large Scale Integration, vol. 12, No. 7, pp. 727-734, Jul. 2004.67Hauck et al., "Software Technologies for Reconfigurable Systems", Northwestern University, Dept. of ECE, Technical Report, 1996.68Hayes, "Computer Architecture and Organization", Second Edition, 1988, pp. 448-459, McGraw-Hill, Inc.69Hezel et al., "FPGA-Based Template Matching Using Distance Transforms", Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, Apr. 22, 2002, pp. 89-97, IEEE Computer Society, USA.70Hollaar, "Hardware Systems for Text Information Retrieval", Proceedings of the Sixth Annual International ACM Sigir Conference on Research and Development in Information Retrieval, Jun. 6-8, 1983, pp. 3-9, Baltimore, Maryland, USA.71Hutchings et al., "Assisting Network Intrusion Detection with Reconfigurable Hardware", FCCM 2002: 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, 2002.72International Search Report for PCT/US2001/011255 dated Jul. 10, 2003.73International Search Report for PCT/US2002/033286; Jan. 22, 2003.74International Search Report for PCT/US2003/015638 dated May 6, 2004.75International Search Report for PCT/US2004/016021 dated Aug. 18, 2005.76International Search Report for PCT/US2004/016398 dated Apr. 12, 2005.77International Search Report for PCT/US2005/030046; Sep. 25, 2006.78International Search Report for PCT/US2007/060835 dated Jul. 9, 2007.79International Search Report for PCT/US2007/067319 dated Jan. 11, 2008.80International Search Report for PCT/US2007/075723 dated Jul. 25, 2008.81International Search Report from corresponding International Application No. PCT/US2006/006105.82Jeanmougin et al., "Multiple Sequence Alignment with Clustal X", TIBS, 1998, vol. 23, pp. 403-405.83Jones et al., "A Probabilistic Model of Information Retrieval: Development and Status", Information Processing and Management, Aug. 1998, 76 pages.84Jung et al., "Efficient VLSI for Lempel-Ziv Compression in Wireless Data Communication Networks", IEEE Transactions on VLSI Systems, Sep. 1998, pp. 475-483, vol. 6, No. 3, Institute of Electrical and Electronics Engineers, Washington, DC, USA.85Keutzer et al., "A Survey of Programmable Platforms—Network Proc", University of California-Berkeley, pp. 1-29.86Koloniari et al., "Content-Based Routing of Path Queries in Peer-to-Peer Systems", pp. 1-19, E. Bertino et al. (Eds.): EDBT 2004, LNCS 2992, pp. 29-47, 2004, copyright by Springer-Verlag, Germany.87Krishnamurthy et al., "Biosequence Similarity Search On The Mercury System", Proceedings of the 15th IEEE International Conference on Application-Specific Systems, Architectures, and Processors(ASAP04), Sep. 2004, pp. 365-375 (2004).88Lancaster et al., "Acceleration of Ungapped Extension in Mercury BLAST", Seventh (7th) Workshop on Media and Streaming Processors, Nov. 12, 2005, Thirty-Eighth (38th) International Symposium on Microarchitecture (MICRO-38), Barcelona, Spain.89Li et al., "Large-Scale IP Traceback in High-Speed Internet: Practical Techniques and Theoretical Foundation", Proceedings of the 2004 IEEE Symposium on Security and Privacy, 2004, pp. 1-15.90Lin et al., "Real-Time Image Template Matching Based on Systolic Array Processor", International Journal of Electronics; Dec. 1, 1992; pp. 1165-1176; vol. 73, No. 6; London, Great Britain.91Lockwood et al., "Field Programmable Port Extender (FPX) for Distributed Routing and Queuing", ACM International Symposium on Field Programmable Gate Arrays (FPGA 2000), Monterey, CA, Feb. 2000, pp. 137-144.92Lockwood et al., "Hello, World: A Simple Application for the Field Programmable Port Extender (FPX)", Washington University, Department of Computer Science, Technical Report WUCS-00-12, Jul. 11, 2000.93Lockwood et al., "Parallel FPGA Programming over Backplane Chassis", Washington University, Department of Computer Science, Technical Report WUCS-00-11, Jun. 12, 2000.94Lockwood et al., "Reprogrammable Network Packet Processing on the Field Programmable Port Extender (FPX)", ACM International Symposium on Field Programmable Gate Arrays (FPGA 2001), Monterey, CA, Feb. 2001, pp. 87-93.95Lockwood, "An Open Platform for Development of Network Processing Modules in Reprogrammable Hardware", IEC DesignCon 2001, Santa Clara, CA, Jan. 2001, Paper WB-19.96Lockwood, "Building Networks with Reprogrammable Hardware", Field Programmable Port Extender: Jan. 2002 Gigabit Workshop Tutorial, Washington University, St. Louis, MO, Jan. 3-4, 2002.97Lockwood, "Evolvable Internet Hardware Platforms", NASA/DoD Workshop on Evolvable Hardware (EHW'01), Long Beach, CA, Jul. 12-14, 2001, pp. 271-279.98Lockwood, "Hardware Laboratory Configuration", Field Programmable Port Extender: Jan. 2002 Gigabit Workshop Tutorial, Washington University, St. Louis, MO, Jan. 3-4, 2002.99Lockwood, "Introduction", Field Programmable Port Extender: Jan. 2002 Gigabit Workshop Tutorial, Washington University, St. Louis, MO, Jan. 3-4, 2002.100Lockwood, "Platform and Methodology for Teaching Design of Hardware Modules in Internet Routers and Firewalls", IEEE Computer Society International Conference on Microelectronic Systems Education (MSE'2001), Las Vegas, NV, Jun. 17-18, 2001, pp. 56-57.101Lockwood, "Protocol Processing on the FPX", Field Programmable Port Extender: Jan. 2002 Gigabit Workshop Tutorial, Washington University, St. Louis, MO, Jan. 3-4, 2002.102Lockwood, "Simulation and Synthesis", Field Programmable Port Extender: Jan. 2002 Gigabit Workshop Tutorial, Washington University, St. Louis, MO, Jan. 3-4, 2002.103Lockwood, "Simulation of the Hello World Application for the Field-Programmable Port Extender (FPX)", Washington University, Applied Research Lab, Spring 2001 Gigabits Kits Workshop.104Madhusudan, "Design of a System for Real-Time Worm Detection", Hot Interconnects, pp. 77-83, Stanford, CA, Aug. 2004, found at http://www.hoti.org/hoti12/program/papers/2004/paper4.2.pdf.105Madhusudan, "Design of a System for Real-Time Worm Detection", Master's Thesis, Washington Univ., Dept. of Computer Science and Engineering, St. Louis, MO, Aug. 2004.106Madhusudan, "Design of a System for Real-Time Worm Detection", Power Point Presentation in Support of Master's Thesis, Washington Univ., Dept. of Computer Science and Engineering, St. Louis, MO, Aug. 2004.107Mitzenmacher, "Compressed Bloom Filters", IEEE/ACM Transactions on Networking, Oct. 2002 (manuscript received Aug. 1, 2001 and revised Dec. 5, 2001), pp. 604-612, vol. 10, No. 5, U.S.A.108Mosanya et al., "A FPGA-Based Hardware Implementation of Generalized Profile Search Using Online Arithmetic", ACM/Sigda International Symposium on Field Programmable Gate Arrays (FPGA '99), Feb. 21-23, 1999, pp. 101-111, Monterey, CA, USA.109Moscola et al., "FPGrep and FPSed: Regular Expression Search and Substitution for Packet Streaming in Field Programmable Hardware", Dept. of Computer Science, Applied Research Lab, Washington University, Jan. 8, 2002, unpublished, pp. 1-19, St. Louis, MO.110Moscola et al., "FPSed: A Streaming Content Search-And-Replace Module for an Internet Firewall", Proc. of Hot Interconnects, 11th Symposium on High Performance Interconnects, pp. 122-129, Aug. 20, 2003.111Moscola, "FPGrep and FPSed: Packet Payload Processors for Managing the Flow of Digital Content on Local Area Networks and the Internet", Master's Thesis, Sever Institute of Technology, Washington University, St. Louis, MO, Aug. 2003.112Navarro, "A Guided Tour to Approximate String Matching", ACM Computing Surveys, vol. 33, No. 1, Mar. 2001, pp. 31-88.113Niewczas et al., "A Pattern Matching Algorithm for Verification and Analysis of Very Large IC Layouts", ACM, Apr. 1998, pp. 129-134.114Nunez et al., "The X-MatchLITE FPGA-Based Data Compressor", Euromicro Conference 1999, Proceedings, Italy, Sep. 8-10, 1999, pp. 126-132, Los Alamitos, CA.115Nwodoh et al., "A Processing System for Real-Time Holographic Video Computation", Reconfigurable Technology: FPGAs for Computing and Application, Proceedings for the SPIE, Sep. 1999, Boston, pp. 129-140, vol. 3844.116Office Action for U.S. Appl. No. 11/836,947, dated Oct. 19, 2009.117Pirsch et al., "VLSI Architectures for Video Compression-A Survey", Proceedings of the IEEE, Feb. 1995, pp. 220-243, vol. 83, No. 2, Institute of Electrical and Electronics Engineers, Washington, DC, USA.118Pramanik et al., "A Hardware Pattern Matching Algorithm on a Dataflow"; Computer Journal; Jul. 1, 1985; pp. 264-269; vol. 28, No. 3; Oxford University Press, Surrey, Great Britain.119Ramakrishna et al., "A Performance Study of Hashing Functions for Hardware Applications", Int. Conf. on Computing and Information, May 1994, pp. 1621-1636, vol. 1, No. 1.120Ramakrishna, M.V. et al., "Efficient Hardware Hashing Functions for High Performance Computers", IEEE Transactions on Computers, vol. 46, No. 12, Dec. 1997.121Ramesh et al., "Automatic Selection of Tuning Parameters for Feature Extraction Sequences", IEEE, Jun. 21-23, 1994, pp. 672-677.122Ranganathan et al., "High-Speed VLSI Designs for Lempe-Ziv Based Data Compression", IEEE Transactions on Circuits and Systems-II: Analog and Digital Signal Processing, Feb. 1993, pp. 96-106, vol. 40, No. 2, Institute of Electrical and Electronics Engineers, Washington, DC, USA.123Ratha et al., "Convolution on Splash 2", Proceedings of IEEE Symposium on FPGAS for Custom Computing Machines, Apr. 19, 1995, pp. 204-213, Los Alamitos, California.124Ratha et al., "FPGA-based coprocessor for text string extraction", IEEE, Sep. 11-13, 2000, pp. 217-221.125Roesch, "Snort-Lightweight Intrusion Detection for Networks", Proceedings of LISA '99: 13th Systems Administration Conference; Nov. 7-12, 1999; pp. 229-238; USENIX Association, Seattle, WA USA.126Roesch, "Snort—Lightweight Intrusion Detection for Networks", Proceedings of LISA '99: 13th Systems Administration Conference; Nov. 7-12, 1999; pp. 229-238; USENIX Association, Seattle, WA USA.127Roy, "A bounded search algorithm for segmented channel routing for FPGA's and associated channel architecture issues", IEEE, Nov. 11, 1993, pp. 1695-1705, vol. 12.128Schmit, "Incremental Reconfiguration for Pipelined Applications", FPGAs for Custom Computing Machines, Proceedings, The 5th Annual IEEE Symposium, Dept. of ECE, Carnegie Mellon University, Apr. 16-18, 1997, pp. 47-55, Pittsburgh, PA.129Schuehler et al., "Architecture for a Hardware Based, TCP/IP Content Scanning System", IEEE Micro, 24(1):62-69, Jan.-Feb. 2004, USA.130Schuehler et al., "TCP-Splitter: A TCP/IP Flow Monitor in Reconfigurable Hardware", Hot Interconnects 10 (Hotl-10), Stanford, CA, Aug. 21-23, 2002, pp. 127-131.131Seki et al., "High Speed Computation of Shogi With FPGA", Proceedings of 58th Convention Architecture, Software Science, Engineering, Mar. 9, 1999, pp. 1-133-1-134.132Shah, "Understanding Network Processors", Version 1.0, University of California-Berkeley, Sep. 4, 2001.133Shirazi et al., "Quantitative Analysis of FPGA-based Database Searching", Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, May 2001, pp. 85-96, vol. 28, No. 1/2, Kluwer Academic Publishers, Dordrecht, NL.134Sidhu et al., "Fast Regular Expression Matching Using FPGAs", IEEE Symposium on Field Programmable Custom Computing Machines (FCCM 2001), Apr. 2001.135Sidhu et al., "String Matching on Multicontext FPGAs Using Self-Reconfiguration", FPGA '99: Proceedings of the 1999 ACM/SIGDA 7th International Symposium on Field Programmable Gate Arrays, Feb. 1999, pp. 217-226.136Singh et al., "The EarlyBird System for Real-Time Detection on Unknown Worms", Technical report CS2003-0761, Aug. 2003.137Sourdis and Pnevmatikatos, "Fast, Large-Scale String Match for a 10Gbps FPGA-based Network Intrusion Detection System", 13th International Conference on Field Programmable Logic and Applications, 2003.138Steinbach et al., "A Comparison of Document Clustering Techniques", KDD Workshop on Text Mining, 2000.139Tan et al., "A High Throughput String Matching Architecture for Intrusion Detection and Prevention", ISCA 2005: 32nd Annual International Symposium on Computer Architecture, pp. 112-122, 2005.140Taylor et al., "Dynamic Hardware Plugins (DHP): Exploiting Reconfigurable Hardware for High-Performance Programmable Routers", Computer Networks, 38(3): 295-310 (16), Feb. 21, 2002, and online at http://www.cc.gatech.edu/classes/AY2007/cs8803hpc-fall/papers/phplugins.pdf.141Taylor et al., "Generalized RAD Module Interface Specification of the Field Programmable Port Extender (FPX) Version 2", Washington University, Department of Computer Science, Technical Report, Jul. 5, 2001, pp. 1-10.142Taylor et al., "Modular Design Techniques for the FPX", Field Programmable Port Extender: Jan. 2002 Gigabit Workshop Tutorial, Washington University, St. Louis, MO, Jan. 3-4, 2002.143Taylor et al., "Scalable Packet Classification using Distributed Crossproducting of Field Labels", Proceedings of IEEE Infocom, Mar. 2005, pp. 1-12, vol. 20, No. 1.144Taylor et al., "Dynamic Hardware Plugins (DHP): Exploiting Reconfigurable Hardware for High-Performance Programmable Routers", Computer Networks, 38(3): 295-310 (16), Feb. 21, 2002, and online at http://www.cc.gatech.edu/classes/AY2007/cs8803hpc—fall/papers/phplugins.pdf.145Taylor, "Models, Algorithms, and Architectures for Scalable Packet Classification", doctoral thesis, Department of Computer Science and Engineering, Washington University, St. Louis, MO, Aug. 2004, pp. 1-201.146Thompson et al., "The Clustal-X Windows Interface: Flexible Strategies for Multiple Sequence Alignment Aided by Quality Analysis Tools", Nucleic Acids Research, 1997, vol. 25, No. 24, pp. 4876-4882.147Thompson et al., "The Clustal—X Windows Interface: Flexible Strategies for Multiple Sequence Alignment Aided by Quality Analysis Tools", Nucleic Acids Research, 1997, vol. 25, No. 24, pp. 4876-4882.148Uluski et al., "Characterizing Antivirus Workload Execution", SIGARCH Comput. Archit. News, vol. 33, No. 1, pp. 90-98, Mar. 2005.149Villasenor et al., "Configurable Computing Solutions For Automatic Target Recognition", FPGAS for Custom Computing Machines, 1996, Proceedings, IEEE Symposium on Napa Valley, CA, Apr. 17-19, 1996, pp. 70-79, 1996 IEEE, Napa Valley, CA, Los Alamitos, CA, USA.150Ward and Snavely, "Dynamically Reconfigurable Computing: Novel Computation Technology with Potential to Improve National Security Capabilities", May 15, 2003, A White Paper Prepared by Star Bridge Systems, Inc. [retrieved Dec. 12, 2006]. Retrieved from the Internet: <URL: http://www.starbridgesystems.com/resources/whitepapers/Dynamically%20Reconfigurable%20Computing.pdf.151Weaver et al., "Very Fast Containment of Scanning Worms", Proc. USENIX Security Symposium 2004, San Diego, CA, Aug. 2004, located at http://www.icsi.berkely.edu/~nweaver/containment/containment.pdf.152Weaver et al., "Very Fast Containment of Scanning Worms", Proc. USENIX Security Symposium 2004, San Diego, CA, Aug. 2004, located at http://www.icsi.berkely.edu/˜nweaver/containment/containment.pdf.153West et al., "An FPGA-Based Search Engine for Unstructured Database", Proc. of 2nd Workshop on Application Specific Processors, Dec. 2003, San Diego, CA.154Yamaguchi et al., "High Speed Homology Search with FPGAs", Proceedings Pacific Symposium on Biocomputing, Jan. 3-7, 2002, pp. 271-282, vol. 7, Online, Lihue, Hawaii, USA.155Yan et al., "Enhancing Collaborative Spam Detection with Bloom Filters", 2006, IEEE, pp. 414-425.156Yoshitani et al., "Performance Evaluation of Parallel Volume Rendering Machine Re Volver/C40", Study Report of Information Processing Society, Mar. 5, 1999, pp. 79-84, vol. 99, No. 21.157Ziv et al., "A Universal Algorithm for Sequential Data Compression", IEEE Trans. Inform. Theory, IT-23(3): 337-343 (1997).158Ziv et al., "Compression of Individual Sequence via Variable-Rate Coding", IEEE Transactions on Information Theory, Sep. 1978, pp. 530-536, vol. IT-24, No. 5, Institute of Electrical and Electronics Engineers, Washington, DC, USA.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8145859Mar 2, 2009Mar 27, 2012Oracle International CorporationMethod and system for spilling from a queue to a persistent storeUS8321450Jul 21, 2009Nov 27, 2012Oracle International CorporationStandardized database connectivity support for an event processing server in an embedded contextUS8386466Aug 3, 2009Feb 26, 2013Oracle International CorporationLog visualization tool for a data stream processing serverUS8387076Jul 21, 2009Feb 26, 2013Oracle International CorporationStandardized database connectivity support for an event processing serverUS8447744Nov 30, 2010May 21, 2013Oracle International CorporationExtensibility platform using data cartridgesUS8498956Aug 26, 2009Jul 30, 2013Oracle International CorporationTechniques for matching a certain class of regular expression-based patterns in data streamsUS8527458Aug 3, 2009Sep 3, 2013Oracle International CorporationLogging framework for a data stream processing serverUS8527531 *Nov 25, 2009Sep 3, 2013Hitachi, Ltd.Stream data generating method, stream data generating device and a recording medium storing stream data generating programUS8589436 *Aug 26, 2009Nov 19, 2013Oracle International CorporationTechniques for performing regular expression-based pattern matching in data streamsUS8620881Jun 21, 2011Dec 31, 2013Ip Reservoir, LlcIntelligent data storage and processing using FPGA devicesUS8655648 *Sep 1, 2010Feb 18, 2014Microsoft CorporationIdentifying topically-related phrases in a browsing sequenceUS8676841Aug 26, 2009Mar 18, 2014Oracle International CorporationDetection of recurring non-occurrences of events using pattern matchingUS8713049Jul 28, 2011Apr 29, 2014Oracle International CorporationSupport for a parameterized query/view in complex event processingUS8751452Jan 6, 2012Jun 10, 2014Ip Reservoir, LlcIntelligent data storage and processing using FPGA devicesUS8768888Jan 6, 2012Jul 1, 2014Ip Reservoir, LlcIntelligent data storage and processing using FPGA devicesUS9047243Apr 5, 2012Jun 2, 2015Ip Reservoir, LlcMethod and apparatus for low latency data distributionUS9047249Feb 19, 2013Jun 2, 2015Oracle International CorporationHandling faults in a continuous event processing (CEP) systemUS9058360Nov 30, 2010Jun 16, 2015Oracle International CorporationExtensible language framework using data cartridgesUS20110060890 *Mar 10, 2011Hitachi, LtdStream data generating method, stream data generating device and a recording medium storing stream data generating programUS20110219016 *Sep 8, 2011Src, Inc.Stream Mining via State Machine and High Dimensionality DatabaseUS20120053927 *Sep 1, 2010Mar 1, 2012Microsoft CorporationIdentifying topically-related phrases in a browsing sequenceUS20130086096 *Apr 4, 2013Exegy IncorporatedMethod and System for High Performance Pattern Indexing* Cited by examinerClassifications U.S. Classification702/19, 702/20, 707/700, 703/11International ClassificationG06F7/00, G06F19/28, G06F19/22Cooperative ClassificationG06F19/22, G06F17/3033, G06F19/28European ClassificationG06F19/22, G06F19/28Legal EventsDateCodeEventDescriptionMar 9, 2006ASAssignmentOwner name: WASHINGTON UNIVERSITY, MISSOURIFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BHLER, JEREMY DANIEL;CHAMBERLIAN, ROGER DEAN;FRANKLIN, MARK ALLEN;AND OTHERS;SIGNING DATES FROM 20060221 TO 20060222;REEL/FRAME:017666/0542Jan 10, 2007ASAssignmentOwner name: WASHINGTON UNIVERSITY, MISSOURIFree format text: CORRECTIVE ASSIGNMENT TO CORRECT THE TO RE-RECORD ASSIGNMENT TO MAKE THE FOLLOWING CORRECTIONS: PREVIOUSLY RECORDED ON REEL 017666 FRAME 0542. ASSIGNOR(S) HEREBY CONFIRMS THE ASSIGNOR FROM JEREMY DANIEL BHLER TO JEREMY DANIEL BUHLER AND ASSIGNOR FROM ROGER DEAN CHAMBERLIAN TO ROGER DEAN CHAMBERLAIN;ASSIGNORS:BUHLER, JEREMY DANIEL;CHAMBERLAIN, ROGER DEAN;FRANKLIN, MARK ALLEN;AND OTHERS;SIGNING DATES FROM 20060221 TO 20060222;REEL/FRAME:018738/0454Aug 29, 2008ASAssignmentOwner name: NATIONAL INSTITUTES OF HEALTH (NIH), U.S. DEPT. OFFree format text: CONFIRMATORY LICENSE;ASSIGNOR:WASHINGTON UNIVERSITY;REEL/FRAME:021465/0400Effective date: 20070619Jun 28, 2011CCCertificate of correctionSep 3, 2014FPAYFee paymentYear of fee payment: 4RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services