System and method for monitoring events against continual range queries

• US 20050071321A1
• Filed: 09/29/2003
• Published: 03/31/2005
• Est. Priority Date: 09/29/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Kun-Lung, Yu, Philip Shi-Lung, Chen, Shyh-Kwei
• Granted Patent: US 8,972,380 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries

Abstract

A method (and structure) for monitoring continual range queries against events includes decomposing each range query with one or more predefined virtual constructs, building a query index, and using the query index to match an event with the range queries.

Claims

1. A method for monitoring continual range queries against events, said method comprising:

decomposing each range query into one or more predefined virtual constructs;

building a query index; and

using said query index to match an event with said range queries.

2. The method of claim 1, said building of a query index further comprising:

storing an identification of said query with identification lists associated with said virtual constructs.

3. The method of claim 1, said building of a query index further comprising:

predefining a set of virtual constructs for each point being monitored.

4. The method of claim 1, said matching of an event with said range queries further comprising:

finding all the virtual constructs that cover said event.

5. The method of claim 1, said decomposing of a range query further comprising:

initializing a working rectangle to be said range query;

repeatedly cutting a strip rectangle from said working rectangle; and

decomposing said strip rectangle with one or more of said virtual constructs.

6. The method of claim 4, wherein the size of the set of covering virtual constructs of an event is constant for all the event points.

7. The method of claim 4, wherein gaps between corresponding different covering virtual constructs of all event points are identical.

8. The method of claim 4, said finding of all covering virtual constructs of an event comprising:

pre-computing of a difference table;

computing the identification of a pivot virtual construct; and

adding said identification of pivot virtual construct to each of the elements stored in said difference table.

9. A method of providing a service of monitoring events or conditions, said method comprising at least one of the following:

providing a service that monitors events against interests of a customer, said service monitoring said events by decomposing continual range queries related to said customer interests with one or predefined virtual constructs, building a query index, and using said query index to match an event with said range queries;

maintaining one or more customer interests expressed as continual range queries for the service that monitors events; and

notifying a subset of said customers whose interests match an event.

10. A system for monitoring continual range queries against events, said system comprising:

a decomposing module that decomposes each range query into one or more predefined virtual constructs;

a query index construction module; and

an event matching module that uses said query index to match an event with said range queries.

11. The system of claim 10, further comprising:

at least one sensor to detect occurrence of events.

12. The system of claim 10, further comprising:

at least one client input station to permit a client to provide an input query.

13. The system of claim 10, further comprising:

at least one client receiver to permit a client to be notified of occurrence of an event of interest.

14. An apparatus for monitoring continual range queries against events, said apparatus comprising one of:

a query monitor that includes;

a decomposing module that decomposes each range query into one or more predefined virtual constructs;

a query index construction module; and

an event matching module that uses said query index to match an event with said range queries;

a sensor to detect occurrence of events and provides said occurrence of events into said query monitor;

a client receiver to permit a client to be notified of occurrence of an event of interest to said client.

15. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for monitoring continual range queries against events, said method comprising:

decomposing each range query into one or more predefined virtual constructs;

building a query index; and

using said query index to match an event with said range queries.