Method and structure for monitoring moving objects

• US 20050071083A1
• 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 7,835,953 B2
• Time in Patent Office: Days
• US Class Current: 701/213
• 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:

identifying a query region in a digital format; and

strictly covering said query region by 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.

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, further comprising:

establishing an object identification listing for each object being monitored, said object identification listing providing an indication of which shingles cover an object and which query region includes these shingles.

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

5. 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.

6. The method of claim 1, further comprising:

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

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

forming 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.

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

relative to a second dimension, forming a second strip rectangle based on said optimal shingle size.

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

10. The method of claim 9, wherein said first strip rectangle and said second strip rectangle overlay in order to achieve said strictly covering.

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

in said second dimension, 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.

12. The method of claim 7, further comprising:

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

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

14. The method of claim 8, further comprising:

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

15. The method of claim 3, further comprising:

identifying which shingles cover each object of interest; and

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

16. The method of claim 15, 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.

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

a module that strictly covers each query with at least one covering shingle, each said query being a region represented in a digital format, 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.

18. The system of claim 17, further comprising:

a calculator that skips certain query evaluations by filtering out a subset of said moving objects using said strict covering shingles.

19. The system of claim 18, 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.

20. The system of claim 18, 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.

21. The system of claim 19, 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 singles; and

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

22. The system of claim 18, 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.

23. The system of claim 18, 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.

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

providing a monitoring of moving objects against continual queries, each said query being a region represented in a digital format, using a method comprising a strictly covering of each said query region by at least one shingle, 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;

providing a result of said monitoring using said method; and

using a result of said monitoring using said method.

25. A signal-bearing 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:

strictly covering each of a 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.