Patent ID: 8086609

Claim:
In a services processor, a computer implemented method for caching a deterministic finite automata-based graph, the method comprising: analyzing nodes in the graph to search for cacheable portions of the graph by: i) determining an accessibility ranking for each node, the accessibility ranking characterizing the likelihood each node will be accessed during a search for a pattern described by a regular expression in an input string, and ii) optimizing a node structure of each node to be cached, and iii) selecting the cacheable portions of the graph based on the accessibility rankings of the nodes during a graph compilation stage; and caching the cacheable portions of the graph during a loading stage of the graph; traversing the cacheable portions of the graph in a cache with a walker process; and further traversing non-cacheable portions of the graph with the walker process in a main memory; wherein each node comprises at least one arc pointing to the node, the method further comprising: reading a location indicator associated with each arc to determine if a next node is in the cache.