System and method for evaluating moving queries over moving objects

• US 20050096841A1
• Filed: 11/03/2003
• Published: 05/05/2005
• 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
• Granted Patent: US 7,299,126 B2
• Time in Patent Office: Days
• 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:

constructing a bounding box to contain each one of the plurality of moving objects and moving queries;

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 box; and

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

2. The method of claim 1, wherein the step of constructing the bounding box comprises varying the size and shape of each bounding box based upon a speed and a direction of motion of the corresponding moving object or moving query.

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

4. The method of claim 1, wherein the step of constructing the bounding box comprises constructing a rectangle for each moving object and moving query, sizing the rectangle based upon a speed and a direction of motion of the corresponding moving object or moving query, and placing the moving object or moving query at a corner of the rectangle such that the direction of motion is generally aligned with a diagonal 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 moving queries, determining which moving objects and moving queries have invalidated the corresponding 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 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 bounding boxes intersecting with a bounding box associated with the query.

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 moving object index and the moving 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 moving object index and the moving query index.

14. A computer readable medium containing a computer executable code that when read by a computer causes the computer to perform a method of evaluating a plurality of moving queries over moving objects, the method comprising:

constructing a bounding box to contain each one of the plurality of moving objects and moving queries;

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 box; and

evaluating the plurality of queries periodically using the query index.

15. The computer readable medium of claim 14, wherein the step of constructing the bounding box comprises varying the size and shape of each bounding box based upon a speed and a direction of motion of the corresponding moving object or moving query.

16. The computer readable medium of claim 14, wherein the step of constructing the bounding box comprises placing the moving object or moving query within the corresponding bounding box in an initial position arranged to maximize the length of time that each moving object and moving query is disposed within the bonding box.

17. The computer readable medium of claim 14, wherein the step of constructing the bounding box comprises constructing a rectangle for each moving object and moving query, sizing the rectangle based upon a speed and a direction of motion of the corresponding moving object or moving query, and placing the moving object or moving query at a corner of the rectangle such that the direction of motion is generally aligned with a diagonal of the rectangle.

18. The computer readable medium of claim 14, wherein the method further comprises receiving at least one of location information and motion information for each one of the moving objects and moving queries, determining which moving objects and moving queries have invalidated the corresponding bounding box based upon the received information, and replacing invalidated bounding boxes with new bounding boxes.

19. The computer readable medium of claim 14, wherein the step of evaluating the moving queries periodically comprises generating predictive query results.

20. The computer readable medium of claim 19, 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 for moving objects and moving queries whose predicted paths vary from their actual paths by a pre-determined threshold value.

21. The computer readable medium of claim 19, wherein the step of generating predictive query results comprises using the bounding boxes to determine which moving objects to consider when generating the predictive query results.

22. The computer readable medium of claim 21, wherein the method further comprises selecting moving objects for the predictive query that have bounding boxes intersecting with a bounding box associated with the query.

23. The computer readable medium of claim 14, wherein the step of periodically evaluating the moving queries comprises maintaining a moving object table containing information about the moving objects.

24. The computer readable medium of claim 23, wherein the step of evaluating the moving queries further comprises scanning the moving object table and updating the moving object index and the moving query index.

25. The computer readable medium of claim 14, wherein the step of periodically evaluating the moving queries comprises maintaining a moving query table containing information about the moving queries.

26. The computer readable medium of claim 25, wherein the step of evaluating the moving queries further comprises scanning the moving query table and updating the moving object index and the moving query index.

27. A system for evaluating a plurality of moving queries over a plurality of moving objects, the system comprising:

a plurality of moving objects;

a plurality of moving queries, each query associated with a spatial range;

a plurality of motion-adaptive bounding boxes, each bounding box associated with one of the moving objects or moving queries;

at least one 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 comprising a motion-adaptive query index and a motion-adaptive object index.

28. The system of claim 27, wherein the motion-adaptive bounding boxes are adaptive to both the speed and frequency of changes in direction of the associated moving object or moving query.

29. The system of claim 27, wherein each moving query comprises a spatial range and the spatial range is contained within the motion-adaptive bounding box associated with the moving query.

30. The system of claim 27, wherein the monitoring system further comprising a moving object table and a moving query table containing information about the moving objects and queries.

31. The system of claim 30, wherein the monitoring system further comprises a logic control unit for evaluating the moving queries, a receiver in communication with the logic control unit for receiving information about the moving objects and queries and a storage system in communication with the logic control unit for storing the indexes and tables.