System and method for evaluating moving queries over moving objects

• US 7,299,126 B2
• Filed: 11/03/2003
• Issued: 11/20/2007
• Est. Priority Date: 11/03/2003
• Status: Active Grant

• Current Assignee: NNG LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Kun-Lung, Gedik, Bugra, Yu, Philip Shi-Lung
• Primary Examiner(s): NGUYEN, CUONG H
• Application Number:
  US10/700,168
• Publication Number:
  US 20050096841A1
• Time in Patent Office: 1,478 Days
• Field of Search: 700/28, 700/56, 717/107, 701/1, 701/207, 701/213, 707/1, 707/3, 342/357.06, 455/456.1, 455/41.2, 455/458, 455/141
• US Class Current: 701/207
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The present invention is directed to a system and a method for evaluating a plurality of moving queries over moving objects. The method, which can be embodied in a computer readable medium containing computer readable code, constructs motion-adaptive bounding boxes around the objects and queries and indexes the objects and queries based upon the bounding boxes. Predictive query results are used to optimize the evaluation of the moving queries. The bounding boxes vary in size and shape depending on the speed and motion direction of the objects and queries. The system of the present invention includes the moving objects and queries, each having an associated motion-adaptive bounding box. The system also provides for a monitoring system capable of monitoring the location and motion of the moving objects and moving queries and of evaluating the moving queries. The monitoring system includes a motion-adaptive query index and a motion-adaptive object index.

Claims

1. A method for evaluating a plurality of moving queries over moving objects, the queries and objects moving with respect to each other, the method comprising:

identifying a plurality of moving objects, each moving object comprising a position, a speed and a direction;

identifying a plurality of moving queries capable of evaluating the moving objects using criteria that change over time;

constructing a moving object bounding box associated with each moving object, each moving object bounding box comprising dimensions corresponding to at least one of the position, the speed and the direction of the associated moving object;

constructing a moving query bounding box associated with each moving query, each moving query bounding box comprising dimensions corresponding to one or more of the criteria, each bounding box sized to minimize overlapping among all bounding boxes and to maximize a length of time that the criteria of each moving query and the position, speed or direction of each moving object remain within the associated bounding box;

creating an object index for each one of the plurality of moving objects and a query index for each one of the moving queries using the corresponding bounding boxes; and

evaluating the plurality of queries periodically using the query index to determine which moving objects to include in the moving query evaluation.

2. The method of claim 1, wherein each bounding box comprises a motion-sensitive bounding box wherein the size and shape of each bounding box varies based upon a behavior of the associated moving object or moving query.

3. The method of claim 1, wherein the step of constructing the bounding box comprises placing each moving object or each moving query within the associated bounding box in an initial position arranged to maximize the length of time that the criteria of each moving query and the position, speed or direction of each moving object remain within the associated bounding box.

4. The method of claim 3, wherein each bounding box comprises a rectangle and the initial position comprises a corner of the rectangle.

5. The method of claim 1, further comprising receiving at least one of location information and motion information for each one of the moving objects and each moving query, determining if moving objects or moving queries have invalidated the associated bounding box based upon the received information, and replacing invalidated bounding boxes with new bounding boxes.

6. The method of claim 1, wherein the step of evaluating the moving queries periodically comprises generating predictive query results.

7. The method of claim 6, wherein the step of generating predictive query results comprises creating a motion function for each moving query and each moving object based upon a present location and a velocity vector associated with each moving object and moving query, computing a predicted path for each moving object and moving query based upon the associated motion function, comparing the predicted paths to actual paths for the moving objects and queries and computing new motion functions only when the predicted paths vary from the actual paths by a pre-determined threshold value.

8. The method of claim 6, wherein the step of generating predictive query results comprises using the bounding boxes associated with the moving queries and the moving objects to determine which moving objects to consider when generating the predictive query results.

9. The method of claim 8, further comprising selecting moving objects for the predictive query that have associated moving object bounding boxes intersecting with one of the moving query bounding boxes.

10. The method of claim 1, wherein the step of periodically evaluating the moving queries comprises maintaining a moving object table containing information about the moving objects.

11. The method of claim 10, wherein the step of evaluating the moving queries further comprises scanning the moving object table and updating the object index and the query index.

12. The method of claim 1, wherein the step of periodically evaluating the moving queries comprises maintaining a moving query table containing information about the moving queries.

13. The method of claim 12, wherein the step of evaluating the moving queries further comprises scanning the moving query table and updating the object index and the query index.