JP2024536720A - Event processing system and method - Patents.com - Google Patents

Abstract

A system and method for processing events is disclosed: receiving event data including passive event data, active event data, or both; determining whether the received event data is available for a pattern of passive event data and active event data; translating one or more constraints between the passive event data and the active event data into one or more query terms in response to determining whether the received event data is available for a pattern of passive event data and active event data; creating at least one query using the query terms; and obtaining remaining passive event data related to some but not all of the active event data using the created at least one query.
[Selected figure] Figure 14

Description

CROSS-REFERENCE TO RELATED APPLICATIONS This application claims the benefit of U.S. Patent Application No. 17/446,924, filed September 3, 2021, the disclosure of which is incorporated herein by reference.

Embodiments of the present disclosure relate generally to event processing. More particularly, embodiments of the present disclosure relate to systems and methods for hierarchical complex event processing (H-CEP).

The security of governments, businesses, organizations, and individuals is becoming more and more important as they are increasingly threatened by many individuals and groups. It is therefore important to have security measures that can detect and prevent potential threats, as well as process information that is useful in responding to growing threats in a timely and effective manner.

The availability of large amounts of data from numerous sources, including transactional systems, social networks, web activity, and historical logs, necessitates the use of data technologies to mine and correlate useful information. Stream processing approaches and event-based systems incorporating complex event processing (CEP) have gained widespread acceptance for processing big data in many application domains. CEP refers to the detection of events with complex relationships that often include a temporal or geographical component.

Unfortunately, current CEP systems have shortcomings, such as assuming that input data comes from similar data sources and that data structures and schemas do not change frequently.

U.S. Patent Specification No. 17/446,924 U.S. Pat. No. 9,858,260

Embodiments of the present disclosure are illustrated by way of example and not by way of limitation in the accompanying drawings, in which like reference numbers refer to substantially the same elements.

FIG. 1 is a block diagram illustrating an event processing system according to one embodiment. FIG. 1 is a block diagram illustrating an event processing system according to one embodiment. 1 is a flow diagram illustrating a method for processing events according to one embodiment. 4 is a flow diagram illustrating an event processing method according to another embodiment. FIG. 2 illustrates a template representation according to one embodiment. FIG. 2 illustrates a template representation according to one embodiment. FIG. 2 illustrates a template representation according to one embodiment. FIG. 2 illustrates a template representation according to one embodiment. FIG. 2 illustrates a template representation according to one embodiment. FIG. 2 illustrates a template representation according to one embodiment. FIG. 2 illustrates a template representation according to one embodiment. FIG. 2 illustrates an example of a template according to one embodiment. FIG. 2 illustrates an example of a template according to one embodiment. FIG. 2 illustrates an example of a template according to one embodiment. FIG. 2 illustrates an example of a template according to one embodiment. FIG. 2 illustrates a representation of a template in Java Script Object Notation (JSON) according to one embodiment. FIG. 2 illustrates a representation of a template in Java Script Object Notation (JSON) according to one embodiment. 4 is a flow diagram illustrating a method for generating a solution according to one embodiment. 4 is a flow diagram illustrating a method for generating a solution according to another embodiment. 1 is a flow diagram illustrating a method for processing results or actions according to one embodiment. 4 is a flow diagram illustrating a method for publishing an event according to one embodiment. 1 is a flow diagram illustrating a method for processing constraints according to one embodiment. 11 is a flow diagram illustrating a method for processing constraints according to another embodiment. 1 is a flow diagram illustrating a method for event retention according to one embodiment. 11 is a flow diagram illustrating another method of event retention according to one embodiment. 1 is a block diagram illustrating a data processing system according to one embodiment.

Various embodiments and aspects of the present disclosure will be described with reference to the details discussed below. The accompanying drawings illustrate various embodiments. The following description and drawings are illustrative of the present disclosure and should not be construed as limiting the present disclosure. Numerous specific details are set forth to provide a thorough understanding of various embodiments of the present disclosure. However, in some cases, well-known or conventional details are not described in order to concisely describe the embodiments of the present disclosure.

When "one embodiment" or "an embodiment" is used herein, it means that a particular feature, structure, or characteristic described in connection with that embodiment may be included in at least one embodiment of the present disclosure. The appearances of the phrase "in one embodiment" in various places in this specification are not necessarily all referring to the same embodiment.

As used herein, a template kind (or template definition) refers to the specification of a set of assertions and constraints that the system is to monitor. A solution template instance (or template instance) refers to a set of events that collectively satisfy the template. This is also called a solution of the template. For example, an event may be involved in multiple solutions. Each solution satisfies all of the constraints in the template. A solution may not satisfy all of the multiple requirements, in which case no action based on that assertion is implied. An assertion refers to a part of a template definition that indicates a set of data that, if true, validates the hypothesis expressed by the template definition. Most commonly, this refers to an event kind, indicating that an event of that kind can satisfy the assertion if all of the constraints are satisfied. A consequence (or action) refers to an action that the system will initiate if all of the assertions that the action depends on are true. This could be an action to publish an event. A group refers to a set of assertions that are satisfied in a set for that group to be satisfied. A constraint refers to a specification of restrictions on the events that are considered to satisfy the assertions to which the constraint applies. For example, the constraint that withdrawals and deposits must be to the same account is a constraint on withdrawal and deposit events/assertions. A field is a piece of data in an event that is used as input to a constraint or action. An event kind (or event definition) is a specification for generating an event from ingested data or emitted from a template. This specification includes a definition of the fields that will be included in the processed event.

According to some embodiments, input source data is received that includes event data for one or more events. One or more event definitions that match the event data are selected. For each matching event definition, the event definition is input into a template to generate a set of events. The template includes a number of assertions, with the event definition as one of the assertions, and each assertion includes a constraint. The constraints of the assertions are processed incrementally to create one or more solutions that are subsets of the set of events. For each constraint and each solution, a set of target events that are executable for that solution is identified, and a new solution is created based on the solution and the identified set of target events, thereby creating a set of new solutions.

In one embodiment, for each new solution and each outcome in the template, it is determined whether all assertions are satisfied. In response to determining that all assertions are satisfied, it is determined whether an equivalent outcome has been previously triggered. An outcome is triggered in response to determining that an equivalent outcome has not been previously triggered.

In one embodiment, in response to a determination that at least one assertion is not satisfied and an equivalent outcome has previously been triggered, the outcome is not triggered.

In one embodiment, to trigger an outcome, event data is created for the new solution and event data is published for the new solution.

In one embodiment, generate new solution base data to publish event data for the new solution. For each resulting data mapping entry, collect source event values from the source events referenced in that data mapping entry, perform calculations on the source event values to create results, and add the results to the new solution. Extract entity data from the source events. The entity data is aggregated into an entity map, which identifies each entity referenced in the source events.

In one embodiment, to process the constraints of an assertion incrementally, order the split constraints such that each split constraint is preceded by a constraint that targets the source event of the split constraint. Generate an event subset in the order of the split constraints. Process the remaining non-split constraints.

In another embodiment, to process the constraints of an assertion incrementally, non-split constraints are grouped into stages. The stages are ordered to form a hierarchical data structure. Each event is placed into one of multiple partial solutions within each assertion with the event's event definition, and the partial solutions are included in the hierarchical data structure. The partial solutions are separated based on a split key. Partial solutions with a common split key are combined to form one or more complete solutions. The combined partial solutions are processed into a result.

According to some embodiments, a system and method for processing events is provided. Receive event data including passive event data, active event data, or both. Determine whether the received event data is available for a pattern of passive event data and active event data. In response to determining that the received event data is available for a pattern of passive event data and active event data, convert one or more constraints between the passive event data and the active event data into one or more query terms. The query terms are used to construct at least one query. Remaining passive event data related to some but not all of the active event data is obtained using the constructed at least one query. Select one or more event definitions that match the event data and the remaining passive event data. For each matching event definition, input the event definition into a template to generate a set of events. The template includes a number of assertions, having the event definition as one of the assertions, each assertion including a constraint. The constraints of the assertions are processed incrementally to create one or more solutions that are subsets of the set of events. For each constraint and each solution, identify a set of target events that are executable for that solution, create a new solution based on the solution and the identified set of target events, and create a set of new solutions.

1A and 1B are block diagrams illustrating an event processing system according to one embodiment. In FIG. 1A and 1B, the event processing system 100 may be a hierarchical complex event processing (H-CEP) system. The term "hierarchy" in H-CEP refers to the ability to create events that enter from one part of the system into another part of the system, forming a conceptual hierarchy of processing. Although the term hierarchy is used, any graph of information flow can be formed. As used herein, the term "template" is used to represent a unit of detection of a set of events and the relationships between the events. The relationships between the events are expressed as "constraints," and template matching is performed using a "constraint solver" method. In some embodiments, the constraint solver filters a set of possible event matches rather than computing a "solution" to a numerical problem.

Referring to FIG. 1A, system 100 includes, but is not limited to, one or more user devices 101-102 communicatively coupled to server 150 via network 103. User devices 101-102 may be any type of device, such as a host or server, a personal computer (e.g., desktop, laptop, and tablet), a "thin" client, a personal digital assistant (PDA), a web-enabled appliance, a mobile phone (e.g., smartphone), a wearable device (e.g., smart watch), etc. Network 303 may be any type of network, whether wired or wireless, such as a local area network (LAN), a wide area network (WAN) such as the Internet, a fiber network, a storage network, or a combination thereof.

The user devices 101-102 may provide an electronic display with input/output capabilities. Alternatively, a separate electronic display and input/output device, such as a keyboard, may be used for direct electronic communication with the server 150. Any of a wide variety of electronic displays and input/output devices may be used in the system 100. In one embodiment, the user may use the user devices 101-102 to access a web page hosted on the server 150 via the network 103. The server 150 may provide a web page that the user can access using a conventional web browser or viewer, such as Safari, Internet Explorer, etc., that may be installed on the user devices 101-102. The published events 165 (described in more detail below) may be presented to the user via the web page. In another embodiment, the server 150 may provide a computer application that can be downloaded to the user devices 101-102. For example, the user may access a web page hosted by the server 150 to download the computer application. A computer application can be installed on the user device 101-102, and the user device provides the user with an interface for viewing the published events.

Continuing to refer to FIG. 1A, server 150 is communicatively coupled or connected to external systems 171 and data stores 172, which may be on substantially the same network as network 103. Server 150 may be any type of server or cluster of servers, such as web or cloud servers, application servers, back-end servers, etc., or combinations thereof. As described in more detail below, server 150 relies on one or more external sources of input events and produces one or more sets of outputs (events). In one embodiment, the set of outputs may act as inputs to server 150 itself. In some embodiments, server 150 selects events of interest, compares them to predefined templates, filters them for combinations of events that match template-specific constraints, and issues new events to potentially match the templates, which may be matched by the templates. The results may be used to detect behavioral patterns represented by the matched events, generate alerts for combinations of events of interest, and synthesize summary information from low-level data.

External system 171 may be any computer system with computational and network connectivity capabilities to interface with server 150. In one embodiment, external system 171 may include multiple computer systems. That is, external system 171 may be a cluster of machines that share computational and source data storage workloads. In one embodiment, data store 172 may be any memory storage medium, computer memory, database, or database server suitable for storing electronic data. Data store 172 may be a separate computer independent of server 150. Data store 172 may be a relational data store. In one embodiment, data store 172 may reside on external system 171 or may be configured to reside separately in one or more locations.

Referring to FIG. 1B, the server 150 includes, but is not limited to, an input data receiving module 151, an event processing module 152, a solution generating module 153, a result processing module 154, and an event publishing module 155. Some or all of the modules 151-155 may be implemented in software, hardware, or a combination thereof. For example, these modules may be installed on persistent storage 182 (e.g., hard disk, solid state drive), loaded into memory 181, and executed on one or more processors (not shown) of the server 150. It should be noted that some or all of these modules may be communicatively coupled to or integrated into some or all modules of the server 150. Some of the modules 151-155 may be integrated together as an integrated module.

In one embodiment, the input data receiving module 151 may receive source data from the external system 171 or data store 172. For example, the source data may be pushed, where data is provided directly to the server 150 when available (i.e., a direct feed). Alternatively, the source data may be pulled, where the server 150 (i.e., module 151) periodically requests the source data from the external system via a database query, such as Solr, Structured Query Language (SQL), etc. The source data may include input events and may be any form of structured and unstructured data (e.g., heterogeneous content). Any data can be used as structured data, such as Extensible Markup Language (XML), Comma-Separated Values (CSV), Java Script Notation (JSON), and Resource Description Framework (RDF) data. In one embodiment, the source data can be source data that can be mapped with a lexicon (or filtered using lexicon data) from an external source, as described in U.S. Patent No. 9,858,260, entitled "System and method for analyzing items using lexicon analysis and filtering process," the disclosure of which is incorporated herein by reference. Upon receiving the source data, module 151 may store the source data in persistent storage 182 as input source data 161.

In various embodiments, a key element in performing event processing is obtaining input events from external sources or systems. For example, obtaining the correct events in a timely manner may be essential. Thus, in one embodiment, streaming/active (or push) data sources may be combined with passive (or pull) data sources to improve the accuracy of the events obtained and the timeliness of the events obtained from passive data stores (e.g., Structured Query Language (SQL) databases, web services, etc.).

In one embodiment, a source of active data may be leveraged to initiate data acquisition from passive sources. Given a pattern of assertions and constraints, where an assertion may be related to a source event and may represent a set of events that collectively satisfy the constraints of that assertion and other assertions and may collectively match the pattern, a method can be defined to handle a mixed pattern of active and passive data sources and acquire a set of target events from the passive data sources in a timely manner.

In one embodiment, the pattern of all passive data can be processed using periodic queries to retrieve events (e.g., polled) from one or more sources to trigger updates and simulate the effect of having an active data source. Once a source of events (active or polled) is available in the pattern, the remaining passive data sources can be queried for events related to them. In one embodiment, constraints between the active and passive data (e.g., common constraints between active and passive data) are translated into a query term (e.g., all constraints between two assertions are translated into a single query). This query term uses the values of each of the available events (e.g., values obtained actively or passively in a previous query) to build the desired query on the passive data source represented by the assertion being processed. If there are multiple available events from multiple assertions, the query term uses the events along with the appropriate constraints to generate the optimal query. For example, if an active event contains a time value and a passive event is constrained to +/- 5 minutes from the time value of the active event, a query can be constructed to identify events in the passive data source that fall within that time window. If the number of events is limited in the set of passive events, a query is constructed to retrieve the events closest to a target value (e.g., time). This may require running two queries to retrieve values above/below the target value. Once the set of events for a passive assertion is obtained, the events are streamed into the pattern as if they were active, which may trigger more constraint processing and may involve more passive data sources.

Input source data 161, which may contain a number of events, may be provided to event processing module 152 for each given template in templates 162. In one embodiment, templates 162 may be predefined and stored in persistent storage 182 for later use. Templates 162 may be defined using a visual notation and stored with a definition of a machine-readable format (e.g., JSON, XML, binary, etc.) used to process the template. Each template is represented by event processing module 152, which receives all events of the event type that appears in the template. For each template, module 152 may filter events (as assertions) from input source data 161 by looking for all possible matches for the event, if constraints are defined.

For each set of matching events, the event publishing module 155 may publish one or more new events and store them in the storage device 182 as published events 165. When publishing an event, the template definition may define data from the source events that are included in the published event. Additionally, to explicitly copy data, some aspects of the source events may be automatically copied to enable traceability of the published event and system-wide concerns (e.g., entity tracking). In one embodiment, the published events 165 may serve as input events to the server 150.

Solution generation module 153 may create a set of feasible solutions 163 (stored in storage 182) for a template (e.g., any of templates 162). To create solutions 163, module 153 may start with all events and then incrementally process the constraints to create solutions that are subsets of the original set of events. For each constraint, each solution created by the previous constraint is augmented with events that match that constraint. This process performs a breadth-first traversal (or search) of all possible solutions by incrementally pruning the events of any one solution and generating new solutions if there are viable alternative solutions. For each type of constraint, generating feasible target events for an input solution is constraint-specific logic. Once a set of target events is identified, a new solution is generated from the input solution and the identified target events. If multiple sets of targets are identified, multiple solutions can be created from one input solution. Once all constraints have been processed, a new set of solutions is completed. Each such solution is also called a "template instance" to mean an instance that matches that template type.

Once the template instances containing matching events are determined by module 153, an action is evaluated, such as action 164 taken by result processing module 154. Action 164 may be predetermined and stored in storage 182. If all assertion multiplicities are satisfied for the inputs to the action, module 154 may trigger the action. A triggered action has access to the input event that initiated the action. If a previously triggered action has not been triggered since updating the solution, it is not triggered. Thus, if a solution matches a set of multiplicities and a new event arrives, which is no longer the case, a previously triggered action is not triggered. If it is an issue event, the event is cancelled if it is not triggered. This removes the event from all solutions that may contain it and re-evaluates their template instances.

FIG. 2 is a flow diagram illustrating a method for processing events according to one embodiment. Process 200 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 200 may be performed by server 150, e.g., some or all of modules 151-155.

Referring to FIG. 2, in operation 201, processing logic receives input source data including event data for one or more events. In operation 202, processing logic selects one or more event definitions that match the event data. In operation 203, for each matching event definition, processing logic inputs the event definition into a template to generate a set of events. The template includes a number of assertions, with the event definition as one of the assertions, and each assertion includes a constraint. In operation 204, processing logic incrementally processes the constraints of the assertions to create one or more solutions that are subsets of the set of events. In operation 205, for each constraint and each solution, processing logic identifies a set of target events that are executable for that solution and creates a new solution based on the solution and the identified set of target events, thereby creating a set of new solutions.

FIG. 3 is a flow diagram illustrating a method for processing events according to another embodiment. Process 300 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 300 may be performed by server 150, e.g., some or all of modules 151-155.

3, in operation 301, the processing logic receives input source data (including events), for example, directly from the external system 171 or by polling new data from the external system 171. As previously described, the external system 171 may be a cluster of machines that collectively provide the input source data. Once the input source data is received, in operation 302, the processing logic matches the input source data against the event definitions to determine the role that the data represents in the pattern being matched. In operation 303, the processing logic determines whether the input source data matches an event definition. Since one piece of data may match multiple event definitions, it is forwarded to multiple template type processing elements. If no event definition matches the data, in operation 304, the data can be archived for possible matches with future event definitions or discarded based on overall requirements. Otherwise, in operation 305, for each event type, the processing logic forwards the data to the processing element (1103) of the associated template type that has the event type as an assertion in the template definition. Upon receiving an event of a template type, processing logic updates the set of solutions for known events in operation 306. This update can be performed after a delay or immediately when a sufficient number of new events are received based on latency and throughput requirements. A solution is a subset of all events sent to the template processing element (also called a module, unit, or logic) that collectively match the assertions of the template definition and satisfy all the constraints between the assertions. The required number of events in an assertion is a secondary condition for whether a solution "matches" and does not limit the events considered in the solution. Each template processing element of the template type creates an updated set of solutions if the event is known. Each solution is processed separately, and processing logic checks to determine whether all assertions that are input to the result are satisfied in operation 307. If they are satisfied and the result does not emit an equivalent event (operation 308), processing logic emits the event as a result in operation 309. If not, processing logic proceeds to operation 310. In one embodiment, publishing an event involves reviewing the result definition to determine which data elements from the source event should be copied to the published event, adding the data determined by the system to the published event, and then sending the event to any external systems (e.g., system 171) that have requested it to be sent, and/or sending the event as a newly received event to server 150 itself (operation 301). Following operation 309, any affected template processing elements persist, and in operation 310, the processing logic updates state to record or track all received and published events. Note that the state of each solution may be tracked and maintained independently of other solutions, state updates may occur continuously during or at the end of computation processing, and state updates may occur while processing one event or a small number of events to meet throughput or latency requirements.

Template Notation The following sections define the notation used and the options available for defining templates within a system, such as system 100. Figures 4A-4G are diagrams illustrating template notation according to one embodiment.

Source Events/Assertions Referring to Figure 4A, events called assertions appear on the template, e.g., as ovals, with a label indicating the event type (e.g., fire alarm, smoke). Other types of assertions are supported, such as constant values or configuration values. Events are extracted from the input data provided to the system, as defined in the system description. If an event definition is changed, the extracted set of events is updated from the archived raw data. Such changes may result in the publication of new matching events or the removal of previously matching events that no longer match the changed definition.

A source event can have a multiplicity specification that indicates the minimum and maximum number of such events that match one template instance (one set of matching/conforming events). For example, a template that searches for money transfers might search for a withdrawal followed by a deposit, while another template might search for at least three people from a particular group who have booked a trip to the same city.

Emission Events/Results/Actions Referring to FIG. 4B, aspects of the disclosure include issuing events that represent conditions assumed by the template. An issue event may be a type of template action or result, e.g., represented by a rounded rectangle with a text name label as shown below, and is connected to each source event or group. Other results may include alerts or invocation of specific programming logic. Each source event is connected to a result, e.g., by a line. In one embodiment, each result that issues an event may include a map that defines a data mapping from the source event to the issue event. In one embodiment, the time range of all source events is automatically recorded in the issue event as in the source template instance. For example, if each event is timed, the system may record the minimum and/or maximum time of all input events in the issue event. The template creator can specify that selected fields from the source events are propagated to the issue event. Even if there are more source events on the template, an event is issued as soon as it matches each connected source event. This therefore allows events to still be issued on partial template matches, if warranted. For example, if a critical step in a process is detected, the template may want to issue an event even though there are other steps in the process that may also be detected. Such partial matches can be used to drive visualization, risk management, and/or alerts.

Time Plane With reference to FIG. 4C, in some embodiments, the primary constraint of the template is the relationship control of event times. With time constraints, the author can simply indicate that one event must follow another within a certain period of time, or within a certain tolerance of each other within a certain period of time. Such constraints may apply to the real-world times of events, rather than the time at which the data is processed or recorded by the system. Time constraints can include fuzzy matching parameters, such as A must come 15-20 minutes after B, or A must come 10+/-2 minutes after B. In addition to time ranges, time constraints can require that the time difference be greater or less than a specified period (such as less than 4 minutes, or at least 5 minutes). Time constraints may be represented, for example, by a directional arrow with some time constraint as a text label on the line. An event can have more than one time value (such as airline booking time, departure time, and arrival time), in which case the time field name appears in the constraint text, such as "arrival<departure" or "booking+24h<departure".

Relationship Aspects Referring to FIG. 4D, a relationship constraint may indicate, for example, that two events must have a particular relationship value between two fields. The data fields come from the original data items that match the event definition. The constraints are useful to ensure that transactions apply to the same account, originate from or refer to the same entity (=), that amounts are greater than (>), less than (<), greater than or equal to (>=), less than or equal to (<=), etc. A relationship constraint may be represented, for example, by a line with an arrow, field names, and a relational operator such as "name=name", read in the direction of the arrow with the first field name from the origin of the arrow and the second field name from the head of the arrow (as shown below). Relationship constraints can operate on strings, numbers, time data, unique IDs, and geographic data, with both fields of compatible type.

Aggregation An aggregation constraint performs a calculation on a set of source events and compares it to a threshold. The threshold can be a constant or a calculated value from another set of source events or the same set of source events. Examples include finding a total of remittances over $10,000 in a 30 day period, or finding an aggregate amount of 200 pounds of fertilizer sold to the same buyer, or buyers associated with the same organization or cell. An aggregation constraint may be represented, for example, as a line containing a primary calculation (e.g., sum, average, minimum, maximum) and a symbol indicating either a threshold or a secondary calculation (as shown in FIG. 4E).

Partitioning A partitioning constraint partitions a set of potentially matching events into subsets based on a field value. In one embodiment, the field value may be an identifier for a person, place, or thing. In another embodiment, the field value may be a quantitative value, such as a dollar amount or other measurement to be compared. This is used to ensure that events with different field values are not incorporated into the same template solution. For example, when considering whether travel to a restricted country matches a restriction, a partitioning constraint is used to ensure that each solution only considers travel by one person. A partitioning constraint is generally from an assertion to the same assertion indicating that it applies to a set of events, and may be represented by a line containing the field name and "par" as an operator, such as "field_name par field_name", as shown in FIG. 4F, indicating that all such events must have the same name to be considered within the same template instance (solution).

Logical Combinations To support more complex situations, groups can be used to combine conditions (source events). For a group to be satisfied, all events contained in the group must be satisfied. If an action has multiple inputs, any of the inputs can trigger the action. Thus, each group acts like an "and" condition, and multiple input rows act as "or" conditions. Groups are represented, for example, by ellipses surrounding source events (e.g., fuel oil, fertilizer, explosives, etc.) as shown in FIG. 4G.

5A-5D are diagrams illustrating example templates according to one embodiment. The sample templates are provided to illustrate contextual notations. For example, in FIG. 5A, a sample template (e.g., Template 1) may be defined to detect jamming tactics. In FIG. 5B, a sample template (e.g., Template 2) may be an attack strategy using jamming issue events and custom constraints. In FIG. 5C, a sample template (e.g., Template 3) may be an aggregation between two sets of correlated events. In FIG. 5D, a sample template (e.g., Template 4) may use And/Or for more complex conditions.

Representation Figures 6A and 6B are diagrams illustrating a representation of a template in JavaScript Object Notation (JSON) according to one embodiment. Figures 6A and 6B describe a JSON representation of one of the previous examples as a persistent representation of one of the expressions. The expression may also be represented in XML or RDF.

Template Matching/Constraint Solving/Solution Filtering Aspects of the present disclosure include template matching. For example, let E be the set of events that satisfy one of the assertions in the template definition, and let C be the set of all constraints on those assertions. The template matching component creates all subsets of E that satisfy the set of constraints C where the target assertion of each C has an event. Note that if an assertion is optional, it may or may not have an event, and if it does not, it does not need to satisfy the corresponding constraint for a valid solution. Thus, a solution may have a subset of all the assertions given and still be considered a solution if it satisfies all the constraints that have any of those assertions as a target. Each such solution becomes a template instance of the system. Each instance may be persisted and tracked as it receives new events, and may be deleted if it no longer applies to the known set of events (most commonly when a significant event is cancelled, as explained in more detail below).

In one embodiment, the method for creating a subset of E is as follows:
1) Order the split constraints such that each constraint is preceded by a constraint that has a source of the split constraint and a constraint that targets a source from the split constraint. In other words, treat all constraints (source->target) as split constraints in a directed graph order based on their direction order.
2) Generate the event subsets of the partition constraints in order:
For the source event of a split constraint, split the event into sets with the same values for the fields referenced in the constraint.
b) Iterate through all non-split constraints that stem from the target of the split constraint until a split constraint is encountered.
3) Process all remaining unprocessed non-split constraints.

Constraints are processed by taking as input all event subsets found by the previous constraint, and creating a subset of subsets that also satisfy the constraint in question. So, as an example, if a constraint presents three subsets, and it is found that subsets 1 and 3 satisfy the constraint, but subset 2 needs to be split into two subsets to satisfy the constraint, then create four subsets as input to the next constraint. This process can be likened to a breadth-first search, but it is not a search in the usual sense of looking for a single solution, given that all solutions are created. In this case, all feasible solutions are identified.

FIG. 7 is a flow diagram illustrating a method for generating a solution according to one embodiment. Process 700 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 700 may be performed by server 150, such as solution generation module 153.

7, at operation 701, processing logic sorts the constraints. As previously described, the partition constraints may be ordered such that each constraint is preceded by any constraints that have a source of the partition constraint and a constraint that targets a source from the partition constraint. In other words, all constraints (source->target) are treated as partition constraints in a directed graph order based on their direction order. At operation 702, processing logic starts with a solution that includes all events, and then progressively processes the constraints to create solutions that are subsets of the original set of events. That is, at operations 703-705, for each constraint, processing logic augments each solution created by the previous constraint with events that match that constraint. That is, processing logic collects a set of target events that independently satisfy the constraint. This process performs a breadth-first traversal (or search) of all possible solutions by progressively pruning events in any one solution and creating new solutions if there are alternative viable solutions. For each type of constraint, it is constraint-specific logic that creates executable target events for the input solution. Once a set of target events is identified, a new solution is created from the input solution and the identified target events. Thus, at operation 706, processing logic replaces the input solution with a new solution for each set of target events. In one embodiment, multiple solutions can be created from an input solution if multiple sets of target events are identified. Once all constraints have been processed, a new set of solutions is completed. Each such solution is also called a "template instance," meaning an instance that matches that template type. At operation 707, processing logic determines whether there are any more solutions to update. If so, processing logic proceeds to operation 704. If not, processing logic proceeds to operation 708, where processing logic determines whether there are any more constraints. If so, processing logic proceeds to block 703. If not, processing logic proceeds to operation 709, where a set of executable solutions (e.g., solution 163 of FIG. 1B) is created for the template.

In another embodiment, a method for creating a subset of E is as follows:
1) Group non-split constraints by related assertions, with equality constraints first, followed by other constraints between the same assertions, each of which is called a stage.
2) Form a hierarchical data structure (e.g. a tree with leaves as raw input events) and order the stages to culminate in a single stage, using any input assertions to ensure that raw events only enter one stage and only processed results enter other stages. The identification of stages and ordering of constraints may happen when the template is instantiated for processing, as events are received or pre-processed and delivered along with the template definition.
3) Each assertion in each stage is processed in order to receive each event from each input and create all valid event pairs that satisfy the constraint. If the constraint follows another constraint in the stage, it receives the set of processed pairs and filters them against those that are also valid for that constraint.
4) This results in a stream of partial solutions with one event for each assertion constrained in the template.
5) Use the set of partition constraints to form partition keys for each partial solution.
6) If the minimum multiplicity of an assertion is >1, then all partial solutions for the same partition key are merged to form a complete solution, which is compared against the multiplicity constraints of all assertions and either accepted or rejected as a valid solution. If a valid solution is found, it fires an event as defined in the template.
7) If the minimum multiplicity of all assertions is <= 1, partial solutions and event emissions can be combined by incrementally modifying previously emitted results with additional events when a new partial solution containing previously unemitted event data is received.
8) If a valid solution is found for any partition key and a containing invalid solution is later found (one in which all events are included in the valid solution), a retract is issued to indicate that the previous valid solution is no longer valid and that any solutions that depend on that event are suspect and need to be reevaluated.
9) If the minimum multiplicity is 0, the processing is split into required and optional constraints, and any partial solutions from the required constraints are processed with both the optional constraints and directly for combination and emission. If an optional assertion matches after emitting the results from the required constraints only, it may result in a retraction.

In this manner, FIG. 8 is a flow diagram illustrating a method for generating a solution according to another embodiment. Process 800 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 800 may be performed by server 150, e.g., solution generation module 150.

In operations 801 and 802, the processing logic continues to process events as they arrive and feed into the constraint processing pipeline established by ordering and grouping into stages. In operation 803, the processing logic may place each received event into a partial solution for each assertion with that event type. This allows constraints to use partial solutions as inputs and outputs. Each constraint, if it is the first constraint of a stage, keeps a list of matching partial solutions for each of its inputs for each observed value in the constraint field. This allows it to create a new partial solution that combines both inputs when a new input is received. For example: A constraint constrains assertion A with field identifier (id) to be equal to assertion B with field person_id. For each value received for A.id and B.person_id, keep track of the partial solutions with that value. When a new partial solution containing A arrives with a particular value, it can be combined with all matching partial solutions containing B.person_id with the same value. Once the partial solutions have been consolidated based on some form of equality, the remaining constraints in that same stage only need to filter the stream of partial solutions to those that also satisfy the constraint. Operation 804 reflects this stage-by-stage processing and feeding the partial solutions from one constraint to the next within a stage and from one stage to the next, as defined in the template. At operation 804, the processing logic determines whether there is an optional stage. If there is an optional stage, the stream of partial solutions is split and proceeds directly to operations 806 and 807. The optional stages may be processed in the same manner as the required stages, except that the output of each stage is sent to both operation 807 and the next optional stage. In one embodiment, the optional stages are ordered in the same manner as the required stages, such that new inputs are processed by only one stage and then combined with the partial solution received from the previous stage (operation 806). The partial solutions for the next constraint processing are split based on a split key constructed from the split fields. The key may be formed from the values in the partial solution for each split field value in the template (operation 807). Partial solutions with different split keys are not combined into the same solution. In operation 808, processing logic determines whether the minimum multiplicity is greater than 1. In the absence of the assertion of minimum multiplicity > 1, the stream of partial solutions can be fed directly to the result processing, and the combination of results performed incrementally as new inputs need to be added to the previous result for a particular split key (operation 809). If such multiplicity is present in the template, the partial solutions may be combined and held until a valid or invalid solution is found (operation 810). If an invalid solution is found first, the result is not triggered for that split key. If a valid solution is found first for a split key, the result may be triggered. If an invalid solution is found after a valid solution, the triggered result is not triggered (in the case of event publishing, this result is retracted, as described in more detail below).

Event Emission and Actions Once the template instances containing matching events have been determined (as described above), the action to be executed (e.g., action 164 in FIG. 1B) is evaluated. If all assertion multiplicities are satisfied for the input to the action, the action may be triggered. A triggered action has access to the input event that initiated the action. If a previously triggered action has not been triggered since updating the solution, the action is not triggered. Thus, if a solution matches a set of multiplicities and a new event arrives, which is no longer the case, previously triggered actions are not triggered. For emission events, the event is retracted if it is not triggered. This removes the event from all solutions that may contain it and causes their template instances to be re-evaluated.

FIG. 9 is a flow diagram illustrating a method for processing results or actions according to one embodiment. Process 900 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 900 may be performed by server 150, such as result processing module 154.

Referring to FIG. 9, once a set of solutions has been identified, result processing is performed. At operations 901-903, for each identified solution and each result in the template, processing logic evaluates the state of the results for that solution. That is, at operation 903, processing logic determines whether all assertions are satisfied. If all assertions are satisfied, then at operation 904, processing logic determines whether an equivalent action has previously occurred. If an equivalent action has not previously occurred or been triggered, then at operation 905, processing logic triggers an action (e.g., one of actions 164 of FIG. 1B). If the assertion is not satisfied and an action was previously triggered (operation 907), then at operation 906, processing logic determines that the action has not been triggered and undoes the action.

If the outcome is to publish a new event, triggering consists of creating the event data and publishing it, whereas non-triggering consists of removing the event data from the system and recalculating the state of the affected templates (i.e. the reverse action). In both cases, ripple effects can occur, since templates are updated by the published or retracted event.

When an event is emitted in this way, data from the input event (assertion) is transferred to the emitted event as defined in the resulting "data mapping". This data mapping defines which fields of which assertion are copied to which fields of the emitted event. In addition to this explicit data mapping, there are implicit mappings, which allow adding data to the emitted event (e.g. needed for full-text search) or algorithmically copying data from the input event (e.g. entity tracking).

Entity tracking refers to the automatic copying of identifying information from source events to emitted events in order to track "entities" involved in template matches. All entities referenced in the source event are aggregated in the emitted event and added to the entity list of any events emitted with this event as the source. This hierarchical aggregation of entity data is useful in many situations where the invention is used to track the behavior of people, organizations, or devices (commonly referred to as "entities"). In addition to simple data duplication, it is also possible to support calculations that occur as part of a "data mapping" process, where the mapping includes the formula for the calculation as well as assertions and field references as inputs to the calculation.

FIG. 10 is a flow diagram illustrating a method for publishing an event according to one embodiment. Process 1000 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 1000 may be performed by server 150, such as event publishing module 155.

In FIG. 10, event publication begins with data mapping. At operation 1001, processing logic may create a skeleton for the event that includes basic data or values (i.e., a unique ID, a data type marking, a creation time, etc.). Together, operations 1002 and 1006, processing logic iterates for each data mapping entry in the result definition. At operation 1003, processing logic may collect values from source events referenced in the data mapping entries from those events. At operation 1004, processing logic performs the specified calculation on the input values. At operation 1005, processing logic places the results in the generated event. At operation 1006, processing logic determines whether there are any more mappings. If so, processing returns to operation 1002. If not, processing logic proceeds to operation 1007 where processing logic extracts or collects entity data from the input or source events. At operation 1008, processing logic aggregates or constructs the entity data into an entity map that identifies each entity referenced in the source event and by which field it is referenced. At operation 1009, processing logic performs global computations, such as text indexing, and publishes the event to some external system (e.g., system 171 of FIG. 1A) and/or back to the system (e.g., server 150).

Constraint Details Embodiments of the present disclosure may support constraints that are "split" or "relationship" constraints, allowing the constraint to reference fields or aggregations from the event as inputs to the constraint.

The following processes 1100 and 1200 may be applied to processes 700 and 800 above when combining partial solutions within a constraint that merges two event streams. If the constraint is filtering a single event stream, simply comparing the actual values of each partial solution is sufficient.

A partitioning constraint ensures that events with different values for a selected field are not in the same solution, thus splitting the events into separate subsets. It is widely used to ensure that all events relate to the same person, place, organization or activity. For example, a template looking for suspicious travel might look at the travel records of one person, while a template looking at maintenance patterns might look at the records of one airline or facility. This constraint works based on evenness, which is explained in the following paragraphs.

A relationship constraint restricts the solutions to those that have events containing values that match some relationship. Strict equality is easiest to test for and can be implemented by putting the events into a hash based on this value. This is often the case for unique identifiers or other string values. For numbers, a tolerance can be specified, such as ±, which allows for fuzzy equality. This is often needed with floating point values. For example, A=B±0.5 finds all floating point numbers in B that are within 0.5 of the value of A. This is calculated by sorting all the values of A and B, and testing each value of B to compare it to the current value of A. When B falls outside the range of A's values, the system moves on to the next value of A and continues identifying values of B that are within the range of A's current value. The same method can be used for datetime values. For both numbers and datetime values, it is possible to allow an offset, such as A<B+5±2. In this case, the offset offsets the value of B before comparing it to A, but it otherwise works the same as the previous one.

FIG. 11 is a flow diagram illustrating a method for processing constraints according to one embodiment. Process 1100 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 1100 may be performed by server 150, such as solution generation module 154.

Process 1100 may use strict equality for strings, identifiers, or other unique values in some embodiments. At operation 1101, processing logic groups a set of target event values by constrained value. At operation 1102, processing logic iterates through each solution and collects target events by source event value using the source values. At operation 1103, processing logic combines the source solutions with the target events into a new solution; that is, each distinct value in the source set becomes a new solution output by the constraint. In some embodiments, process 1100 is also used for partitioning constraints.

12 is a flow diagram illustrating a method for processing constraints (e.g., relationship constraints) according to another embodiment. Process 1200 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 1200 may be performed by server 150, such as solution generation module 154.

Referring to FIG. 12, at operation 1201, processing logic may sort source and target events based on the constraint field values being compared. At operation 1201, processing logic determines whether all source and target events have been processed. If all source and target events have been processed, processing logic proceeds to operation 1209 where a new solution is calculated by adding a set of target events (or target set) to the input solution. If not, processing logic proceeds to operations 1203 and 1204 where processing logic compares the current source and target event values. If the target event value satisfies the constraint, at operation 1205, processing logic adds the target event value to the target set (or solution) and proceeds to the next target (operation 1206). If the target event value is later than the current source event value, processing logic discards the target event value at operation 1207. If the target event value precedes the current source event value, then at operation 1208 the processing logic proceeds to the next source event value and repeats until all source and target event values have been examined (operations 1202 and 1209).

FIG. 13 is a flow diagram illustrating a method of event retention according to one embodiment. Process 1300 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 1300 may be performed by server 150, such as input data processing module 151.

13, a simple query may be constructed using constraints 1301 and active data 1302 (e.g., events) (operation 1303). For example, if constraints 1301 are simple relational operations (e.g., =, !=, <, <=, >, >=), a query may be constructed to include all constraints between active data 1302 and passive data. As previously described, the constraints between active data 1302 and passive data may be converted into query terms (e.g., the constraints between two assertions may be converted into a query). The query terms may utilize the values of each available event (active or passive events obtained in a previous query) to construct a target query on the passive data source represented by the assertion being processed. In one embodiment, if there are multiple events available from multiple assertions, the query terms may utilize the values along with the appropriate constraints to generate an optimal query. Constraints 1301 may be predefined as part of patterns of data (active and/or passive) and may be available at the beginning of deployment of a system (e.g., system 100 of FIG. 1 ) to guide query construction for each data pattern, constructing queries using values from active data 1302 (e.g., active events).

In operation 1304, the constructed target query may be used to obtain query results (which may be from a passive data store) representing passive event data. The query results may be streamed to a system (which may be similar or the same as the other streaming sources described above) for constraint resolution.

At operation 1305, constraint solving may be performed on the query results. Aspects of constraint solving have been previously described herein and will not be described again for the sake of brevity.

In operation 1306, an event retention may be performed on the query results. In some embodiments, the query results that have passed constraint resolution (e.g., passive events) may be retained for reference. For example, in cases where active inputs allow for changes, and in more complex cases, the query results that have passed constraint resolution (in operation 1305) are retained for reference. In some embodiments, if there is only one active data source and the data source does not support changes to the input events over time, the processing of the query results may be passive in nature and no data from the events (e.g., events from the passive source) needs to be retained to resolve the constraints. If the data in the active data can change over time (e.g., events are removed), the query results may be retained so that the constraint resolution can be modified when the active events are modified. In some embodiments, the passive sources cannot be queried again to process the changes, since the passive source data may have changed, which may cause inconsistent results. For example, if an active event is removed from the data stream, any passive data for that event may need to be removed from the set of events for this pattern, and the output of the entire pattern may need to be modified. The same is true when changing values used to construct a query that may return different events, and therefore may need to remove some previous events to adjust for the new values. As an example, if a date field is modified, events selected related to the old date may no longer match the modified date. In some embodiments, the passive source can be queried again, but in other embodiments, if the passive source has also been modified, previous results may need to be retained to produce a complete and appropriate set of results.

FIG. 14 is a flow diagram illustrating another method of event retention according to one embodiment. Process 1400 may be performed by processing logic that may include software, hardware, or a combination thereof. For example, process 1400 may be performed by server 150, such as input data processing module 151.

Referring to FIG. 14, constraints 1401 and active data 1402 (e.g., events) may be used to construct ambiguous or complex queries (operation 1403). For example, if constraints 1401 are ambiguous with +/- values, multiple query terms may be used to construct queries for each constraint. Even if the ambiguity aspect applies to simple relational operators, it may still be combined into a single query with additional query terms. As mentioned above, if the number of result events is limited to optimize the query, two queries may be used to resolve the ambiguous terms to obtain events above/below a target value. These may be combined into simpler terms to further limit the number of queries, or with other similar ambiguous queries, for example, n*2 queries (where n is the number of events above/below a target value) for each above/below combination. In some cases, the order of operations is important and may be considered when constructing the query.

If the constraint 1401 involves a more complex operation (e.g., an aggregate such as sum, average (avg) function, or array operation), it may be necessary to perform the processing of such a constraint after the query execution provides a set of candidate events and all other constraints have been processed. In some passive data stores (e.g., SQL databases), it may also be possible to execute a subquery or preceding query to obtain the aggregate or function value used in the query that satisfies the primary constraint. For example, in a constraint that the sum of field "a" of event A must be equal to the sum of field "a" of event B, a query can be constructed to use all other constraints to obtain the set of A and B that satisfies all other constraints, and then narrow down to the set of A and B whose sum is equal. As another example, if there is a constraint that requires country codes to be equal between A and B, a SQL query that calculates the sum of A and B by country code can be executed in advance or as a subquery of the constraint query, and only the countries whose sum is equal need to be fetched in the actual constraint query that returns the individual events.

In operation 1404, each constructed query may be used to obtain query results (which may be from a passive data store) representing passive event data. The query results may be streamed to a system (which may be similar or the same as the other streaming sources described above) for constraint resolution.

At operation 1405, constraint resolution may be performed on the query results from each constructed query. Aspects of constraint resolution have been previously described herein and will not be described again for the sake of brevity.

In operation 1406, an event retention may be performed on the query results from each constructed query. In some embodiments, the query results (e.g., events) that have passed through constraint resolution may be retained for reference. For example, in cases where active inputs allow for changes, and in more complex cases, the query results that have passed through constraint resolution (in operation 1405) are retained for reference. In some embodiments, if there is only one active data source and the data source does not support changes to the input events over time, the processing of the query results may be passive in nature and no data from the events (e.g., events from the passive source) needs to be retained to resolve the constraints. If the data in the active data can change over time (e.g., events are deleted), the query results may be retained so that the constraint resolution can be modified when the active event is modified. In some embodiments, the passive source cannot be queried again to process the changes, since the passive source data may have changed, which may cause inconsistent results. For example, if an active event is deleted, any passive data related to that event may need to be removed from the set of events for this pattern, which may require the output of the entire pattern to be modified. The same is true when changing values used to construct a query that may return different events, and therefore may need to remove some previous events to adjust for the new values. As an example, if a date field is modified, events selected related to the old date may no longer match the modified date. In some embodiments, the passive source can be queried again, but in other embodiments, if the passive source has also been modified, previous results may need to be retained to produce a complete and relevant result set.

It should be noted that some or all of the components shown and described above may be implemented in software, hardware, or a combination thereof. For example, such components may be implemented as software installed and stored in a persistent storage device that is loaded into memory and executed by a processor (not shown) to perform the processes or operations described throughout this specification. Alternatively, such components may be implemented as programmed executable code or embedded in dedicated hardware such as an integrated circuit (e.g., an application specific integrated circuit or ASIC), a digital signal processor (DSP), or a field programmable gate array (FPGA) that is accessible to an application via a corresponding driver and operating system. Furthermore, such components may be implemented as specific hardware logic in a processor or processor core as part of a set of instructions that are accessible by the software components via one or more specific instructions.

FIG. 15 is a block diagram illustrating an example of a data processing system that may be used in one embodiment. For example, system 1500 may represent any of the data processing systems, such as user devices 101-102, server 150, and/or external system 171, described above, that perform any of the processes or methods described above. System 1500 may include many different components. These components may be implemented as integrated circuits (ICs), parts thereof, separate electronic devices, or other modules that fit onto a circuit board, such as a computer system motherboard or add-in card, or as components that are otherwise integrated into the chassis of the computer system. It should also be noted that system 1500 is intended to illustrate a high-level view of many of the components of a computer system. However, it should be understood that additional components may be present in certain embodiments, and that different arrangements of the components than those shown may occur in other embodiments. System 1500 may represent a desktop, laptop, tablet, server, mobile phone, media player, personal digital assistant (PDA), personal communicator, gaming device, network router or hub, wireless access point (AP) or repeater, set-top box, or combinations thereof. Additionally, although only a single machine or system is shown, the term "machine" or "system" is also intended to include any collection of machines or systems that individually or collectively execute a set (or sets) of instructions to implement one or more of the methodologies discussed herein.

In one embodiment, system 1500 includes processor 1501, memory 1503, and devices 1505-1508 connected via bus or interconnect 1510. Processor 1501 may represent a single processor or multiple processors including a single processor core or multiple processor cores. Processor 1501 may represent one or more general purpose processors such as a microprocessor, a central processing unit (CPU), or the like. More specifically, processor 1501 may be a complex instruction set computer (CISC) microprocessor, a reduced instruction set computer (RISC) microprocessor, a very long instruction word (VLIW) microprocessor, or a processor implementing other instruction sets or a combination of instruction sets. Processor 1501 may be one or more special purpose processors, such as an application specific integrated circuit (ASIC), a cellular or baseband processor, a field programmable gate array (FPGA), a digital signal processor (DSP), a network processor, a graphics processor, a network processor, a communications processor, a cryptographic processor, a co-processor, an embedded processor, or any other type of logic capable of processing instructions.

The processor 1501 may be a low-power multi-core processor socket, such as an ultra-low voltage processor, and may act as the main processing unit and central hub for communicating with the various components of the system. Such a processor may be implemented as a system on a chip (SoC). The processor 1501 is configured to execute instructions to perform the operations and steps discussed herein. The system 1500 may further include a graphics interface in communication with an optional graphics subsystem 1504, which may include a display controller, a graphics processor, and/or a display device.

The processor 1501 may communicate with the memory 1503, which in one embodiment may be implemented through multiple memory devices to provide a certain amount of system memory. The memory 1503 may include one or more volatile storage (or memory) devices, such as random access memory (RAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), static RAM (SRAM), or other types of storage devices. The memory 1503 may store information including sequences of instructions to be executed by the processor 1501, or any other device. For example, executable code and/or data for a wide variety of operating systems, device drivers, firmware (e.g., input/output basic system or BIOS), and/or applications may be loaded into the memory 1503 and executed by the processor 1501. The operating system may be any type of operating system, such as Microsoft's (registered trademark) Windows (registered trademark) operating system, Apple's (registered trademark) MacOS (registered trademark)/iOS (registered trademark), Google's (registered trademark) Android (registered trademark), Linux (registered trademark), Unix (registered trademark), or other real-time or embedded operating systems such as VxWorks.

System 1500 may further include IO devices such as devices 1505-1508, including a network interface device 1505, an optional input device 1506, and other optional IO devices 1507. Network interface device 1505 may include a wireless transceiver and/or a network interface card (NIC). The wireless transceiver may be a WiFi transceiver, an infrared transceiver, a Bluetooth transceiver, a WiMax transceiver, a wireless mobile phone transceiver, a satellite transceiver (e.g., a Global Positioning System (GPS) transceiver), or other radio frequency (RF) transceiver, or a combination thereof. The NIC may be an Ethernet card.

The input devices 1506 may include a mouse, a touchpad, a touch-sensitive screen (which may be integrated with the display device 1504), a pointer device such as a stylus, and/or a keyboard (e.g., a physical keyboard or a virtual keyboard displayed as part of a touch-sensitive screen). For example, the input devices 1506 may include a touch screen controller connected to a touch screen. The touch screen and touch screen controller may detect contact and movement or destruction using any of a number of touch sensitivity technologies, such as, but not limited to, capacitive, resistive, infrared, and surface acoustic wave technologies, as well as other proximity sensor arrays or other elements to determine one or more points of contact with the touch screen.

IO devices 1507 may include audio devices. Audio devices may include speakers and/or microphones to facilitate voice-enabled functions such as voice recognition, voice duplication, digital recording, and/or telephony functions. Other IO devices 1507 may further include universal serial bus (USB) ports, parallel ports, serial ports, printers, network interfaces, bus bridges (e.g., PCI-PCI bridges), sensors (e.g., motion sensors such as accelerometers, gyroscopes, magnetometers, light sensors, compasses, proximity sensors, etc.), or combinations thereof. Devices 1507 may further include an image processing subsystem (e.g., a camera), which may include optical sensors such as charge-coupled device (CCD) or complementary metal-oxide semiconductor (CMOS) optical sensors utilized to facilitate camera functions such as recording of photographs and video clips. Certain sensors may be coupled to the interconnection arrangement 1510 via a sensor hub (not shown), while other devices such as a keyboard or thermal sensor may be controlled by an embedded controller (not shown), depending on the particular configuration or design of the system 1500.

A mass storage device (not shown) may also be coupled to the processor 1501 to provide persistent storage of information, such as data, applications, and one or more operating systems. In various embodiments, this mass storage may be implemented via a solid state device (SSD) to enable thinner and lighter system designs and improve system responsiveness. However, in other embodiments, the mass storage may be implemented primarily using a hard disk drive (HDD) with a small amount of SSD storage acting as an SSD cache to enable non-volatile storage of context state and other such information during power-down events and to allow for fast power up when system activity resumes. A flash device may also be coupled to the processor 1501, for example via a serial peripheral interface (SPI). This flash device may provide non-volatile storage of system software, including basic input/output software (BIOS) and other firmware of the system.

The storage device 1508 may include a computer-accessible storage medium 1509 (also known as a machine-readable storage medium or computer-readable medium) that stores one or more sets of instructions or software (e.g., processing modules, units, and/or logic 1528) that embody one or more of the methodologies or functions described herein. The processing modules/units/logic 1528 may represent any of the previously described components, such as the input data receiving module 151, the event processing module 152, the solution generating module 153, the result processing module 154, and the event publishing module 155, as previously described. The processing modules/units/logic 1528 may reside completely or at least partially within the memory 1503 and/or within the processor 1501 during execution thereof by the data processing system 1500, the memory 1503, and the processor 1501, which also constitute a machine-accessible storage medium. The processing modules/units/logic 1528 may further be transmitted or received over a network via the network interface device 1505.

The computer-readable storage medium 1509 may also be used to persistently store some of the software functions described above. Although the computer-readable storage medium 1509 is shown in the exemplary embodiment as being a single medium, the term "computer-readable storage medium" should be interpreted to include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that store one or more sets of instructions. The term "computer-readable storage medium" should also be interpreted to include any medium that can store or encode a set of instructions for execution by a machine and cause the machine to perform any one or more of the methodologies of the present disclosure. Thus, the term "computer-readable storage medium" should be interpreted to include, but is not limited to, solid-state memory, optical and magnetic media, or other non-transitory machine-readable media.

The processing modules/units/logic 1528, components and other features described herein may be implemented as separate hardware components or integrated into the functionality of hardware components such as ASICS, FPGAs, DSPs or similar devices. Additionally, the processing modules/units/logic 1528 may be implemented as firmware or functional circuits within a hardware device. Additionally, the processing modules/units/logic 1528 may be implemented in any combination of hardware devices and software components.

It should be noted that while system 1500 is shown with various components of a data processing system, it is not intended to represent a particular architecture or manner of interconnecting the components. Such details are not germane to the embodiments of the present disclosure. It will also be understood that network computers, handheld computers, mobile phones, servers, and/or other data processing systems having fewer components or possibly more components may also be used with embodiments of the present disclosure.

Some portions of the above detailed descriptions are presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the method used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of operations leading to a desired result. The operations are those requiring physical manipulations of physical quantities.

However, it should be noted that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels used for such quantities. As is apparent from the above discussion, unless otherwise indicated, throughout the description, discussion of terms such as those set forth in the claims below will be understood to refer to the actions and processes of a computer system, or similar electronic computing device, that transforms data represented as physical (electronic) quantities in the registers and memory of the computer system into other data similarly represented as physical quantities in the memory or registers of the computer system or other similar information storage, transmission or display devices.

Embodiments of the present disclosure also relate to apparatus for performing the operations herein. Such computer programs are stored on non-transitory computer-readable media. Machine-readable media includes any mechanism for storing information in a form readable by a machine (e.g., a computer). For example, machine-readable (e.g., computer-readable) media includes machine (e.g., computer) readable storage media (e.g., read-only memory ("ROM"), random access memory ("RAM"), magnetic disk storage media, optical storage media, flash memory devices).

The process or method depicted in the foregoing figures may be performed by processing logic that may include hardware (e.g., circuits, dedicated logic, etc.), software (e.g., embodied on a non-transitory computer-readable medium), or a combination of both. Although the process or method is described above in terms of several sequences of operations, it should be understood that some of the operations described may be performed in a different order. Additionally, some operations may be performed in parallel rather than sequentially.

The embodiments of the present disclosure have not been described with reference to any particular programming language. It will be appreciated that a wide variety of programming languages may be used to implement the teachings of the embodiments of the present disclosure described herein.

In the foregoing specification, embodiments of the present disclosure have been described with reference to certain exemplary embodiments. It will be apparent that various modifications may be made therein without departing from the broader spirit and scope of the present disclosure as set forth in the appended claims. The present specification and drawings are therefore to be regarded in an illustrative rather than a restrictive sense.

Claims (22)

1. A computer-implemented method for processing an event, comprising:
receiving event data, including passive event data, active event data, or both;
determining whether the received event data is available for a pattern of passive event data and active event data;
responsive to determining that the received event data is available for a pattern of passive event data and active event data, translating one or more constraints between the passive event data and the active event data into one or more query terms;
constructing at least one query using the one or more query terms;
using the constructed at least one query to obtain remaining passive event data related to some but not all of the active event data;
selecting one or more event definitions that match the event data and the remaining passive event data;
for each matching event definition, inputting the event definition into a template to generate a set of events, the template including a plurality of assertions, the template having the event definition as one of the assertions, each assertion including a constraint;
incrementally processing the constraints of the assertion to generate one or more solutions that are a subset of the set of events; and for each constraint and each solution,
identifying a set of target events that are actionable for the solution; and generating a new solution based on the solution and the identified set of target events to generate a set of new solutions. Obtaining the remaining passive event data includes:
obtaining a query result using the constructed at least one query;
The method of claim 1 , comprising performing constraint solving on the query results and retaining the query results as the remaining passive event data that passes through the constraint solving. The method of claim 1, wherein the one or more query terms are ambiguous terms and the at least one query is two or more queries. The method of claim 1 , further comprising executing a preceding query to obtain aggregate or function values used in the query that satisfy the constraint. 2. The method of claim 1, further comprising modifying the pattern of passive and active event data by deleting any of the passive event data associated with a previous active event from the active event data if an active event is deleted. The method of claim 1, wherein the active event data is pushed from an active data source and the passive event data is pulled from a passive data source. For each new solution and each result in the template:
determining whether all of said assertions are satisfied;
2. The method of claim 1, further comprising: in response to determining that all of the assertions are satisfied, determining whether an equivalent outcome has been previously triggered; and in response to determining that the equivalent outcome has not been previously triggered, triggering the outcome. 8. The method of claim 7, further comprising: in response to determining that at least one assertion has not been satisfied and that the equivalent outcome was previously triggered, not triggering the outcome. Triggering the result comprises:
The method of claim 7 , further comprising: creating event data from the new solution; and publishing the created event data to the new solution. Publishing the event data of the new solution includes:
generating basis data for said new solution;
For each resulting data mapping entry:
collecting source event values from the source events referenced in said data mapping entries;
performing a calculation on the source event values to generate a result; and placing the result in the new solution.
10. The method of claim 9, comprising extracting entity data from the source events and aggregating the entity data into an entity map, the entity map identifying entities referenced in the source events. Incrementally processing the constraints of the assertions includes:
ordering the previous split constraints such that each split constraint is preceded by a constraint that targets the source event of the split constraint;
The method of claim 1 , further comprising generating an event subset of the pre-split constraints in order and processing remaining non-split constraints. Generating the event subsets of the partitioning constraints in order includes:
For each pre-split constraint,
12. The method of claim 11, comprising: separating source events of the split constraint into sets having the same field value referenced by the split constraint; and processing non-split constraints derived from target events of the split constraint in order until the non-split constraint encounters the split constraint. Incrementally processing the constraints of the assertions includes:
Grouping non-split constraints into stages;
ordering said stages to form a hierarchical data structure;
placing each event into one of a plurality of partial solutions of each of said assertions having an event definition for said event, said partial solutions being included in said hierarchical data structure;
splitting the partial solutions based on a split key;
2. The method of claim 1, comprising combining partial solutions having a common partitioning key to form one or more complete solutions, and processing the combined partial solutions into a result. Incrementally processing the constraints of the assertion may include, before splitting the partial solutions based on the partition key,
Determining whether there are optional stages;
14. The method of claim 13, further comprising, in response to determining that there are optional stages, processing the optional stages, including ordering the optional stages, such that new input events are processed stage by stage before being incorporated into the partial solution received from a previous stage. Incrementally processing the constraints of the assertion includes, after separating the partial solutions based on the partition key,
determining whether the minimum multiplicity of any of said assertions is greater than one;
in response to determining that there are no assertions with a minimum multiplicity greater than one,
14. The method of claim 13, further comprising combining the partial solutions having a common partition key to form one or more complete solutions and processing the combined partial solutions into a result, and in response to determining that a minimum multiplicity of at least one assertion is greater than one, combining the partial solutions and retaining the combined partial solution until a valid or invalid solution is found. The method of claim 13, wherein the split key is formed based on one or more split fields of the partial solution. 1. A data processing system comprising:
A processor;
a memory coupled to the processor for storing instructions that, when executed by the processor, cause the processor to perform operations, the operations including:
receiving event data, including passive event data, active event data, or both;
determining whether the received event data is available for a pattern of passive event data and active event data;
responsive to determining that the received event data is available for a pattern of passive event data and active event data, translating one or more constraints between the passive event data and the active event data into one or more query terms;
constructing at least one query using the one or more query terms;
using the constructed at least one query to obtain remaining passive event data related to some but not all of the active event data;
selecting one or more event definitions that match the event data and the remaining passive event data;
for each matching event definition, inputting the event definition into a template to generate a set of events, the template including a plurality of assertions, the template having the event definition as one of the assertions, each assertion including a constraint;
incrementally processing the constraints of the assertion to generate one or more solutions that are a subset of the set of events; and for each constraint and each solution,
identifying a set of target events that are actionable for the solution; and generating a new solution based on the solution and the identified set of target events to generate a set of new solutions.
Data processing system. Obtaining the remaining passive event data includes:
obtaining a query result using the constructed at least one query;
20. The system of claim 17, further comprising: performing constraint solving on the query results; and retaining the query results as the remaining passive event data that passes through the constraint solving. The system of claim 17, wherein the one or more query terms are ambiguous terms and the at least one query is two or more queries. The operation includes:
20. The system of claim 17, further comprising executing the preceding query to obtain aggregate or function values used in the query that satisfy the constraint. The operation includes:
20. The system of claim 17, further comprising: if an active event is deleted, modifying the pattern of passive and active event data by deleting any of the passive event data associated with the previous active event from the active event data. The system of claim 17, wherein the active event data is pushed from an active data source and the passive event data is pulled from a passive data source.

Images