JP4452234B2 - Data stream processing method, data stream processing program, storage medium, and data stream processing apparatus - Google Patents

Description

  The present invention relates to a data stream processing method, a data stream processing program, a storage medium, and a data stream processing apparatus in stream mining technology.

  A data stream is a large amount of data flowing from a network at high speed. Stream mining is a technique for quickly finding useful information from a data stream expressed as a time series. This is not a technique for simply analyzing large-scale data stored in a database, but a technique for analyzing and monitoring an increasing flow of data in real time.

  For example, in the field of stream mining, there is a technique for detecting a pair of correlated streams from a plurality of streams. The method of Non-Patent Document 1 detects a pair of correlated streams from a plurality of streams at high speed by using discrete Fourier transform. However, many correlated streams usually have some delay, and the method of Non-Patent Document 1 cannot detect a correlated stream that has a delay (hereinafter referred to as delay correlation).

In order to detect a pair of streams with delayed correlation, it is necessary to calculate a cross-correlation function. The cross correlation function is a function often used in the field of statistics. In addition, when two time series of length n X = (x ₁ , x ₂ ,..., X _n ) and Y = (y ₁ , y ₂ ,..., Y _n ) are given, (Equation 1) is a cross-correlation function.

  FIG. 7 is a diagram illustrating an example of a cross-correlation function of two time series data. Two time series in FIG. 7A and FIG. 7B are temperature sensor data. The temperature measured every 30 seconds is shown. The two temperature sensors show a similar tendency, but there is a slight deviation. Specifically, the temperature sensor A is slightly delayed. FIG. 7C shows a cross-correlation function. The vertical axis shows the correlation value, that is, how much the two time series are correlated. The horizontal axis is the magnitude of the delay (delay time). In other words, the cross-correlation function indicates how much correlation value exists between the two time series when they are shifted.

  In FIG. 7, when the correlation is examined on the assumption that there is no delay between the two temperature sensors, the result is that there is not much correlation. There is a correlation value peak at a delay of 1300 [seconds]. In this case, it can be said that “temperature sensor A correlates with temperature sensor B with a delay of 1300 [seconds]”.

  Efficiency is demanded in a technique for detecting a pair of streams having a delayed correlation. As a factor of efficiency, for example, it is necessary to increase the speed and save memory in order to analyze a large amount of data that is increasing and to provide information to users in real time.

  What is effective for achieving efficiency is a data stream summary information (hereinafter referred to as summary information) calculation method and a query processing method using summary information. This is because the length of the original data stream becomes very long, and summary information that expresses the data stream in a compact manner is effective for speeding up and saving memory. By holding the summary information, it is possible to execute a query process for obtaining a pair of streams having a delayed correlation while discarding the original data stream.

  As a method for efficiently calculating a pair of streams having delay correlation based on summary information of a data stream, the method of Non-Patent Document 2 has been proposed. In order to obtain the delay correlation, statistical values (average, variance, inner product) of the data stream are held as summary information, and each time the data is received, the summary information is updated.

  As a method for efficiently calculating a pair of streams having a delay correlation, the method of Non-Patent Document 2 has been proposed. In the method of Non-Patent Document 2, when there is a request from a user or an application, a delay correlation is calculated from summary information, and a pair of correlated streams and a value of the delay are output. The time and amount of memory for calculating the delay correlation increases linearly in proportion to the length of the data stream. Therefore, in order to achieve speedup and memory saving, the cross-correlation function is approximated using smoothing and sampling.

In the method of Non-Patent Document 2, the delay correlation calculation time is reduced by approximation of the cross-correlation function. However, the method of Non-Patent Document 2 has a problem that when the number of streams increases, the update cost of summary information is proportional to the square of the number of streams.
Yunyue Zhu, Dennis Shasha “StatStream: Statistical Monitoring of Thousands of Data Streams in RealTime.” In Proceedings of VLDB, pp.358-369, August2002. Yasushi Sakurai, Spiros Papadimitriou, Christos Faloutsos “BRAID: Stream Mining through Group Lag Correlations” In Proceedings of ACM SIGMOD, pp.599-610, June 2005.

  However, the conventional method cannot efficiently calculate a pair of streams having a delay correlation. Here, being inefficient means that the calculation amount and the memory usage amount in the calculation are excessively wasted.

The memory usage for calculating the delay correlation is as follows. Let m be the number of data streams. At this time, when a method for calculating (Equation 1) as it is (hereinafter referred to as a naive method) is used, a memory of O (m ² ) is required. The function O indicates the order of calculation amount. This is because the naive method calculates the sum and variance of all the data streams and further calculates the inner product of all the data stream pairs and stores them in the memory as summary information. That is, an inner product is stored for each pair of data streams, and a correlation value is calculated using the inner product, so that an O (m ² ) memory is required.

In the method of Non-Patent Document 1, a pair of streams having a delay correlation cannot be calculated in the first place. In the method of Non-Patent Document 2, the amount of calculation related to the update of summary information is O (m ² ), and the efficiency is insufficient.

  Therefore, the main object of the present invention is to solve the above-described problem and to efficiently calculate a pair of streams having a delay correlation.

  In order to solve the above-mentioned problem, the present invention provides a data stream processing method for obtaining a delayed correlation between a plurality of data streams measured in time series, wherein a computer performs random projection, time Summary information calculation procedure for creating summary information based on sum of series and sum of squares of time series, storing the summary information in storage means, and updating the summary information based on update of the measurement value of the data stream, and the storage A delay correlation calculation that reads the summary information stored in the means, calculates a cross-correlation function of the data stream based on the summary information, and obtains and outputs a delay correlation between the data streams from the cross-correlation function And a procedure is executed.

  As a result, the calculation time and memory usage when updating the summary information can be reduced as compared with the prior art.

  The present invention is characterized in that the summary information calculation procedure updates the summary information based on the data stream updated at time intervals calculated by an exponential function.

  As a result, the number of samples of the data stream is reduced, so that the calculation time and the memory usage when updating the summary information can be reduced as compared with the prior art.

  The present invention is characterized in that when a pair of the data streams designated as having a correlation in advance is not detected by the delay correlation calculation procedure, it is detected as a failure.

  This makes it possible to quickly detect a failure in the data stream measurement device.

  The present invention is characterized in that a plurality of computers calculate the summary information about the data stream in charge in parallel with other computers.

  Thereby, since the calculation of the data stream is parallelized, the calculation time for updating the summary information can be reduced as compared with the prior art.

  The present invention is a data stream processing program for causing a computer to execute the data stream processing method.

  As a result, the calculation time and memory usage when updating the summary information can be reduced as compared with the prior art.

  The present invention is a computer-readable storage medium storing the data stream processing program.

  As a result, the calculation time and memory usage when updating the summary information can be reduced as compared with the prior art.

  The present invention is a data stream processing apparatus for obtaining a delay correlation between a plurality of data streams measured in time series, the random projection of the input data stream, the sum of time series, and the square of time series Summary information based on the sum is created and stored in the storage means, the summary information calculation unit that updates the summary information based on the update of the measurement value of the data stream, and the summary information stored in the storage means is read, A delay correlation calculating unit that calculates a cross-correlation function of the data stream based on the summary information, and obtains and outputs a delay correlation between the data streams from the cross-correlation function;

  As a result, the calculation time and memory usage when updating the summary information can be reduced as compared with the prior art.

  The present invention is characterized in that the summary information calculation unit updates the summary information based on the data stream updated at time intervals calculated by an exponential function.

  As a result, the number of samples of the data stream is reduced, so that the calculation time and the memory usage when updating the summary information can be reduced as compared with the prior art.

  The present invention is characterized in that when the pair of data streams designated as having a correlation in advance is not detected by the delayed correlation calculation unit, it is detected as a failure.

  This makes it possible to quickly detect a failure in the data stream measurement device.

  The present invention is characterized in that a plurality of the data stream processing devices calculate the summary information related to the data stream in charge in parallel with the other data stream processing devices.

  Thereby, since the calculation of the data stream is parallelized, the calculation time for updating the summary information can be reduced as compared with the prior art.

  According to the present invention, by reducing the update cost of summary information to O (m), it is possible to perform high-speed and memory-saving processing while detecting the delay correlation of the data stream with high accuracy. This is because the method of the present invention stores the average value, variance value, and random projection of each data stream as summary information, and the correlation value requires only O (m) memory to calculate from them. is there.

  Hereinafter, an embodiment of a data stream processing system to which the present invention is applied will be described in detail with reference to the drawings. First, the configuration of the data stream processing system of this embodiment will be described with reference to FIG.

  FIG. 1 is a configuration diagram showing a data stream processing system. The data stream processing system includes a sensor 2 that measures a data stream and a data stream processing device 1 that processes the data stream. The data stream processing device 1 is configured as a computer including at least a memory serving as storage means used when performing arithmetic processing and an arithmetic processing device that performs the arithmetic processing. The memory is composed of a RAM (Random Access Memory) or the like, and stores summary information of the data stream. Arithmetic processing is realized by an arithmetic processing unit configured by a CPU (Central Processing Unit) executing a program on a memory. The data stream processing device 1 includes a summary information calculation unit 10 and a delay correlation calculation unit 20.

  Each time the summary information calculation unit 10 receives a data stream, it calculates the summary information of each data stream and discards the original data stream. Note that the summary information in the present embodiment is calculated based on a random projection, a time-series sum, and a time-series sum of squares.

When the data stream X = (x ₁ , x ₂ ,..., X _n ) is given, the time series sum Sx and the square sum Sxx of X are respectively calculated as (Equation 2) below. . The summary information calculation unit 10 notifies the delay correlation calculation unit 20 of the calculated Sx and Sxx.

The summary information calculation unit 10 calculates not only one correlation value but also correlation values when various delays are present for each data stream pair. Therefore, the summary information calculation unit 10
A plurality of sums and variances are calculated for the data stream X as shown in (Formula 3) below, and for the data stream Y as shown in (Formula 4) below. Here, l is the magnitude of the delay.

The random projection of summary information is a technique for dimensional reduction used in computer science, and a random function is used for projection (mapping) from a time series to a space vector. Random projection is described, for example, in the literature (Dimitris Achlioptas “Database-friendly random projections.” In Proceedings of PODS, pp. 274-281, May 2001.). If the vector of the random projection of X is P _x = (p ₁ , p ₂ ,..., P _d ), the number of dimensions of Px is d, and the random function is U = (u _ti ), the i-dimensional value in Px is The following (Formula 5) is obtained.

  Here, the summary information calculation unit 10 calculates a plurality of random projections Px (l + 1, n) in the same manner as the sum and variance when the delay l is considered. The same applies to the data stream Y, and the summary information calculation unit 10 calculates Py (1, n−1).

  When receiving a query request from an application or a user, the delay correlation calculation unit 20 calculates delay correlation using the summary information of the data stream calculated by the summary information calculation unit 10. When the summary information calculation unit 10 receives a single inquiry request, the summary information calculation unit 10 checks the data stream pairs input to the data stream processing device 1 in a brute force manner and outputs a pair having a delay correlation and its delay value as a list. .

The delayed correlation calculation unit 20 calculates the cross-correlation function of the data stream pair using the summary information. First, an inner product is calculated using a random projection and a square sum of time series (Formula 6). Then, the delayed correlation calculation unit 20 calculates a cross-correlation function R (l) using the calculated inner product (Formula 7).

  FIG. 2 is a flowchart showing an outline of data stream processing.

  First, the data stream processing apparatus 1 determines whether there is a data stream update (S101). The update of the data stream indicates that new data of the data stream that has not been input to the summary information calculation unit 10 in the past is newly input to the summary information calculation unit 10. If there is no update of the data stream (S101, No), the process proceeds to S103. When there is an update of the data stream (S101, Yes), the subroutine process “summary information update process” is called (S102), and the process proceeds to S103.

  Next, the data stream processing apparatus 1 determines whether or not there is an inquiry request (S103). If there is no inquiry request (S103, No), the process returns to S101. Hereinafter, the processing when there is an inquiry request (S103, Yes) will be described.

  The data stream processing apparatus 1 calls a subroutine process “delay information calculation process” (S104), and outputs a pair having a delay correlation as a result and a delay value thereof as a list.

  Further, the data stream processing apparatus 1 may execute the delay information application process using the result calculated in S104 as an input (S105). The application process of delay information is, for example, failure detection in a sensor network. Specifically, the data stream processing apparatus 1 registers a pair of sensors 2 to be linked (that is, correlated) in advance, and if the pair of sensors 2 having a delayed correlation calculated in S104 is not detected, The possibility can be suggested.

  Another example of the delay information application process (S105) is an abnormality detection of network traffic measured by the sensor 2. For network traffic, for example, it is assumed that almost the same measurement value is expected on the same day of the week. Then, the correlation between the measured value measured last week by the same sensor 2 and the measured value measured this week is checked, and when there is no correlation, the detection of abnormality in network traffic is notified.

  FIG. 3 is a flowchart showing the “summary information update process” (S102).

First, the summary information calculation unit 10 executes a loop (S201 to S209) in which the loop variable k is added one by one from 1 to m. The summary information calculation unit 10 substitutes the kth data stream for the variable X (S202). The summary information calculation section 10, at time t, to receive _{x t} (S203). Summary information calculation unit 10, the Sx + _{x t} to Sx, and the Sxx _{+ x} ^{t 2} in Sxx, the values are (S204). Each parameter in S204 is described in (Equations 2, 3, 6, and 7).

Then, the summary information calculation unit 10 executes a loop (S205 to S208) in which the loop variable i is added one by one from 1 to d. Summary information calculation unit 10 generates a _{u ti} from a random function (S206), substitutes _p i ₊ x _{t u ti} to _{p i} (S207). Each parameter in S207 is described in (Formula 5). The processing in FIG. 3 has been described above.

Since the summary information calculation unit 10 described above requires only the calculation cost of O (m) and the memory usage, the calculation cost and the memory usage can be reduced. In the method of Non-Patent Document 2, when m data streams are handled, since Non-Patent Document 2 must calculate the inner product of all data stream pairs, O (m ² ) Computational cost and memory usage were required and inefficient.

  Here, it will be described that the calculation cost of the summary information calculation unit 10 is O (m). In FIG. 3, there are two loops. In the first loop (S201 to S209), since the upper limit value of the loop variable k is m, the calculation cost is O (m). In the second loop (S205 to S208), the upper limit value of the loop variable i is d. Here, d is the number of dimensions of the random projection vector Vx. Since the dimension number d is an attribute of one data stream, it is a parameter that does not depend on the number m of other data streams input to the summary information calculation unit 10. Therefore, since the loop from 1 to d does not affect the order of calculation amount, the total calculation cost in FIG. 3 is O (m).

  FIG. 4 is a flowchart showing the “delay information calculation process” (S104).

  First, the delay correlation calculation unit 20 executes a loop (S301 to S308) in which the loop variable k is added one by one from 1 to m. The delayed correlation calculation unit 20 substitutes the kth data stream for the variable X (S302). Then, the delay correlation calculation unit 20 executes a loop (S303 to S307) in which the loop variable j is added one by one from k to m.

  The delayed correlation calculation unit 20 substitutes the jth data stream for the variable Y (S304). The delayed correlation calculation unit 20 calculates a cross-correlation function from the X summary information (Sx, Sxx, Px) and the Y summary information (Sy, Syy, Py) (S305). The delay correlation calculation unit 20 detects delay information from the cross-correlation function calculated in S305 (S306).

The delay information detection (S306) is specifically as follows. Given time series X and Y, X and Y are defined to have a delay correlation of l when the following conditions are met: Therefore, whether or not the delay information can be detected is determined depending on whether or not the following condition is satisfied.
(1) the absolute value of the correlation value | R (l) | When the score is a local maximum score of _{x t} and _{y t-l} exceeds the threshold value gamma.
(2) When there are a plurality of maximum values, the first maximum value is indicated.

Here, in FIG. 4, the calculation cost of the delay correlation calculation unit 20 is O (m ² ). However, since the trigger for starting the processing in FIG. 4 is an inquiry request, the frequency is extremely less than the trigger for starting the processing in FIG. 3 (data stream update). Therefore, the calculation cost of the process of FIG. 4 does not have a significant influence compared to the process of FIG.

  The data stream processing apparatus 1 described above is characterized in that the summary information is updated incrementally. Incremental means that an amount or value is added to a certain data item according to a certain rule in the state of repeated operation. Since the summary information calculation unit 10 uses random projection for the summary information, the summary information can be updated incrementally. Thereby, since the original data stream may be discarded, the memory usage can be saved. Then, the delayed correlation calculation unit 20 finds a correlated data stream pair and its delay value using only each summary information that is incrementally updated without using the original data stream.

  The data stream processing device 1 may be configured by a single computer or a plurality of computers. For example, since a data stream is generated for each sensor 2, a data stream processing device 1 may be provided for each sensor 2, and the processes of FIGS. 3 and 4 may be executed in parallel. At that time, the loop (S201 to S209) in FIG. 3 and the loop (S301 to S308) in FIG. 4 are distributed to the data stream processing apparatus 1 in charge of the sensor 2. Further, the sensor 2 and the data stream processing device 1 may be accommodated in the same casing.

  The data stream processing apparatus 1 described above will be evaluated below. The evaluation is performed on two scales, that is, the accuracy of the output result and the calculation time. As will be described below, the data stream processing apparatus 1 of the present embodiment realizes a reduction in calculation time without degrading the accuracy of the output result.

  FIG. 5 shows experimental results for indicating the accuracy of the output results. The optical sensor C in FIG. 5A and the optical sensor D in FIG. 5B are sensor data of illumination, respectively. In the cross-correlation function of FIG. 5C, the dotted line is the result of calculating the cross-correlation function as it is, and is expressed as “naive method”. The solid line in FIG. 5C is the result of the approximate calculation according to this embodiment. Since these two lines trace almost the same result, it can be seen that the present embodiment approximates with very high accuracy. Note that the solution obtained by the method of Non-Patent Document 2 is an approximate solution as in the present embodiment. Therefore, sufficient accuracy can be verified by comparing the result of the present embodiment with a naive technique instead of comparing with the result of Non-Patent Document 2.

  The “*” mark on the solid line in FIG. 5C indicates the calculated value. The solid line in FIG. 5C is generated by smoothly connecting the calculated values. Here, in FIG. 5C, the calculated value becomes denser as it goes to the left of the horizontal axis and becomes coarser as it goes to the right. This is because the sampling interval of the data stream is not constant and is based on an exponential function. For example, sampling is performed at time t = 1, 2, 4, 8, 16,. As a result, the number of calculated values can be reduced without greatly reducing the accuracy of the calculated values, so that the amount of calculation can be appropriately reduced.

  FIG. 6 compares the calculation time of the naive method and the method of the present embodiment. Pay attention to the calculation time on the vertical axis with respect to the increase in the number of data streams shown on the horizontal axis. The naive method increases the calculation time exponentially, whereas the method of the present embodiment is not affected by the increase in the number of data streams, and requires a substantially constant calculation time. Thereby, it can be seen that the method of the present embodiment achieves a significant reduction in calculation cost.

It is a block diagram which shows the data stream processing apparatus regarding one Embodiment of this invention. It is a flowchart which shows the outline | summary of the data stream process regarding one Embodiment of this invention. It is a flowchart which shows the calculation procedure of the summary information regarding one Embodiment of this invention. It is a flowchart which shows the calculation procedure of the delay correlation regarding one Embodiment of this invention. It is a graph which shows the experimental result of the precision of the delay correlation regarding one Embodiment of this invention. It is a graph which shows the experimental result of the calculation time for calculating the delay correlation regarding one Embodiment of this invention. It is a graph which shows the example of a delay correlation in the prior art regarding one Embodiment of this invention.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Data stream processing apparatus 2 Sensor 10 Summary information calculation part 20 Delay correlation calculation part

Claims (10)

A data stream processing method for obtaining a delayed correlation between a plurality of data streams measured in time series,
Computer
Summarization information based on random projection of the input data stream, sum of time series, and sum of squares of time series is created and stored in storage means, and the summary information is based on the update of the measurement value of the data stream The summary information calculation procedure to update
A delay that reads the summary information stored in the storage means, calculates a cross-correlation function of the data stream based on the summary information, and obtains and outputs a delayed correlation between the data streams from the cross-correlation function Correlation calculation procedure;
The data stream processing method characterized by performing.   2. The data stream processing method according to claim 1, wherein the summary information calculation procedure updates the summary information based on the data stream updated at a time interval calculated by an exponential function.   3. The data stream according to claim 1, wherein when the pair of data streams designated as correlated in advance is not detected by the delayed correlation calculation procedure, a computer detects the pair as a failure. Processing method.   The data stream processing method according to any one of claims 1 to 3, wherein a plurality of computers calculate the summary information related to the data stream in charge in parallel with other computers.   A data stream processing program for causing a computer to execute the data stream processing method according to any one of claims 1 to 4.   A computer-readable storage medium storing the data stream processing program according to claim 5. A data stream processing apparatus for obtaining a delay correlation between a plurality of data streams measured in time series,
Summarization information based on random projection of the input data stream, sum of time series, and sum of squares of time series is created and stored in storage means, and the summary information is based on the update of the measurement value of the data stream A summary information calculator for updating
A delay that reads the summary information stored in the storage means, calculates a cross-correlation function of the data stream based on the summary information, and obtains and outputs a delayed correlation between the data streams from the cross-correlation function A correlation calculator;
A data stream processing apparatus comprising:   8. The data stream processing apparatus according to claim 7, wherein the summary information calculation unit updates the summary information based on the data stream updated at time intervals calculated by an exponential function.   9. The data stream processing apparatus according to claim 7, wherein when the pair of data streams designated as having a correlation in advance is not detected by the delayed correlation calculation unit, it is detected as a failure.   10. The data stream processing apparatus according to claim 7, wherein a plurality of the data stream processing devices calculate the summary information regarding the data stream in charge in parallel with the other data stream processing devices. 2. A data stream processing device according to 1.

Images