CN111771195A - Stream processing device and data stream processing method - Google Patents

Abstract

The present invention provides a stream processing device 100 having a processor 110 for processing a data stream 120 in a stream window 130. The processor 110 is used to generate a higher-order representation 140 from the contents of the stream window 130, and the processor 110 is used to process the higher-order representation 140.

Description

Stream processing device and data stream processing method

technical field

The present invention relates to a stream processing device and a data stream processing method.

Background technique

The present invention is directed to the field of big data distributed stream processing. Streams are sequences of events, i.e. tuples containing various data, generated in chronological order by various sources such as sensors, machines or humans. The stream processing paradigm involves applying analytical functions to events in a stream. A typical approach to stream processing assumes that such events are accumulated within certain bounds at a given time, and an analytical function is applied to the resulting collection. This collection of transient events is called a window.

Stream processing engines provide tools to process events on the fly (as they enter the system). In terms of data acquisition technology, stream processing engines can support data arriving in real-time from stream sources, as well as loading data pre-stored in storage media. Data is often referred to as an event, which represents an aggregation of different pieces of data that may have different logical meanings. These data are generated and received in a certain order in the system. We can consider at least three concepts of time associated with each event (or at least the concept of order in the absence of a time source): arrival time is the time at which the processing engine (or buffer queue) is notified of the event; the event Time is when the event is actually generated; processing time is when the system actually processes the event. In general, processing can be triggered at fixed time intervals (eg based on the concept of wall clock time watermarks), or by the arrival of each event. The processing logic is usually handled by a specific trigger function.

Most functions applied to data streams require a subset of the overall processed events from the stream at any given time. That is, the function is applied on a window, where a window is a delimitation about a time or logical sequence of events that contains events within a given boundary (eg, 2 hours before the current time). The contents of these windows change over time as new events arrive and old events go beyond the window boundaries and are deleted. Typically, the window and handler functions to be applied are specified to be executed on the machine. However, since the data size can grow rapidly, especially in the case of large window boundaries, there is great interest in designing an efficient method to perform pattern matching for such windows. However, windowed stream operators require significant resources to iteratively compute pattern matching verification over large windows. The window operator keeps all events in memory, and at each trigger moment, all elements are (re)iteratively processed to compute the window function, as shown in Figure 1. Notably, pattern matching computations for large windows require both keeping a large state in memory and re-iterative computations for windows containing millions of events, making it difficult to meet (approximately) real-time requirements. Therefore, big data applications cannot obtain efficient, general-purpose, low-latency, and low-computing time stream processing.

The main problem is that existing streaming technologies do not provide default solutions to achieve extremely low-latency complex event processing and pattern matching on event windows. This means that pattern matching computations for event windows can be described and executed while maintaining real-time system timing constraints. Pattern description and analysis are expensive, inefficient, and complex to express in rules or user-defined functions. However, there exist higher-order representations that are convenient for describing patterns and performing pattern matching, but at this stage they are not available on streaming engines, and they cannot meet real-time requirements because they are usually performed on warm or cold data.

Online complex event processing and pattern matching is a challenge because it may require re-iterating processing large windows that may contain millions of events and performing pattern matching while the stream is in progress. When represented in terms of available stream operators (such as User-Defined Functions (UDFs)) or rules containing long lists of statements, pattern matching computations must be performed in a sliding event window (i.e. concurrently with the stream and possibly in Shared events between consecutive instances) are recomputed. However, data-intensive applications result in windows with millions of elements, such as the number of credit card transactions in a country over the past 6 months, increasing computational overhead. This leads to performance degradation as resource and computational overhead grows linearly with the number of elements to be aggregated. Another related aspect is that complex patterns containing many statements are difficult to obtain and represent both as rules and processing statements in specially defined functions. In fact, current tools support only a small number of statements expressed as regular expressions in complex event processing (CEP) pattern matching.

The present invention overlaps with some areas of data management and processing. As discussed below, none of these techniques provides or constitutes a solution to the specific problem addressed by the present invention. Existing streaming engines and related mechanisms focus on using features that require window operators with dedicated window functions and keep all events in a window cache. Handler functions can be used for some types of functions, but need to be recalculated for different functions as the window state changes. This significantly impacts real-time constraints and resource usage when scaling to larger event sets, high-frequency streams, and long/large windows. Lack of mechanisms, stream operators or schemes to support complex events and pattern matching: (1) rely on second-order data models; (2) enable online operations on such higher-order data models; (3) operate with extremely low latency . The most representative techniques and concepts of the present invention relate to stream processing.

Streaming engines such as Spark Streaming, Flink, Storm, Samza, and Dataflow are the main streaming technologies discussed in this article. The role of the streaming engine is to process dynamic data, that is, to process data in motion. They provide computational power for stream-based temporal ordering. Depending on the specific engine, time can be further set to refer to event time, processing time, computer time, or arrival time of the event. Most streaming engines allow some form of grouping of events in a window. Depending on the application programming interface (API) of the streaming engine, there are different levels of flexibility to define and drive computations in the window. The main limitation is that window operators use user-defined functions, so they are not optimized based on function properties. Also, all windows typically keep all data within the window's extent in memory, even if the window function only uses a portion of that data.

Most streaming engines support CEP in the form of Structured Query Language (SQL) query expressions. Spark and Ignite support time series analysis in batch mode, but not in stream processing mode. The Druid system is designed for fast injection and time series analysis with high throughput and low latency, but does not handle stream processing issues and requires Extract, Transform, and Load (ETL) to correctly input data. Druid is used as a stream processing sink node for subsequent execution of queries and is therefore not part of the real-time pipeline.

Current approaches to stream processing treat pattern matching as user-defined window functions or rather simple state machines, and this approach suffers from three main limitations. The first limitation is that the target pattern description is determined by custom user implementations or regular expressions describing the sequence of event types. The second limitation is that each window function saves the entire sequence of events in a window cache (or state), which grows with the number of events contained in the window. A third limitation is that pattern matching requires that the entire data be iterated over at each trigger event. Therefore, unless the pattern is very simple, defining pattern matching can be expensive, and the computation time may not meet real-time requirements.

Typically, a set of rules is defined to model user behavior based on different aggregates (sums, counts, averages, etc.) computed over a specific time window. However, complex patterns require many complex rules to be defined and validated against analysts' interpretations of fraud schemes.

In the default approach, a large window is created to hold all historical data during global feature computation, or a subdomain of data during feature computation for certain partitions. Each feature needs its own window. Results will be computed by traversing the entire dataset and recomputing pattern matching or rule validation from scratch, resulting in slow result computation or limited validation capabilities. Additionally, small changes in pattern range or trend can lead to missed detections. The first option is to define a user-defined function that gets the schema. The function should traverse the entire window, verifying line by line the corresponding match between the current state of the window and the target pattern.

The main limitation of this approach is that it requires significant resources to describe the schema and perform its validation. Also, due to its high complexity and non-scalable, it is prone to errors because the entire logic would be embedded in a unique dedicated function. Another option is to rely on the CEP API for defining state machines. For example, element1=x FOLLOWED BY element2=y FOLLOWED BY element3=z and so on. The main limitation of this approach is that it is only used for fairly simple analyses and cannot be used for distributed models, i.e. only for single-machine state machines.

SUMMARY OF THE INVENTION

In view of the above problems and disadvantages, the present invention aims to improve distributed stream processing of big data. Therefore, the object of the present invention is to provide a stream processing device and a method for processing a data stream. The apparatus and method perform better than corresponding solutions known in the art.

The objects of the invention are achieved by the solutions provided by the attached independent claims. Advantageous implementations of the invention are further specified in the dependent claims.

The present invention proposes a new windowed processing system, which on the one hand provides a mechanism for converting the window of an incoming data stream into a second-order representation, and on the other hand, provides a mechanism for processing this data stream as the stream progresses. Mechanism for second-order representation of class windows. More specifically, there are various scenarios, such as fraud prevention, outlier detection or monitoring, where complex pattern matching processes must be performed with very low latency. Furthermore, in such scenarios, second-order representations can be used to embed statistical properties or mathematical models of events in windows, and such tools can be used to support online machine learning modules as well as predictive analytics.

According to the present invention, a new system is proposed that enables efficient and effective pattern matching and CEP in streaming windows to be able to cope with a wide range of big data scenarios. To this end, a specialized system is built for transforming event windows in second-order data models (such as time series indices) and defining a set of higher-order operators capable of performing operations based on this representation.

A first aspect of the present invention provides a stream processing device having a processor for processing a data stream in a stream window, wherein the processor is configured to generate a high-order representation from the content of the stream window, and the processor uses for processing the higher-order representation.

The present invention is based on two new operator types. First, a transformation window operator generates a second-order representation (eg, a time series), and thus implements an elevate method. Different types of representations can be generated according to different promotion logics. Second, higher-order operators are second- or third-order functions implemented as stream operators, with second-order representations as inputs and parameters. In principle, all existing first-order operator types will have corresponding implementations that are higher-order operators.

The present invention has the advantage of overcoming the complexity of iterative methods for performing pattern matching in windows (methods in the prior art) by computing pattern matching, and overcoming the complexity of other second-order functions by an efficient second-order representation complexity, thereby: (a) reducing the computational overhead of pattern matching (such as log complexity for index searches versus polynomial complexity for multiple iterations); (b) saving resources and reducing data dimensionality; (c) by applying statistical methods to reduce noise and improve accuracy.

Another advantage of the present invention is that it improves performance by reducing the complexity of pattern matching, from polynomial complexity based on the number of events in the window to logarithmic complexity (plus the constant overhead of building higher order representations). Complex event processing and pattern matching can be performed on high-dimensional and complex data without specifying fine-grained rules or complex programs to represent patterns.

Another advantage of the present invention is that it saves resources/overhead with a more efficient representation, where high dimensional data is compressed up to 1000 times. Methods can be natively applied to second-order representations to reduce dimensionality and thus the memory occupied by window representations during pattern matching.

Another advantage of the present invention is to improve accuracy by reducing noise by improving pattern matching accuracy. Statistical methods normalize or emphasize specific characteristics of the data in a window, making it adaptable to changes in window events without correcting query parameters (such as smoothing).

Another advantage of the present invention is that it has rich functions. Compared with the stream engine in the prior art, at least 2 times more operators are provided. The present invention implements a whole new set of real-time analysis procedures, and proposes a system that utilizes all existing time-series analysis and processing (eg spectral, intervention, interpretation and predictive analysis) tools.

The present invention can be applied to a large number of scenarios where pattern matching needs to be performed on large data streams. Its immediate application areas include the Internet of Things (IoT), finance, fraud detection, risk analysis, and future areas such as artificial intelligence (AI) and real-time intelligent decision-making.

The main advantage of the system of the first aspect is that it enhances the capabilities of the stream processing system for complex event processing and pattern matching, and simplifies the programming model for such analysis. In fact, the second-order representation can be optimized to improve the performance of pattern matching in large windows. The system will be burdened with the overhead of building a second-order representation, but at each iteration it will be possible to verify a match with the target schema by simply performing transformations and comparisons on this optimized data structure. For example, the second order representation can be a time series index such as SAX or ADS. This time series representation guarantees a logarithmic complexity of matching the number of execution points. In addition, they contain geometric distances between points to accommodate temporal drift in similar events.

The present invention is highly relevant to the current stream processor landscape as it solves the problem of current stream engines needing to apply an iterative method to perform pattern matching on windows of incoming events. This means that when using window operators, these operators may cache a large number of events that must be iterated over each time. On the one hand, complex pattern matching as an iterative algorithm is rather complex to represent and validate in current stream processing settings. On the other hand, as the amount of data grows over time, so does the required resource budget, which may even make computation too expensive or even infeasible compared to real-time requirements (eg, given the computational resources of an operator performing processing). Furthermore, different scenarios may require different types of pattern matching techniques, with different tolerances for different aspects of the problem. Each different scenario must be handled using a specially defined pattern matching function, which increases the cost of the analysis and the time to deploy a new analysis.

The present invention is applied to use cases that require real-time pattern matching and complex event processing (CEP) on high-dimensional data. The present invention proposes a new system to simplify complex analysis, enabling the use of time series mining techniques typical of stream processing. The present invention describes a new system based on two novel types of operators, utilizing a mechanism for online transformation of time series (windows) of events into second-order representations (e.g. mode (1)) to enable such representations ( 2) seamless stream processing.

The system of the first aspect provides a new paradigm for data flow analysis and provides a basis for directly stream processing patterns. Such operators include, for example: stream correlation detectors, outlier detectors, matching operators, filters, mapping and grouping functions.

Higher-order representations will enable existing toolkits and methods to perform pattern analysis in the context of streaming engines. An application example is online machine learning, since some time series representations contain a large number of statistics (such as autoregressive moving averages) that are also relevant to financial and trade markets.

In an implementation of the first aspect, the processor is configured to generate the higher-order representation by performing at least one of the following: a dimensionality reduction transform, such as a discrete Fourier transform, a fast Fourier transform, a fast Inverse Fourier transform, discrete wavelet transform; piecewise aggregate approximation; symbolic aggregate approximation; Bezier curve generation; shape description alphabet; singular value decomposition; autoregressive moving average; martingale difference sequence; indexing methods such as iSAX2, ADS ; hash function; piecewise sum of variance.

The higher-order representation may be of second or third order, and even higher orders are possible. The above transformations or functions are not an exhaustive list. All suitable functions can be used to generate the higher-order representation.

In another implementation of the first aspect, the processor is configured to process the higher order representation by performing at least one of the following functions: filtering based on time series correlation/matching functions and multiple filtering functions, eg, Euclidean distance and dynamic time warping; maps; flattened maps; time series clustering/matching methods, allowing for example grouping and joint implementation; higher-order grouping reduction, allowing for example to create first-order entity groupings by reducing and collapsing grouping functions ; Power spectral transforms such as Fourier transform, square root, cube root, logarithm; seasonal adjustment; trend amplification or removal; smoothing; filtering events to simplify correlations; stream joins based on time series matching; time series functions, Used to represent priors, likelihoods for time series models, supports search strategies using probabilistic procedures, and extrapolation of parametric and parametric models for regression, such as automatic Bayesian covariance discovery; feature extraction from time series to support feature derivation windows, forecast points and forecast windows and distances; synthetic measures of time series to derive descriptive features such as rolling mean, rolling maximum, rolling minimum, Bollinger Bands indicators and statistics, categories Rolling entropy of features, rolling majority of category features, rolling text statistics.

The above functions or higher-order operators are not an exhaustive list. All suitable first-order functions can be used to process the higher-order representation. The output of this higher-order operator can be used as the input of another higher-order operator, or it can be used as the input of a first-order operator based on demote methods. When higher-order representations or time series are too dense, dimensionality reduction methods, such as time series smoothing, can be applied to speed up the execution of pattern matching with minimal loss of accuracy.

In another implementation manner of the first aspect, the processor is configured to generate the high-level representation triggered by a trigger event, wherein the buffered data of the flow window is used to generate the state of the flow window at the trigger moment high-level representation of .

Such triggering events may be based on time periods, number of events in a window, and the like.

In another implementation of the first aspect, the processor is configured to return to first-order stream processing by processing the metadata and/or context of the generated high-order representation.

The processor or higher-order operator may implement a reduction-order method that, given a function output, produces a relevant output based on the metadata and/or context of the entity generating the higher-order representation. Through order reduction, results, representations, etc. can be returned from higher order to first order for further processing, evaluation, etc.

In another implementation manner of the first aspect, the processor is configured to pass the higher-order object return logic as a parameter.

Providing the logic as a parameter increases flexibility.

In another implementation of the first aspect, the processor is configured to provide an interface to retrieve and query the generated higher-order representation, and to store the higher-order representation and context related to the generation of the higher-order representation and/or metadata.

Providing such a standardized interface simplifies data transfer and function calls.

In another implementation of the first aspect, the metadata includes a description of the boundaries of the flow window and/or a description of processing for the flow window.

The metadata simplifies data processing and reduces communication bandwidth, thereby improving overall performance.

In another implementation of the first aspect, the processor is configured to dynamically update the generated high-order representation according to the state of the flow window.

Such dynamic updating increases flexibility and reduces processing requirements as the generated higher order representation can be adapted to the flow window.

In another implementation manner of the first aspect, the processor is configured to pass the type of the higher-order representation as a parameter when generating the higher-order representation.

Providing the type of the higher-order representation as a parameter increases flexibility.

In another implementation of the first aspect, the processor is configured to generate and operate a higher-order representation comprising at least one statistical model adapted to detect distribution changes, wherein the processor is configured to initiate all of the distribution changes based on the distribution changes. Updates to the statistical model described.

Such an implementation makes it easy and quick to adapt to distribution changes without having to reset.

In another implementation of the first aspect, the processor is configured to generate a higher-order representation of a second- or third-order representation. Even higher order representations are possible, but may increase the processing burden.

A second aspect of the present invention provides a method of processing a data stream in a stream window, comprising: generating a higher-order representation from the content of the stream window, and processing the higher-order representation.

The same advantages of the system of the first aspect described above also apply to the method of the second aspect. Further, the method of the second aspect may have an implementation manner corresponding to the implementation manner of the above-mentioned first aspect. Thus, the method may also achieve the advantages of these implementations.

It should be noted that all devices, elements, units and means described in this application may be implemented in software or hardware elements or any combination thereof. All steps performed by the various entities described in this application and the functions described to be performed by the various entities are intended to indicate that the various entities are adapted or used to perform the respective steps and functions.

Although in the following description of specific embodiments, specific functions or steps performed by an external entity are not reflected in the description of specific elements of that entity performing the specific steps or functions, it should be clear to those skilled in the art that these methods and functions may be implemented in implemented in respective hardware or software elements or any combination thereof.

Description of drawings

In conjunction with the accompanying drawings, the following description of specific embodiments will illustrate various aspects of the present invention described above and implementations thereof, wherein:

FIG. 1 shows an example of a high-order stream processing device according to an embodiment of the present invention.

Figure 2 shows a first example of higher order stream processing.

Figure 3 shows a second example of higher order stream processing.

Figure 4 shows a third example of higher order stream processing.

Figure 5 shows a flow diagram of higher order stream processing.

FIG. 6 shows a flowchart of a method for processing a data stream according to an embodiment of the present invention.

Detailed ways

FIG. 1 shows an example of a high-order stream processing device 100 according to an embodiment of the present invention. The stream processing device 100 includes a processor 110 for processing the data stream 120 in the stream window 130 . The processor 110 may be implemented in hardware and/or software. The processor 110 may be part of the server or may be a digital signal processor (DSP). The data stream 120 includes events or data items that then pass through the stream window 130 .

The processor 110 is used to generate or upgrade a high-order representation 140 from the content of the stream window 130 . Higher order can be second or third order, and can even include higher order. The higher order can be a second order in the form of a time series.

The processor 110 is adapted to process the higher-order representation 140 by performing at least one of the following: dimensionality reduction transforms, such as discrete Fourier transforms, fast Fourier transforms, inverse fast Fourier transforms, discrete wavelet transforms; piecewise aggregate approximation ; symbolic aggregation approximation; Bezier curve generation; shape description alphabets; singular value decomposition; autoregressive moving averages; martingale difference sequences; indexing methods such as iSAX2, ADS; hash functions;

The processor 110 is also used to process the higher-order representation 140, eg, using one or more higher-order operators. The higher-order operators may be of the same order as the higher-order representation 140 . The processor 110 is configured to process the higher-order representation 140 by performing at least one of the following functions: filtering and multiple filtering functions based on time series correlation/matching functions, eg, Euclidean distance and dynamic time warping; mapping; flattening mapping; Time series clustering/matching methods, allowing e.g. grouping and joint implementation; higher-order grouping reduction, allowing e.g. creation of first-order entity groupings by reducing and collapsing grouping functions; power spectral transforms such as Fourier transform, square root, cube root , logarithmic; seasonally adjusted; trend amplification or removal; smoothing; filtering events to simplify correlations; stream joins based on time series matching; time series functions to represent priors, likelihoods of time series models, Supports search strategies using probabilistic procedures, and extrapolation of parameters and parametric models for regression, such as automatic Bayesian covariance discovery; features extraction from time series to support feature-based derivation of windows, forecast points, and forecast windows and distances forecasting; synthetic measures of time series to derive descriptive features such as rolling mean, rolling maximum, rolling minimum, Bollinger Bands indicators and statistics, rolling entropy for categorical features, rolling majority for categorical features, rolling text statistics .

FIG. 2 shows a first example of high-order stream processing, where a data stream 120 in a stream window 130 is processed. Stream processing is performed in a device 100 according to an embodiment of the present invention, which is based on the device 100 shown in FIG. 1 .

First, events are buffered in the flow window 130 or flow window operator. Then, when the triggering event occurs, the cached event is used to generate a second-order representation 140 of the state of the window 130 at the triggering instant. The transformation logic is performed in the ascending method.

The transformation window operator 200 generates a second-order representation 140, ie, a time series, in an ascending step, and implements the ascending method. Different types of representations 140 may be generated according to different ascending logics. The second-order representation 140 provides an API to retrieve and query the generated representation, and store the time-series representation, context, and metadata related to the entity body of the promotion process. Referring to the high-level processing proposed by the present invention, the logical stage or step in which the event sequence in the window is converted into a second-order representation is called an ascending order. The second-order representation 140 may also contain some metadata and descriptions for the generated windows so that downstream operators can consistently process the generated data model. The metadata may include, for example, a description of the bounds of the upgraded window, and a description of the body of the window processing entity.

The one or more higher-order operators 210 are second- or third-order functions implemented as stream operators, with the second-order representation 140 as input and parameter. In principle, all existing first-order operator types will have corresponding implementations that are second-order operators. The high-order operator 210 acts on the second-order representation 140 and issues an output in the second-order domain.

Additionally or alternatively, the higher order operator 210 implements a reduced order method that, given the output of the function, will produce a relevant output 230 based on the metadata and context of the entity generating the second order representation. The output 230 is still in the first order domain.

Higher-order flow operator types take as input a second-order representation 140 and perform functions such as business logic on the second-order representation 140 . For a single event, it can be a third-order operator, but assuming that the second-order representation 140 is generated by an irreversible function, we can rely on second-order functions that handle complex and rich representations to implement such operators. To extend current streaming engines, the output of the high-order representation 140 may be processed according to a second-order, eg, a high-order map or filter function, or based on raw first-order processing of metadata attached to the second-order representation. The logical stage or step where the output of a higher-order operator is returned to first-order stream processing is called order reduction.

Once the second-order representation 140 is input to the higher-order flow operator 210, for example to perform some business logic according to the defined semantics, such as mapping, grouping, reduction, filtering, etc., the output of the higher-order operator can be used as another higher-order operator The input of the sub, can also be used as the input of the first-order operator based on the reduction method.

Figure 3 shows a second example of higher order stream processing. Stream processing is performed in a device 100 according to an embodiment of the present invention, which is based on the device 100 shown in FIG. 1 . Figure 3 particularly shows an example of a higher order grouping operator for grouping entities based on their behavior within a particular time frame. In the first stage, events are accumulated in windows 130a, 130b based on some key identifiers (partition streams). Then, at the trigger moment, each special window operator generates a specific second-order representation 140a, 140b, and each second-order representation is input to the higher-order grouping operator 210. The operator 210 then performs a clustering operation based on the patterns defined by the behavior of the entities in the time window under consideration, and outputs groups or clusters of second order representations 220a, 220b according to the similarity of the second order representations.

Figure 4 shows a third example of higher order stream processing employing a second order filter. Stream processing is performed in a device 100 according to an embodiment of the present invention, which is based on the device 100 shown in FIG. 1 .

The application of the system in high-order stream processing is described below. The proposed operator will be instantiated for each data partition considered and will run on limited resources. When a triggering event occurs, a second-order representation 140 is generated, and a comparison of such representations may be performed, eg, by a second-order filter operator 400 . The target pattern 410 can be represented according to a chosen second order representation model (eg SAX or ADS), then compared to some distance metrics, and filtered based on a threshold parameter. One or more target patterns 410 may be stored in memory and retrieved when needed.

The generated second order representation 140 will match the target pattern 410 once for all events contained in the window 130 at each trigger instant. When matched, the corresponding metadata/key associated with the event-related entity may be output. Many concurrent windows can generate the second-order representation 140 and filter in parallel, making the system scalable and distributed.

In addition, higher-order stream processing systems can build and operate second-order representations 140 suitable for detecting changes in distributions, such as autoregressive differential moving average (ARIMA) models, which can be used in online machine learning algorithms as well as triggering the need to update and train deployed models . Such tools are designed as stream-based processing components for sliding complex features (i.e. mathematical functions, statistics), supporting online continuous machine learning by optimizing the computation of complementary mathematical functions to feed and fine-tune the lifecycle of deployed models.

Another use case for outlier detection monitoring of large-scale cloud infrastructures for fault detection and root cause analysis is considered. Currently, batch analysis of infrastructure events is performed to extract trajectories (sequences of operations) grouped by fingerprints (a set of features that provide context for trajectory comparison), which are then analyzed and compared to personalize indications of existing problems. Trajectory (outlier detection). The outlier trajectories are then shown to the operator for further analysis. The monitoring process does not rely on any distributed framework to analyze the data, and any further operations on the trajectory should be custom implemented.

With the higher order flow operators according to the invention, the monitoring process becomes a flow process, wherein for monitoring purposes a set of time series generated by a set of trajectories can be analyzed and compared. The number of false alarms for operators can be reduced by triggering further analysis and comparison with standardized relevant metrics, such as removing trends. Furthermore, since monitoring tools can leverage distributed streaming engines, the scalability of monitoring capabilities will be managed by the data processing framework.

Figure 5 shows a flowchart or work flow diagram of higher order stream processing. The workflow of the defined system begins at step 500 . The workflow may be performed in the device 100 according to an embodiment of the present invention, which is based on the device 100 shown in FIG. 1 .

According to step 510, the continuous stream reads and accumulates data in a windowed operator when a trigger event occurs, such as when the send time is reached or when a default trigger is invoked. In step 520, event data for the flow is collected.

Next, in step 530, it is checked whether the second order representation can be incrementally constructed. Incremental builds are possible if the second-order representation is an indexed or compressed representation of the collected events. Then, in step 540, a second order representation is constructed. In step 550, metadata and keys are added for illustration.

In step 560, it is checked whether there is a triggering event. If not, flow returns to step 520 to collect event data. If so, flow continues to step 570 to check if the higher order representation is ready. If so, the process continues. If not, flow returns to step 540 to construct a second order representation.

The above description focuses on incremental construction of second-order representations. For non-incremental construction of the second-order representation, the determination at step 530 is NO, and in the presence of a triggering event, the method proceeds to step 560 and further to step 570, where it is determined that the higher-order representation is not ready. Accordingly, the method returns to step 540 to construct the second-order representation non-incremental, and the subsequent process is as described above.

With the transmission of one or more second-order representations in step 580, the step-up portion of the method is completed. Now, in step 582 is the second order representation collected by or passed to the higher order flow operator. One or more higher-order flow operators perform second- or higher-order functions, eg, related to statistics or traffic, on one or more second-order representations.

In step 586, it is determined whether high-level processing should continue. If so, flow returns to step 580 and the constructed second order representation is sent. If not, flow continues to step 588 to determine whether the output has sunk or finished. If so, flow continues to step 590 (sinking) and step 592 (end of flow).

If not, flow continues to step 594, where the order reduction method is initiated. In step 594, the key and metadata are extracted from the second order representation, as they are necessary to reduce the order back to the first order. In step 596, a first-order object such as a row or tuple is sent as the result of the order reduction method. In step 598, the first order processing is continued or completed. Flow then proceeds to step 590 (sinking) and step 592 (end of flow).

Executes an ascending method and outputs a second-order representation to a higher-order operator that performs a defined logical OR function. The higher-order operators can then be programmed to downgrade processing and switch back to first-order event processing, or to continue higher-order processing with other higher-order operators executing in the pipeline. Higher-order stream processing tasks usually end with a sinking step that outputs a full pipeline.

The ascending method of a special window operator that produces a time series representation will use the following format as input:

A list of numbers representing the notification moment when a partial result should be output as a second-order object, the default value is related to the triggering mechanism of the window operator.

A parameter that indicates whether a new second-order output stream is generated for each specified time series or only one time series needs to be created and updated. The target second-order representation must support the update mode.

A parameter indicating a specific implementation of generating a second-order representation from a time series to allow different types of transformations suitable for different types of analysis (e.g. pattern matching, statistical extraction, etc.) Existing methods implemented in , and defined and implemented according to the chosen type of operator extended using the ascending method.

For each logical window that generates a second-order representation, e.g. sliding/tumbling/scrolling/session windows can be used, the window's metadata and actual parameters will be attached as context to the second-order representation. In addition, the specific parameter pointing part of the raw records/rows/tuples accumulated in the window target analysis will also be appended to the second-order representation. In principle, the part pointed to by a particular parameter can be of type tuple, row, or standard Simple Unregular Java Object (POJO).

Efficient time series index representations exist, for example, iSAX2+ builds bit-level trees to support approximate searches, and ADS+ is the latest indexing algorithm. Currently stream operators use rows or tuples, while time series operators will use special time series objects, so a serialization mechanism must be defined to avoid POJO serialization overhead.

Higher-order operator outputs will be input to corresponding higher-order operators of application logic, for example, a second-order mapping function will transform a second-order representation object applying an appropriate function (such as smoothing), a second-order filter will be implemented based on pattern matching methods, etc. filter.

The higher-order operator results are output directly through a reduced-order method, or the second-order representation is passed to another operator as in standard data processing streaming topologies. Since second order representations will usually be associated with entities such as customers, sensors, etc. A windowed grouping key saved with the second-order temporal representation will typically be used to integrate this process with normal first-order stream processing.

FIG. 6 shows a flowchart of a method for processing a data stream according to an embodiment of the present invention. In a first step 600, the data stream 120 in the stream window 130 is processed. The processing may include, for example, caching, serving, and executing trigger events. In a second step 610, the high-order representation 140 is generated from the content of the flow window 130. The generation may be initiated by a trigger event. In a third step 620, the high-order representation 140 is processed, for example, by a high-order operator.

In an exemplary use case, consider the case of automated fraud detection, which typically attempts to obtain and verify user behavior based on some pattern (ie, fraudulent signatures). This scenario was inspired by the detection of fraud rules for credit card transaction verification. Fraud detection systems typically utilize many concurrent metrics to build complex detection systems. Typically, a set of rules is defined to model user behavior based on different aggregates (sums, counts, averages, etc.) computed over a specific time window. However, complex patterns require many complex rules to be defined and validated against analysts' interpretations of fraud schemes. Transformation to higher order reduces complexity, allowing real-time processing of large data sets or streams.

The present invention will be based on the development of a complete set of higher-order stream operators, including the adaptation of the most relevant second-order functions already available for stream processing, such as mapping, reduction, grouping, and other new algorithms that are otherwise impossible to implement son.

Each higher-order representation 140 will be classified according to the properties of the embedded function (eg, allow or disallow updates), and the developer will be responsible for creating a pipeline of second-order transformations and corresponding higher-order processing such that the chosen representation is compatible with the processing purpose.

The present invention has been described in connection with various embodiments and embodiments by way of example. However, those skilled in the art can understand and obtain other variations by practicing the claimed invention, studying the drawings, the present disclosure and the independent claims. In the claims and descriptions, the term "comprising" does not exclude other elements or steps, and "a" does not exclude a plural possibility. A single element or other unit may fulfill the functions of several entities or items recited in the claims. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

Claims (13)

1. A stream processing apparatus (100) having a processor (110) for processing a data stream (120) in a stream window (130),

the processor (110) is configured to generate a high-order representation (140) from the content of the stream window (130);

the processor (110) is configured to process the high order representation (140).

2. The stream processing apparatus (100) according to claim 1,

the processor (110) is configured to generate the higher order representation (140) by performing at least one of: discrete Fourier transform; discrete wavelet transform; segment aggregation approximation; a symbol aggregation approximation; b, generating a Bezier curve; a shape description alphabet; singular value decomposition; autoregressive moving average; an index, such as indexable symbol aggregation approximation (iSAX)2.0, Adaptive Data Sequence (ADS); a hash function; and (4) piecewise variance and sum.

3. The stream processing apparatus according to claim 1 or 2,

the processor (110) is configured to process the high order representation (140) by performing at least one of the following functions: filtering; mapping; flattening mapping; time series clustering/matching methods, allowing for example grouping and joint implementations; high-order packet reduction, allowing first-order entity packets to be created, for example, by reducing and folding packet functions; correlation/matching functions, allowing for example filtering and multiple filtering functions; power spectral transforms such as fourier transforms, square roots, cube roots, logarithms; adjusting seasonality; trend amplification or removal; smoothing; filtering the events to simplify correlation; stream connection based on time series matching.

4. The stream processing apparatus according to any one of claims 1 to 3,

the processor (110) is configured to generate the higher order representation (140) triggered by a trigger event, wherein the buffered data of the stream window (130) is configured to generate the higher order representation (140) of the state of the stream window (130) at a trigger time.

5. The stream processing apparatus according to any one of claims 1 to 4,

the processor (110) is configured to return to first order streaming processing by processing metadata and/or context of the generated higher order representation (140).

6. The stream processing apparatus according to claim 5,

the processor (110) is configured to pass high-order object return logic as a parameter.

7. The stream processing apparatus according to any one of claims 1 to 6,

the processor (110) is configured to provide an interface to retrieve and query the generated higher order representation (140) and to store the higher order representation (140) and context and/or metadata related to the generation of the higher order representation (140).

8. The stream processing apparatus according to claim 7,

the metadata includes a boundary description of the stream window (130) and/or a specification of processing for the stream window (130).

9. The stream processing apparatus according to any one of claims 1 to 8,

the processor (110) is configured to dynamically update the generated high-order representation (140) in dependence on a state of the stream window (130).

10. The stream processing apparatus according to any one of claims 1 to 9,

the processor (110) is configured to pass the type of the higher order representation (140) as a parameter when generating the higher order representation (140).

11. The stream processing apparatus according to any one of claims 1 to 10,

the processor (110) is configured to generate and operate a higher order representation (140) comprising at least one statistical model adapted to detect changes in a distribution, wherein the processor (110) is configured to initiate an update of the statistical model in dependence of the changes in the distribution.

12. The stream processing apparatus according to any one of claims 1 to 11,

the processor (110) is configured to generate a high order representation (140) in the form of a second or third order representation.

13. A method of processing a data stream (120) in a stream window (130), comprising:

generating a high-order representation (140) from the content of the stream window (130);

processing the high order representation (140).

Images