Graph-Based Data Search
AssigneeThe Boeing Company
InventorsBrian D. Hanner, Jason Amanatullah, Timothy Chung-Ming Wu
Life of this patent
Estimating the term…
Abstract
Computer based systems and methods for searching data transiting a network using a graph-based search model. A set of rules that describe strings or patterns of data to be identified in the data set, is expressed as a graph. As blocks of the data set are obtained for processing, the state of the graph is updated based upon the value of the received data block. The transition to the next state depends upon both the current state and the received data block. As blocks of data are received and processed, the graph is traversed until one of the rules is identified.
Claims24
A method for searching a data set for one or more data values;
- comprising:
- obtaining a data block of the data set;
- traversing a graph rule set based at least in part upon a current state of said graph rule set and said data block, wherein said graph rule set is a graph representation of a set of rules;
- and
- identifying a rule of said set of rules as a function of traversal of said graph rule set for the data set, wherein said set of rules describes the one or more data values.
A computer-based method for generation of a graph representation of a rule set, comprising:
- selecting a rule from the rule set;
- determining at least one verification set for the selected rule, wherein said at least one verification set encompasses all valid values;
- processing each of the at least one verification sets, comprising:
- creating a subgraph for each of said verification sets;
- and
- recursively processing said subgraph;
- and
- linking said subgraph to the graph representation.
A system that searches a data set for one or more data patterns, comprising:
- a receiver component that obtains at least one data block of the data set;
- a graph rule set that represents a set of rules as a graph, wherein said set of rules describes the one or more data patterns;
- and
- a search component that traverses said graph rule set as a function of a current state of said graph rule set and said at least one data block, and identifies a rule of said set of rules based upon traversal of said graph rule set.
A system for filtering a data set for one or more data patterns;
- comprising:
- means for obtaining a data block of the data set;
- means for searching the data set using a graph rule set and based at least in part upon a current state of said graph rule set and said data block wherein said graph rule set is a graph representation of a set of rules that describe the one or more data patterns;
- and
- means for filtering the data set to generate a filtered data set based at least in part upon searching the data set.
Dependencies are inferred from the claim text.