# US 2008/0288441 A1 · Processing method of data stream using Border Monitoring Query

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0288441 A1
- Document ID: US20080288441A1
- Status: Published application
- Kind: A1
- Application number: 11/741,923
- Filed: 2007-04-30
- Published: 2008-11-20
- Earliest claimed: 2006-05-08
- Assignees: Korea Advanced Institute of Science and Technology
- Inventors: JIN WON LEE; YOUNG KI LEE; SEUNG WOO KANG; SANG JEONG LEE; HYUN JU JIN; BYUNG JIP KIM; JUNE HWA SONG
- Web page: https://patentgrep.com/patent/US20080288441A1

## CPC

- G06F 16/334: Query execution (filtering based on additional data G06F16/335)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present invention relates to a processing method of data stream using Border Monitoring Query, and more particularly a monitoring method and a system for data streams which are a large volume of data and continuously generated such as financial ticker, GPS data or a ubiquitous sensor network (USN). The objectives of the present invention are to process a large number of BMQs over data streams in high-performance and scalable manner. For this purpose, the invention presents BMQ-Index, a scalable and high performance data stream monitoring framework. The main idea of BMQ-Index is shared and incremental processing. For shared processing, BMQ-Index adopts a query indexing approach, thereby achieving a high level of scalability. Once BMQ-Index is built on registered queries, only relevant queries are quickly searched for upon an incoming data. For incremental processing, BMQ-Index employs an incremental access method, i.e., an index structure to store delta query information and an incremental search algorithm. Thus, successive BMQ evaluations are greatly accelerated.

## Claims

### Claim 1

In a system including the central processing unit, the database storing the BMQ-Index, the data stream sensor, a method which processes data streams using Border Monitoring Query, comprising;
Step 1 identifying a data stream in the sensor;
Step 2 checking an ID of the data stream in the central processing unit, testing whether the data stream is registered in the BMQ-Index or not, and identifying that it is registered;
Step 3 assigning a new node pointer based on the new data value for the data stream in the central processing unit;
Step 4 processing the new information for the data stream using the BMQ-Index in the central processing unit, and;
Step 5 updating the previous BMQ-Index for the data stream with the new node pointer and new data value in the central processing unit.

### Claim 2 (depends on 1)

The method of claim 1, wherein the BMQ-Index consists of a Stream Table and a RS (Region Segment) list.

### Claim 3 (depends on 1)

The method of claim 1, wherein the BMQ-Index consists of a Stream Table and multiple RS lists and a Query Table.

### Claim 4 (depends on 1)

The method of claim 1, wherein the data stream has a unique ID to identify each data stream so that the system can process multiple data streams.

### Claim 5 (depends on 1)

The method of claim 1, wherein the database turns locations of points in a region which the system handles into coordinates and stores the coordinates.

### Claim 6 (depends on 1)

The method of claim 1, the step 3, wherein the new node pointer is assigned by searching for a RS node which contains the new data value of the identified data stream from the BMQ-Index.

### Claim 7 (depends on 1)

The method of claim 1, the step 4 comprising,
reading the previous node pointer of the data stream and a RS list from the BMQ-Index;
traversing from the previous node to the new node in the RS list, and retrieving differential query sets, and;
storing the data stream, the current processing time, and the differential query sets into a database.

### Claim 8 (depends on 1)

The method of claim 1, wherein the BMQ-Index is one-dimensional index consisting of a Stream Table and a RS list.

### Claim 9 (depends on 8)

The method of claim 8, wherein the Stream Table has an ID of each registered data stream and a node pointer which points to the RS node where the recent data value of each data stream is located.

### Claim 10 (depends on 8)

The method of claim 8, wherein the RS list comprises RS nodes which have different ranges of region segments and the corresponding two delta query sets.

### Claim 11 (depends on 7)

The method of claim 7, wherein retrieving differential query sets for one-dimensional BMQ-Index is to retrieve the differential query sets incrementally through a linear traversal from the region segment matched to the previous data stream to the region segment matched to the current data stream.

### Claim 12 (depends on 11)

The method of claim 11, wherein a differential query set is incrementally retrieved as follows.
Given two consecutive data values, vt−1 and vt, let vt−1 fall in the range of an RS node Nj and vt fall in that of Nh, i.e., bj−1≦vt−1<bj and bh−1≦vt<bh. If j<h, QSet+ has all queries in the union of +DQSeti excluding the queries in the union of −DQSeti where i takes the values from j+1 to h. Similarly, QSet− is calculated by subtracting the union of +DQSeti from the union of −DQSeti. On the other hand, if j>h, +DQSeti and −DQSeti are switched while i takes the values from j to h+1. There is no differential query if j=h.

### Claim 13 (depends on 1)

The method of claim 1, wherein a two-dimensional BMQ-Index consists of a stream table, two RS(Region Segment)-lists and a query table.

### Claim 14 (depends on 13)

The method of claim 13, wherein a stream table consists of the ID of data stream, two node pointers to the last located RS node and two last data values in X- and Y-dimension.

### Claim 15 (depends on 13)

The method of claim 13, wherein a RS-list in X-dimension consists of region segment nodes and two delta query sets, and a RS-list in Y-dimension consists of region segment nodes and two delta query sets.

### Claim 16 (depends on 13)

The method of claim 13, wherein a query table consists of the borders of queries and query IDs which are hashed.

### Claim 17 (depends on 7)

The method of claim 7, wherein a differential query set is retrieved in a two-dimensional BMQ-Index as follows.
The first step is to calculate differential query sets for each dimension: ±XQSet and ±YQSet. This is simply done by applying one-dimensional incremental search algorithm on the RS-X list and RS-Y list.
The second step is a cross-check, which validate if all the borders of queries in ±XQSet and ±YQSet are indeed crossed by the data value. Through the cross-check, the verified result BMQ sets, ±XBMQSet and ±YBMQSet, are obtained.
The final step, the final results are calculated as a union of ±XBMQSet and ±YBMQSet.

### Claim 18 (depends on 17)

The method of claim 17, wherein a differential query set is incrementally retrieved per dimension as follows.
Given two consecutive data values, vt−1 and vt in X-dimension. let vt−1 fall in the range of an RS node Nj and vt fall in that of Nh, i.e., bj−1≦vt−1<bj and bh−1≦vt<bh. If j<h, +XQSet has all queries in the union of +DQSeti excluding the queries in the union of −DQSeti in X-dimension where i takes the values from j+1 to h. Similarly, −XQSet is calculated by subtracting the union of +DQSeti from the union of −DQSeti in X-dimension. On the other hand, if j>h, +DQSeti and −DQSeti are switched in X-dimension while i takes the values from j to h+1. There is no differential query if j=h. ±YQSet in Y-dimension is also calculated similarly.

### Claim 19 (depends on 17)

The method of claim 17, wherein a cross-check is done as follows.
At first, central processing unit reads and identifies the current and previous data values stored in the BMQ-index.
At next, for a query in +XQSet, it is checked if a newly arrived data value is located between the Y-dimension borders of the query. The verified result is included as +XBMQSet. On the other hand, for a query in −XQSet, it is checked if the previous value of the stream was located between the Y-dimension borders. The verified result is included as −XBMQSet.
For Y-dimension, similar processing is performed.

### Claim 20 (depends on 17)

The method of claim 17, wherein the final results are calculated as follows.
QSet+ is union of +XBMQSet and +YBMQSet. QSet− is union of −XBMQSet and −YBMQSet.

### Claim 21 (depends on 1)

The method of claim 1, wherein the system contains output unit. The central processing unit extract data from data stream information stored in a database. Also, the central processing unit outputs the extracted data through the output unit.

### Claim 22 (depends on 21)

The method of claim 21, wherein extracting data comprises,
in order to get count data for a specific query Qi,
selecting a specific processing time window, extracting data streams which include the query Qi among the differential query sets, i.e., the number of data streams which include the query Qi in QSet+ and the number of data streams which include the query Qi in QSet−.

### Claim 23 (depends on 21)

The method of claim 21, wherein output result for output unit comprises,
one of inflow, outflow, net-flow and total-flow for a specific Qi during a specific time window.

### Claim 24 (depends on 21)

The method of claim 21, wherein extracting data comprises,
in order to get temporal aggregation data for a specific query Qi,
selecting a query Qi among the stored differential query sets, extracting data streams which include the query Qi among the differential query sets, extracting the processing time which include the query Qi in QSet+ and the processing time which include the query Qi in QSet− for each data stream.

### Claim 25 (depends on 21)

The method of claim 21, wherein output result for output unit comprises,
one of minimum, maximum, average, top-k and bottom-k for a specific Qi, involving the begin time, end time, and time interval of satisfying a range condition of Qi during a specific time window.

### Claim 26 (depends on 21)

The method of claim 21, wherein the size of BMQ results is limited by a window and then aggregated on them.

### Claim 27

In a system including the central processing unit, the database storing the BMQ-Index, the data stream sensor, a method which processes data streams using Border Monitoring Query, comprising;
Step 1 identifying a data stream in the sensor;
Step 2 checking an ID of the data stream in the central processing unit, testing whether the data stream is registered in the BMQ-Index or not, and identifying that it is not registered;
Step 3 assigning a new node pointer based on the new data value for the data stream in the central processing unit;
Step 4 registering the new node pointer and the ID of the data stream to the BMQ-Index in the central processing unit.

### Claim 28 (depends on 27)

The method of claim 27, wherein the node pointer of the step 3 is configured by reading the region segment node containing the new data value of the identified data stream in the BMQ-index.

### Claim 29

In a system containing a central processing unit, a input unit for the central processing unit, and a database storing a BMQ-index, a method of modifying the BMQ-index, comprising:
The step inputting a query to be changed and the corresponding query region from the input unit to the central processing unit;
The step assigning a region segment and delta query sets based on borders of query to be changed in the central processing unit;
The step setting up new borders of region segments (b0, b1, . . . , bm) and the corresponding new nodes (N1, N2, . . . , Nm) in the central processing unit; and
The step storing each RS node and its region and delta query sets into the database in the central processing unit.

### Claim 30 (depends on 29)

The method of claim 29 that modifies the BMQ-index for a newly registered query Qin whose range is (lin, uin), wherein the BMQ-idex:
locates the RS node, Ni which contains lin, i.e., bi−1≦lin<bi,
inserts Qin into the +DQSeti of Ni if lin is equal to bi−1, or splits Ni into two RS nodes: the left node with the range of (bi−1, lin) containing the ±DQSet of Ni and the right node with the range of (lin, bi) containing Qin in its +DQSet,
locates the RS node, Nj which contains uin, i.e., bj−1≦uin<bj,
and inserts Qin is inserted into the −DQSetj of Nj, if uin is the same as bj−1, or splits Nj into the two RS nodes: the left node with the range of (bj−1, uin) containing the ±DQSet of Nj and the right node with the range of (uin, bj) keeping Qin in its −DQSet.

### Claim 31 (depends on 29)

The method of claim 29 that modifies the BMQ-index for a deregistered query Qout whose range is (lout, uout), wherein the BMQ-index:
locates the RS node, Ni whose lower bound is equal to lout,
removes Qout from the +DQSeti,
merges Ni with Ni−1 if both +DQSeti and −DQSeti are empty,
locates the RS node, Nj whose lower bound is uout,
removes Qout from −DQSetj,
and merges Nj with Nj−1 if both +DQSetj and −DQSetj are empty.

### Claim 32 (depends on 29)

The method of claim 29 that modifies the BMQ-index, wherein all the operations of the modification are performed in each dimension for multi-dimensional cases.

### Claim 33 (depends on 29)

The method of claim 29 that modifies the BMQ-index, wherein the system contains the additional step for registering or deregistering the modified query and its region into the query table of the BMQ-index, for multi-dimensional cases.

### Claim 34 (depends on 1)

The method of claim 1, wherein the system contains the additional step for registering or deregistering the modified query into the region segment lists of the BMQ-index.

### Claim 35 (depends on 1)

The method of claim 1, wherein the system modifies the original BMQ-index with new data values in the previous step 5.

### Claim 36 (depends on 27)

The method of claim 27, wherein the system modifies the original BMQ-index with new data values in the previous step 4.
