Method and structure for monitoring moving objects

• US 7,835,953 B2
• Filed: 09/29/2003
• Issued: 11/16/2010
• Est. Priority Date: 09/29/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Kun-Lung, Chen, Shyh-Kwei, Yu, Philip Shi-lung
• Primary Examiner(s): Gart; Matthew S
• Assistant Examiner(s): CRAWLEY, TALIA F
• Application Number:
  US10/671,932
• Publication Number:
  US 20050071083A1
• Time in Patent Office: 2,605 Days
• Field of Search: 705/28, 707/104.1, 702/102
• US Class Current: 705/28
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

A method and structure for monitoring continual queries over moving objects, including identifying a query region in a digital format. Each query region is strictly covered by at least one shingle such that each query region is completely covered by the at least one shingle and no section of any of the at least one shingle falls outside the query region.

Claims

1. A method of monitoring continual queries over moving objects, said method comprising:

preliminarily establishing, using a processor on a computer, an object identification listing for each of an object being monitored, said object identification listing providing an indication of which shingles cover an object and which query region includes these shingles, said object identification listing to be updated as said object moves;

storing coordinates defining a query region in a memory;

for each query region, retrieving, from said memory, said coordinates of said query region representing a continual query over which movements of moving objects are to be monitored and constructing, using said processor of said computer and said retrieved coordinates, a covering for said query region, said covering comprising at least one shingle, so that said query region is completely covered by said at least one shingle and no section of any said at least one shingle falls outside said query region;

periodically, throughout a period of said continual query monitoring, receiving location information for each said object being monitored;

determining from said location information whether any said object is covered by any of said shingles of said query region; and

updating said object identification listing based on said determining, thereby also reflecting an updating of said moving objects relative to said query regions.

2. The method of claim 1, wherein, when said at least one shingle strictly covering a query region comprises a plurality of shingles, the shingles in said plurality are allowed to overlap.

3. The method of claim 1, wherein said shingles are all one predetermined shape.

4. The method of claim 1, wherein the query regions comprise predetermined geographical areas on the earth'"'"'s surface and said shingles comprise at least one of:

two-dimensional shapes; and

three-dimensional shapes.

5. The method of claim 1, further comprising:

for a query region, determining, using said processor, an optimal shingle size for said query region.

6. The method of claim 5, wherein said strictly covering said query region comprises:

forming, using said processor, a first strip rectangle based on said optimal shingle size, said first strip rectangle aligned along an edge of said query region in a first dimension.

7. The method of claim 6, wherein if said first strip rectangle fails to strictly cover said query region, said method further comprising:

relative to a second dimension, using said processor to form a second strip rectangle based on said optimal shingle size.

8. The method of claim 7, wherein said optimal shingle size allows said second strip rectangle to strictly cover said query region.

9. The method of claim 8, wherein said first strip rectangle and said second strip rectangle overlay in order to achieve a strict covering of said query region.

10. The method of claim 7, wherein if said optimal shingle size does not permit said second strip to strictly cover said query region, said method further comprising:

in said second dimension, using said processor for repeatedly forming a strip rectangle based on said optimal shingle size until said query region is completely covered by strip rectangles, wherein a final strip rectangle is allowed to overlap a previous strip rectangle to achieve said strict covering.

11. The method of claim 6, further comprising:

forming shingles, using said processor, in said first strip rectangle, each said shingle based on said optimal shingle size, so as to strictly cover said first strip rectangle.

12. The method of claim 1, wherein a strict covering of said first strip rectangle is achieved by allowing a last shingle in said first strip rectangle to overlap a previously-placed shingle.

13. The method of claim 7, further comprising:

for each strip rectangle formed, using said processor for forming shingles in said strip rectangle in a manner that strictly covers said strip rectangle.

14. The method of claim 1, further comprising:

maintaining, in a memory of said computer, a query index of objects that are located in each query region, as based on which shingles currently cover the objects of interest.

15. The method of claim 14, wherein certain query evaluations are skipped by filtering out a subset of said objects of interest that have not moved from a shingle previously covering the object.

16. A system of monitoring continual queries over moving objects, said system comprising:

a module executed on a computer that receives coordinates defining one or more query regions, constructs a cover that strictly covers each query region with at least one covering shingle, each said query region being a region represented in a digital format over which said objects are to be continually monitored, wherein the strictly covering function comprises completely covering a query by at least one said covering shingle, wherein none of said shingles strictly covering said query extends outside said query, and each said shingle strictly covering said query is permitted to overlap another shingle strictly covering said query, and determines whether any object being monitor is currently covered by any of said covering shingles,

wherein said determining is repeated in a repetitive manner as updated current locations of objects are received, thereby providing updates of movements of said objects relative to each said query region.

17. The system of claim 16, further comprising:

a calculator, executed on said computer, that skips certain query evaluations by filtering out a subset of said moving objects using said strictly covering shingles.

18. The system of claim 17, wherein said calculator further constructs a query index based on said covering shingles and said filtering out a subset of moving objects is based on said query index.

19. The system of claim 17, wherein said filtering out a subset of said moving objects is based on determining a relative movement since the last position with respect to shingle boundaries.

20. The system of claim 18, wherein said filtering out a subset of moving objects is based on building of a query index, said calculator further:

predefining a set of shingles;

strictly covering a range query with one or more said shingles; and

maintaining the ID of said range query with said covering shingles.

21. The system of claim 17, wherein said filtering out a subset of said moving objects, further comprises:

computing the covering shingles of an old object location;

computing the covering shingles of a new object location;

deleting an object ID instance from object lists associated with the queries that are covered by the covering shingles of the old location but not of the new location; and

inserting an object ID instance into object lists associated with the queries that are covered by the covering shingles of the new location but not of the new location.

22. The system of claim 17, wherein the filtering out of a subset of moving objects further comprises:

computing the covering shingles of an old object location;

computing the covering shingles of a new object location; and

taking no action for queries that are covered by the covering shingles of both the new and the old locations.

23. A service based on a computerized monitoring of continual queries over moving objects, said service comprising at least one of:

providing a monitoring of moving objects against continual queries, using a computer, each said query being a region represented in a digital format and representing a region over which said moving objects are to be continually monitored, using a method comprising;

receiving coordinates defining at least one query region in a processor of a computer;

constructing a cover strictly covering each said query region by at least one shingle, using said processor, wherein said strictly covering function comprises completely covering a query region by said at least one shingle and no section of any said at least one shingle falls outside said query region;

determining, using said processor, whether any object being monitored is covered by any of said shingles of any of said query regions; and

reporting location information of said moving objects based on said determining, wherein said determining and reporting are repeated in a repetitive manner as updated current locations of objects are received, thereby providing updates of movements of said objects relative to said query regions;

providing a result of said monitoring using said computerized method; and

using a result of said monitoring using said method.

24. A signal-bearing storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of monitoring continual queries over moving objects, said method comprising:

receiving coordinates defining one or more query regions, each said query region comprising a region over which said moving objects are being continually monitored;

constructing a cover strictly covering each said query region by at least one shingle, wherein said strictly covering function comprises completely covering said query region by at least one shingle and no section of any said at least one shingle falls outside said query region;

periodically receiving location information of each object being monitor and determining whether each said monitor object is covered by any of said shingles, thereby providing updates on movements of said monitor objects relative to said query regions; and

reporting locations of said objects based on said determining.