The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
May. 24, 2011
Filed:
Nov. 27, 2007
Rajan Goyal, San Jose, CA (US);
Rajan Goyal, San Jose, CA (US);
Cavium Networks, Inc., Mountain View, CA (US);
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.