Processing method of data stream using border monitoring query
View Patent ↗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.
1. A method of processing data streams using a Border Monitoring Query (BMQ), comprising:
identifying a data stream, by a data stream sensor;
checking an ID of the data stream, by a central processing unit, and checking a BMQ-Index, by the central processing unit, to determine that the data stream is registered in the BMQ-Index;
assigning a new node pointer based on a new data value of the data stream, by the central processing unit;
processing new information of the data stream using the BMQ-Index, by the central processing unit, and;
updating the BMQ-Index with the new node pointer and new data value, by the central processing unit.
2. The method of claim 1 , wherein the BMQ-Index consists of a stream table, multiple region segment lists, and a query table.
3. The method of claim 1 , wherein the new node pointer is assigned by searching for a region segment node which contains the new data value of the identified data stream from the BMQ-Index.
4. The method of claim 1 , wherein processing new information of the data stream comprises:
reading a previous node pointer of the data stream and a region segment list from the BMQ-Index;
traversing from a previous node to a new node in the region segment list, and retrieving differential query sets, and;
storing the data stream, a current processing time, and the differential query sets in a database.
5. The method of claim 4 , wherein retrieving the differential query sets comprises retrieving differential query sets incrementally through a linear traversal from a region segment matching a previous data stream to a region segment matching a current data stream.
6. The method of claim 1 , wherein the BMQ-Index is a one-dimensional index consisting of a stream table and a region segment list.
7. The method of claim 6 , wherein the stream table stores an ID of each registered data stream and a node pointer which points to a region segment node where a recent data value of each data stream is located.
8. The method of claim 6 , wherein the region segment list comprises region segment nodes which have different ranges of region segments and two corresponding delta query sets.
9. The method of claim 1 , wherein the BMQ-Index is a two-dimensional BMQ-Index consisting of a stream table, two region segment lists and a query table.
10. The method of claim 9 , wherein the stream table stores, for each registered data stream, an ID of the data stream, two node pointers to a last located regions segment node and two last data values in X- and Y-dimensions.
11. The method of claim 9 , wherein the region segment lists consist of a region segment list for an X-dimension and a region segment list for a Y-dimension, the region segment list for the X-dimension consists of region segment nodes and two delta query sets, and in the region segment list for the Y-dimension consists of region segment nodes and two delta query sets.
12. The method of claim 9 , wherein the query table consists of borders of queries and query IDs which are hashed.
13. The method of claim 1 , further comprising extracting data from data stream information stored in a database and outputting the extracted data.
14. The method of claim 13 , wherein extracting the data comprises, in order to get count data for a specific query Q i ,
selecting a specific processing time window, and
extracting data streams which include the query Q i among the differential query sets.
15. The method of claim 13 , wherein the extracted data is outputted as one of inflow, outflow, net-flow and total-flow for a specific Q i during a specific time window.
16. The method of claim 13 , wherein extracting the data comprises,
in order to get temporal aggregation data for a specific query Q i ,
selecting a query Q i among stored differential query sets, extracting data streams which include the query Q i among the differential query sets, extracting the processing time which include the query Q i in QSet + 0 and the processing time which include the query Q i in QSet − for each data stream.
17. The method of claim 13 , wherein the extracted data is outputted as one of minimum, maximum, average, top-k and bottom-k for a specific Q i , involving the begin time, end time, and time interval of satisfying a range condition of Q i during a specific time window.
18. The method of claim 13 , wherein the extracted data is limited by a time window.
19. The method of claim 1 , further comprising modifying the BMQ-index with new data values.
20. A method of processing data streams using a Border Monitoring Query (BMQ), comprising:
identifying a data stream, by a data stream sensor;
checking an ID of the data stream, by a central processing unit, and checking a BMQ-Index, by the central processing unit, to determine that the data stream is not registered in the BMQ-Index;
assigning a new node pointer based on a new data value of the data stream, by the central processing unit; and
registering the new node pointer and the ID of the data stream in the BMQ-Index, by the central processing unit.
21. The method of claim 20 , wherein the node pointer is configured by reading a region segment node containing the new data value of the identified data stream in the BMQ-index.
22. The method of claim 20 , further comprising modifying the BMQ-index with new data values.
23. A method of modifying a Border Monitoring Query (BMQ)-index, comprising:
inputting a query to be changed and a corresponding query region from an input unit to a central processing unit;
assigning a region segment and delta query sets based on borders of the query to be changed, by the central processing unit;
setting up new borders of region segments (b 0 , b 1 , . . . , b m ) and corresponding new nodes (N 1 , N 2 , . . . , N m ), by the central processing unit; and
storing each node and its region and delta query sets in a database, by the central processing unit.
24. The method of claim 23 that modifies the BMQ-index for a newly registered query Q in whose range is (l in , u in ), wherein the BMQ-index:
locates the RS node, N i which contains l in , the node N i having a range (b i−1 , b i ),
inserts Q in into the +DQSet i of N i if l in is equal to b i−1 , or splits N i into two RS nodes: the left node with the range of (b i−1 , l in ) containing the ±DQSet of N i and the right node with the range of (l in , b i ) containing Q in in its +DQSet,
locates the RS node, N j which contains u in , i.e., b j−1 ≦u in <b j ,
and inserts Q in is inserted into the −DQSet i of N j , if u in is the same as b i−1 , or splits N j into the two RS nodes: the left node with the range of (b j−1 , u in ) containing the ±DQSet of N j and the right node with the range of (u in , b j ) keeping Q in in its −DQSet.
25. The method of claim 23 that modifies the BMQ-index for a deregistered query Q out whose range is (l out , u out ), wherein the BMQ-index:
locates the RS node, N i whose lower bound is equal to l out ,
removes Q out from the +DQSet i ,
merges N 1 with N i−1 if both +DQSet i and −DQSet i are empty,
locates the RS node, N j whose lower bound is u out ,
removes Q out from −DQSet j ,
and merges N j with N j−1 if both +DQSet j and −DQSet j are empty.
26. The method of claim 23 that modifies the BMQ-index, wherein all the operations of the modification are performed in each dimension for multi-dimensional cases.
27. The method of claim 23 that modifies the BMQ-index, further comprising registering or deregistering the modified query and its region into the query table of the BMQ-index, for multi-dimensional cases.