CN105930494A - Multimode matching model based complex event detection method - Google Patents

Abstract

The invention discloses a multimode matching model based complex event detection method. A plurality of complex event detection modes are fused to construct a finite state automata, so that the storage and search of numerous redundant automata states and transfer boundaries are greatly reduced, the repeated data operation matching and computing operations are avoided, the detection and matching of the complex event detection modes can be finished by scanning data streams once, and the efficiency of detecting complex events in the massive data streams is improved. According to the method, the shared detection of the complex events in the massive data streams is realized, a current automata-based complex event mode detection method is improved, and an existing complex event detection technology is extended for finishing detection of the complex events in the massive data streams more efficiently.

Description

A Complex Event Detection Method Based on Multi-pattern Matching Model

technical field

The present invention relates to the technical field of massive data stream processing, and more specifically, to a complex event detection method based on a multi-pattern matching model in massive data stream processing.

Background technique

The Internet of Things technology integrates electronic information technologies such as network, embedded, RFID, sensors and actuators with traditional production technologies to realize data perception, transmission, calculation, control and services covering the whole process of product design, production and service. It is an important means to increase the added value of product technology, enhance the management and control capabilities of production and service processes, and give birth to a new modern production model.

In the production environment, with the increasing scale of production and the increasing complexity of the production process, the spatiotemporal distribution of the production process and the multi-source interference of the production environment have led to the deployment of a large number of sensing devices such as RFID tags and sensor nodes in the production environment. On-site monitoring of on-site conditions generates a variety of massive production data streams. Due to the existence of these massive production data streams: 1) The amount of data is huge and massive, reaching TB or even PB levels per second; 2) The data content has multiple sources, including people, materials, equipment, production processes, products, 3) The data structure is complex, structured data, semi-structured data and unstructured data coexist; 4) The data update speed is fast, and the data is generated and updated every minute and every second; 5) The data Response requirements are high, and data needs to be processed in real time and quickly to respond to other data characteristics, resulting in the processing of massive data streams in the Internet of Things: the important problem that massive multi-source dynamic data streams are difficult to process in a timely manner. Since the existing data processing methods are difficult to fully support the real-time and efficient processing of the massive data streams of the Internet of Things, it is difficult to quickly find the required information from the massive data streams and respond in a timely manner, thus affecting the scheduling and decision-making of production enterprises. Because the complex event detection technology can use the association between event attributes, continuously filter the massive production data stream arriving continuously through matching rules or algebraic operations, and quickly find out the event sequence that the enterprise needs that meets a certain association constraint, it has become popular in recent years. It has received increasing attention in various production industries.

At present, the research on complex event detection methods in data streams mainly includes automata-based, Petri net-based, matching tree-based and directed graph-based complex event detection methods and some of their improved methods, such as time-based Petri Network complex event detection method, tree complex event detection method based on compressed composition, complex event detection method based on improved graph, complex event detection method based on pushdown automata structure, complex event detection method based on matching tree model matching result sharing and other methods. However, because the above-mentioned existing detection methods can only detect and query a single complex event in a data stream in isolation, they cannot implement shared detection of multiple complex event queries in a data stream. In real life, we usually face the problem of querying and detecting multiple complex events on a data stream. If the above detection method is directly used to detect multiple complex events in the data stream, there will be a large number of redundant automaton states and transition edges, and a large amount of data will be repeatedly stored, searched and calculated, resulting in long detection time and consumption. The problem of large memory and low detection efficiency makes it difficult to realize the real-time detection function of multi-mode events in massive data streams.

Contents of the invention

The present invention aims at the problems of long detection time, large memory consumption and low detection efficiency when the current complex event detection method realizes the detection of multiple complex events on the data stream. The present invention faces massive data streams and proposes a multi-pattern matching model The complex event detection method, the method of the invention improves the conventional automatic machine (NFA) sequence scanning and sequence process, expands the existing complex event detection technology, and greatly improves the complex event detection ability in massive data streams.

In order to solve the problems of the technologies described above, the technical solution of the present invention is as follows:

A complex event detection method based on a multi-pattern matching model, comprising the following steps:

S1: Construct a multi-mode finite state automaton matching model, which is realized through the following small steps:

S1.1: Read each single-mode event matching expression;

S1.2: Construct the corresponding single-mode finite state automata matching models according to the read single-mode event matching expressions;

S1.3: Construct a state transition function according to the constructed single-mode finite state automaton matching model, and the function of the state transition function is to realize the state transition path of the finite automaton;

S1.4: Build a failure transition function based on the execution of the constructed transition function. The function of the failure transition function is to point to the next state to continue the comparison when a mismatch occurs;

S1.5: Build an output transfer function based on the constructed transfer function and the execution of the failure letter. The output transfer function (output) is used to output or record a match success message when a certain pattern string is matched, and continue to the next state Compare;

S1.6: Output the multi-mode finite state automaton matching model;

S2: Multi-mode finite state automaton matching model matching, specifically through the following small steps:

S2.1: Read the detection data one by one from the data stream;

S2.2: Determine the multi-mode state transfer direction according to the read detection data;

S2.3: Determine whether to execute the multi-mode failover function according to the state transition path;

S2.4: Determine whether to execute the multi-mode matching output function according to the multi-mode state transition direction or the multi-mode matching failure transfer function;

S2.5: Judging whether the detection task is completed, if it is completed, jump to S2.6 for execution; otherwise, jump to S2.1 for execution;

S2.6: output the detection result.

Further, in step S2.2, the detection data is an atomic event.

In step S1, it is first necessary to construct a corresponding single-mode finite state automaton matching model according to the single-mode matching expression; then use the construction of the corresponding single-mode finite state function and output transfer function; finally, using the above three transfer functions to cooperate with each other, the single-mode matching model is fused into a fusion multi-mode matching model;

In step S2, it is first necessary to use the above-mentioned multi-mode finite state automaton matching model to read in atomic events one by one from the massive data stream, and use the state transition function and failure transition function to perform state transition and matching; finally use the output transition function to output Comparing the matching results each time, and finally completing the multi-mode event matching of massive data streams;

Compared with the prior art, the beneficial effect of the technical solution of the present invention is: the present invention discloses a complex event detection method based on a multi-pattern matching model, which fuses multiple complex event detection patterns into a finite state automaton, greatly reducing Many redundant automaton states and transition side storage and lookup avoid repeated data operation matching and calculation operations, and realize the detection and matching of multiple complex event detection modes by scanning the data stream once, which improves the complexity of complex events on the data stream. detection efficiency. This method realizes the shared detection of multiple complex events in the massive data stream of the Internet of Things, improves the current complex event pattern detection method based on automaton, and expands the existing complex event detection technology, so that it can more efficiently detect massive data. detection of multiple complex events.

Description of drawings

Fig. 1 is a diagram of the construction process of the multi-pattern matching model proposed by the method of the present invention.

Figure 2 is a diagram of the NFA model whose detection mode expression is SEQ(A, B, C, D).

Fig. 3 is a diagram of the NFA model whose detection mode expression is SEQ(A, F, E).

Figure 4 is a diagram of the NFA model whose detection mode expression is SEQ(M, E, C, A).

Fig. 5 is a multi-pattern matching model proposed by the method of the present invention.

Fig. 6 is a complex event detection process of multi-pattern matching proposed by the method of the present invention.

Fig. 7 is a schematic diagram comparing detection time between the present invention and the single-mode detection method.

Fig. 8 is a schematic diagram comparing memory consumption between the present invention and the single-mode detection method

FIG. 9 is a schematic diagram of the comparison between the present invention and the single-mode detection method in terms of throughput.

detailed description

The accompanying drawings are for illustrative purposes only, and should not be construed as limiting the patent; the technical solutions of the present invention will be further described below in conjunction with the accompanying drawings and embodiments.

Example 1

A complex event detection method based on a multi-pattern matching model, comprising the following steps:

S1: Construct a multi-mode finite state automaton matching model, which is realized through the following small steps:

S1.1: Read each single-mode event matching expression;

S1.2: Construct the corresponding single-mode finite state automata matching models according to the read single-mode event matching expressions;

S1.3: Construct a transition function according to the constructed single-mode finite state automata matching model, and the function of the transition function is to realize the state transition path of the finite automaton;

S1.4: Construct a failure function according to the execution of the constructed transition function. The function of the failure function is to point to the next state to continue the comparison when a mismatch occurs;

S1.5: Construct an output function according to the execution status of the constructed state transition function and failure transition function. The output function is used to output or record a matching success message when a certain pattern string is matched;

S1.6: Output the multi-mode finite state automaton matching model;

S2: Multi-mode finite state automaton matching model matching, specifically through the following small steps:

S2.1: Read the detection data one by one from the data stream, and the detection data is an atomic event;

S2.2: Determine the multi-mode state transfer direction according to the read detection data;

S2.3: Determine whether to execute the multi-mode failover function according to the state transition path;

S2.4: Determine whether to execute the multi-mode output transition function according to the multi-mode state transition direction or the multi-mode failure transition function;

S2.5: Judging whether the detection task is completed, if it is completed, jump to S2.6 for execution; otherwise, jump to S2.1 for execution;

S2.6: output the detection result.

This embodiment describes in detail the specific detection process of a complex event detection method based on a multi-pattern matching model. In this example, the data generator module is used to simulate and generate massive data streams from various production industries. By controlling the parameters of the data generator module to generate the specification of the event type, the probability distribution of the event flow, etc., the requirements of the experiment can be realized. The experimental tool of the present embodiment is: Visual C++ 6.0, and the test index is: detection time, three aspects of memory consumption and throughput, and the experimental comparison method is: single pattern detection (Singpattern detection) method, promptly uses existing automaton-based Structural complex event detection methods implement complex event detection expressions respectively. The detection expressions are SEQ(A,B,C,D), SEQ(A,F,E) and SEQ(M,E,C,A), respectively. This example takes the detection of the above three detection expressions as an example to illustrate the specific application process of the complex event detection method based on the multi-pattern matching model proposed in the present invention.

Fig. 1 is a diagram of the construction process of the multi-pattern matching model proposed by the method of the present invention. It mainly includes five major functions: reading a single model matching expression, building a single model matching model, creating a multi-mode state transition function, creating a multi-mode failure transition function, creating a multi-mode output transfer function and multi-mode matching model output. The main function it realizes is to fuse multiple single-mode event matching models into a multi-mode event matching model, so as to realize the sharing among multiple mode detection expression strings and eliminate many redundant automaton states between them and transfer sides. Figure 2 is the NFA model diagram generated by the detection pattern expression as SEQ (A, B, C, D); Fig. 3 is the NFA model diagram generated by the detection pattern expression as SEQ (A, F, E); Fig. 4 is the NFA model graph generated by the detection pattern expression as SEQ(M, E, C, A). Fig. 5 is the multi-pattern matching model of the method of the present invention, and it is expressed as SEQ (A, B, C, D), SEQ (A, F, E) and SEQ (M, E, C, A) by detection mode expression built together.

The multi-mode matching complex event detection process proposed by the method of the present invention is shown in Figure 6, which mainly includes: reading data from the data stream one by one, multi-mode state transition, multi-mode failure transition, multi-mode output transition and multi-mode The matching results output part of the function. Its main function is to use the newly fused multi-mode event matching model to detect complex events in the data stream and output the detection results.

Fig. 7 is a schematic diagram comparing detection time between the present invention and the single-mode detection method. It can be seen from FIG. 7 that under the same test conditions, compared with the single-mode detection method, the method of the present invention can greatly increase the detection time and improve the event detection efficiency. The main reason for the analysis is that the method of the present invention eliminates the redundant automaton states and transition edges that cannot be shared in many single-mode detection methods, reduces the storage, search and calculation operations of many repeated data, and thus saves a lot of detection time .

FIG. 8 is a schematic diagram of comparing memory usage and consumption between the present invention and the existing single-mode detection method. It can be seen from FIG. 8 that under the same test conditions, the method of the present invention is superior to the single-mode detection method in terms of memory usage and consumption. The main reason for the analysis is that under the same test conditions, the method of the present invention uses a multi-mode event model to detect related events in massive data streams, eliminating redundant automaton states and transition edges in many single-mode detection methods. It reduces the storage, lookup and calculation operations of many duplicate data, thus saving a lot of memory usage consumption.

FIG. 9 is a schematic diagram comparing the event throughput between the present invention and the existing single-mode detection method. It can be seen from FIG. 9 that under the same test conditions, the method of the present invention is also superior to the single-mode detection method in terms of event throughput. The main reason for the analysis lies in the use of the multi-mode event matching model in the present invention. In this invention, we use the multi-mode event model to find related events, realize fast search, calculation and matching operations of related events in the data stream, and reduce many redundant automaton states and transition edge search and calculation in the single-mode detection method , reducing the repeated matching and calculation operations of many data, thereby improving the processing speed of system events.

Apparently, the above-mentioned embodiments of the present invention are only examples for clearly illustrating the present invention, rather than limiting the implementation of the present invention. For those of ordinary skill in the art, other changes or changes in different forms can be made on the basis of the above description. It is not necessary and impossible to exhaustively list all the implementation manners here. All modifications, equivalent replacements and improvements made within the spirit and principles of the present invention shall be included within the protection scope of the claims of the present invention.

Claims (2)

1. a complex events detecting methods based on multi-mode matching model, it is characterised in that said method comprising the steps of:

S1: build multi-mode finite-state automata Matching Model, realizes especially by following little step:

S1.1: read each monotype event matches expression formula；

S1.2: build each self-corresponding monotype finite-state automata Matching Model according to each monotype event matches expression formula read；

S1.3: building transfer function according to the monotype finite-state automata Matching Model built, the function of transfer function is to realize the state transition path of finite automata；

S1.4: build unsuccessfully function according to the transfer function implementation status built, the function of failure function is to realize, for when there is mismatch, pointing to next state to continue to compare；

S1.5: build output function according to the transfer function built and failure letter implementation status, output function for when certain pattern string obtains coupling, exports or records one the match is successful information；

S1.6: output multi-mode finite-state automata Matching Model；

S2: multi-mode finite-state automata Matching Model is mated, and realizes especially by following little step:

S2.1: read in detection data one by one from data stream；

S2.2: the detection data according to reading determine multi-mode state shift direction；

S2.3: determine whether to perform multi-mode matching failure forwarding function according to state transition path；

S2.4: determine whether to perform multi-mode matching output function according to multi-mode state shift direction or multi-mode matching failure forwarding function；

S2.5: judge whether Detection task completes, if completing, jumping to S2.6 and performing；Otherwise jump to S2.1 perform；

S2.6: output detections result.

Complex events detecting methods based on multi-mode matching model the most according to claim 1, it is characterised in that in step S2.2, described detection data are atomic event.