Graph caching
First Claim
1. A computer implemented method for caching a deterministic finite automata-based (DFA-based) graph, the method comprising:
- analyzing nodes in the DFA-based graph to search for cacheable portions of the DFA-based graph by utilizing an accessibility ranking associated with each node in the DFA-based graph, the accessibility ranking for each node in the DFA-based graph determined by a compiler generating the DFA-based graph and characterizing the likelihood each node will be accessed during a search of the DFA-based graph for a pattern described by a regular expression in an input string, the compiler determining the accessibility ranking for each node during a graph compilation stage;
selecting the cacheable portions of the DFA-based graph based on the accessibility rankings of the nodes; and
caching, during a loading stage of the DFA-based graph, the cacheable portions of the DFA-based graph selected based on the accessibility rankings determined during the graph compilation stage and storing non-cacheable portions of the DFA-based graph in a main memory, wherein a walker process is configured to search for the pattern by traversing the cacheable portions of the DFA-based graph in cache and traversing the non-cacheable portions of the DFA-based graph in the main memory.
7 Assignments
0 Petitions
Accused Products
Abstract
In a method and apparatus for analyzing nodes of a Deterministic Finite Automata (DFA), an accessibility ranking, based on a DFA graph geometrical configuration, may be determined in order to determine cacheable portions of the DFA graph in order to reduce the number of external memory accesses. A walker process may be configured to walk the graph in a graph cache as well as main memory. The graph may be generated in a manner allowing each arc to include information if the node it is pointing to is stored in the graph cache or in main memory. The walker may use this information to determine whether or not to access the next arc in the graph cache or in main memory.
-
Citations
20 Claims
-
1. A computer implemented method for caching a deterministic finite automata-based (DFA-based) graph, the method comprising:
-
analyzing nodes in the DFA-based graph to search for cacheable portions of the DFA-based graph by utilizing an accessibility ranking associated with each node in the DFA-based graph, the accessibility ranking for each node in the DFA-based graph determined by a compiler generating the DFA-based graph and characterizing the likelihood each node will be accessed during a search of the DFA-based graph for a pattern described by a regular expression in an input string, the compiler determining the accessibility ranking for each node during a graph compilation stage; selecting the cacheable portions of the DFA-based graph based on the accessibility rankings of the nodes; and caching, during a loading stage of the DFA-based graph, the cacheable portions of the DFA-based graph selected based on the accessibility rankings determined during the graph compilation stage and storing non-cacheable portions of the DFA-based graph in a main memory, wherein a walker process is configured to search for the pattern by traversing the cacheable portions of the DFA-based graph in cache and traversing the non-cacheable portions of the DFA-based graph in the main memory. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A system comprising a hardware processor, the hardware processor configured to:
-
analyze a searchable graph including a plurality of interconnected nodes to determine cacheable portions of the searchable graph by utilizing an accessibility ranking associated with each node in the searchable graph; determine the accessibility ranking of each node in the searchable graph during generation of the searchable graph, the accessibility ranking for each node characterizing the likelihood each node will be accessed during a search of the searchable graph for a pattern described by a regular expression in an input string; determine the accessibility ranking during a graph compilation stage; select the cacheable portions of the searchable graph based on the accessibility ranking of the nodes; and cache, during a loading stage of the searchable graph, the cacheable portions of the searchable graph selected based on the accessibility rankings determined during the graph compilation stage and store non-cacheable portions of the searchable graph in a main memory, wherein a walker process is configured to search for the pattern by traversing the cacheable portions of the searchable graph in cache and traversing the non-cacheable portions of the searchable graph in the main memory. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
19. A computer implemented method for caching a deterministic finite automata-based (DFA-based) graph, the method comprising:
-
analyzing nodes in the DFA-based graph to search for cacheable portions of the DFA-based graph by utilizing an accessibility ranking associated with each node in the DFA-based graph, the accessibility ranking for each node in the DFA-based graph determined by a compiler generating the DFA-based graph and characterizing the likelihood each node will be accessed during a search of the DFA-based graph for a pattern described by a regular expression in an input string, the compiler determining the accessibility ranking for each node during a graph compilation stage, wherein determining the accessibility ranking for each node during the graph compilation stage includes evaluating an in-degree and an out-degree of the node and a greater in-degree or out-degree of the node results in a higher accessibility ranking; selecting the cacheable portions of the DFA-based graph based on the accessibility rankings of the nodes; and caching the selected cacheable portions of the DFA-based graph and storing non-cacheable portions of the DFA-based graph in a main memory, wherein a walker process is configured to search for the pattern by traversing the cacheable portions of the DFA-based graph in cache and traversing the non-cacheable portions of the DFA-based graph in the main memory.
-
-
20. A computer implemented method for caching a deterministic finite automata-based (DFA-based) graph, the method comprising:
-
analyzing nodes in the DFA-based graph to search for cacheable portions of the DFA-based graph by utilizing an accessibility ranking associated with each node in the DFA-based graph, the accessibility ranking for each node in the DFA-based graph determined by a compiler generating the DFA-based graph and characterizing the likelihood each node will be accessed during a search of the DFA-based graph for a pattern described by a regular expression in an input string, the compiler determining the accessibility ranking for each node during a graph compilation stage, wherein determining the accessibility ranking for each node during the graph compilation stage includes evaluating a heaviness of the node and a heavier node comprises a higher accessibility ranking; selecting the cacheable portions of the DFA-based graph based on the accessibility rankings of the nodes; and caching the selected cacheable portions of the DFA-based graph and storing non-cacheable portions of the DFA-based graph in a main memory, wherein a walker process is configured to search for the pattern by traversing the cacheable portions of the DFA-based graph in cache and traversing the non-cacheable portions of the DFA-based graph in the main memory.
-
Specification