Method and system for querying in a moving object database

• US 6,895,329 B1
• Filed: 10/29/2001
• Issued: 05/17/2005
• Est. Priority Date: 10/30/2000
• Status: Expired due to Term

• Current Assignee: Fluensee Incorporated (TrackX Holdings, Inc.)
• Original Assignee: Board of Trustees of The University of Illinois
• Inventors: Wolfson, Ouri
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US10/074,903
• Time in Patent Office: 1,296 Days
• Field of Search: 701/201, 701/209, 701/202, 701/204, 701/205, 701/210, 701/211, 340/988, 340/990, 340/991, 340/992, 340/993, 340/995.23, 707/3, 707/4, 707/5
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• 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: Y10S 707/99933 Query processing, i.e. searching

Abstract

A database receives location information about a moving object. Using the destination of the object and an electronic map, the database finds a projected path for the moving object. From the projected path, the database computes a trajectory. The trajectory may be used to estimate past and future positions of the moving object. The moving object may send location updates to the database when its actual location differs from its anticipated location by more than an uncertainty threshold.

Claims

1. A method for querying a trajectory of a moving object, the method comprising:

obtaining a sequence of expected locations for the moving object including a starting paint, a destination paint and intermediate points;

computing a temporal-spatial path along which the moving object travels from the starting point through the intermediate points to the destination point;

creating a trajectory for the moving object, wherein the trajectory defines permissible spatial and temporal uncertainties in actual locations of the moving object relative to expected locations of the moving object along the temporal-spatial path; and

performing a query on the trajectory in order to determine location information about the moving object.

2. A computer readable medium having stored therein instructions for causing a processor to execute the method of claim 1.

3. The method of claim 1, further comprising:

storing the trajectory in the database; and

wherein performing a query on the trajectory comprises accessing the trajectory in the database in order to perform the query.

4. The method of claim 3, wherein the database stores respective trajectories for a plurality of moving objects.

5. The method of claim 1, wherein the query receives as input a location and a time, wherein the query returns a statistical likelihood that the moving object will be at the location and the time, and wherein the statistical likelihood is based at least in part on the permissible spatial and temporal uncertainties in the actual locations of the moving object.

6. The method of claim 5, further comprising providing a notification to a user based an results of the query.

7. The method of claim 1, wherein the query receives as input a spatial region and a time, wherein the query returns a statistical likelihood that the moving object will be within the spatial region at the time, and wherein the statistical likelihood is based at least in part on the permissible spatial and temporal uncertainties in the actual locations of the moving object.

8. The method of claim 7, wherein the spatial region is a convex polygon, a concave polygon, a circle, a sphere, a hypersphere, or a volumetric polygon.

9. The method of claim 7, further comprising providing a notification to a user based on results of the query.

10. The method of claim 1, wherein the query receives as input a spatial region and a time interval, wherein the query returns a statistical likelihood that the moving object will be within the spatial region during the time interval, and wherein the statistical likelihood is based at least in part on the permissible spatial and temporal uncertainties in the actual locations of the moving object.

11. The method of claim 10, wherein the spatial region is a convex polygon, a concave polygon, a circle, a sphere, a hypersphere or a volumetric polygon.

12. The method of claim 10, further comprising providing a notification to a user based results of the query.

13. A method for querying trajectories of a plurality of moving objects, the method comprising:

creating a respective trajectory for each of a plurality of moving objects, wherein the trajectory encompasses all possible temporal-spatial paths along which the moving object may travel between starting and destination locations within a range of spatial and temporal uncertainties; and

performing a query on the trajectories in order to determine location information about the moving objects.

14. A computer readable medium having stored therein instructions for causing a processor to execute the method of claim 13.

15. The method of claim 13, wherein the query receives as input a location and a time, wherein the query returns which of the plurality of moving objects has a highest statistical likelihood of being closest to the location at the time, and wherein the statistical likelihood is based at least in part on the range of spatial and temporal uncertainties for the moving object.

16. The method of claim 15, wherein the query additionally returns the statistical likelihood that the moving object will be closest to the location at the time.

17. The method of claim 13, wherein the query receives as input a location and a time, wherein the query returns, for each of the moving objects, a respective statistical likelihood that the moving object will be closest to the location at the time, and wherein the respective statistical likelihoods are based at learnt in part on the range of spatial and temporal uncertainties for the moving objects.

18. The method of claim 13, wherein the query receives as input a location, a time and a statistical likelihood threshold, wherein the query returns which of the plurality of moving objects have respective statistical likelihoods of being closest to the location at the time that are at least as high as the statistical likelihood threshold, and wherein the respective statistical likelihoods are based at least in part on the range of spatial and temporal uncertainties for the moving objects.

19. The method of claim 13, wherein the query receives as input a location and a time interval, wherein the query returns which of the plurality of moving objects has a highest statistical likelihood of being closest to the location during the time interval, and wherein the statistical likelihood is based at least in part on the range of spatial and temporal uncertainties for the moving object.

20. The method of claim 19, wherein the query additionally returns the statistical likelihood that the moving object will be closest to the location during the time interval.

21. The method of claim 13, wherein the query receives as input a location and a time interval, wherein the query returns, for each of the moving objects, a respective statistical likelihood that the moving object will be closest to the location during the time interval, and wherein the respective statistical likelihoods are based at least in part on the range of spatial and temporal uncertainties for the moving objects.

22. The method of claim 13, wherein the query receives as input a location, a time interval and a statistical likelihood threshold, wherein the query returns which of the plurality of moving objects have respective statistical likelihoods of being closest to the location during the time interval that are at least as high is the statistical likelihood threshold, and wherein the statistical likelihoods are based at least in part on the range of spatial and temporal uncertainties for the moving objects.

23. The method of claim 13, wherein the query receives as input a spatial region and a time, wherein the query returns which of the plurality of moving objects has a highest statistical likelihood of being within the spatial region at the time, and wherein the statistical likelihood is based at least in part on the range of spatial and temporal uncertainties for the moving object.

24. The method of claim 23, wherein the spatial region is a convex polygon, a concave polygon, a circle, a sphere, a hypersphere or a volumetric polygon.

25. The method of claim 23, wherein the query additionally returns the statistical likelihood that the moving object will be within the spatial region at the time.

26. The method of claim 13, wherein the query receives as input a spatial region and a time, wherein the query returns, for each of the moving objects, a respective statistical likelihood that the moving object will be within the spatial region at the time, and wherein the respective statistical likelihoods are based at least in part on the range of spatial and temporal uncertainties for the moving objects.

27. The method of claim 26, wherein the spatial region is a convex polygon, a concave polygon, a circle, a sphere, a hypersphere or a volumetric polygon.

28. The method of claim 13, wherein the query receives as input a spatial region, a time and a statistical likelihood threshold, wherein the query returns which of the plurality of moving objects have respective statistical likelihoods of being within the spatial region at the time that are at least as high as the statistical likelihood threshold, and wherein the respective statistical likelihoods are based at least in part on the range of spatial and temporal uncertainties for the moving objects.

29. The method of claim 28, wherein the spatial region is a convex polygon, a concave polygon, a circle, a sphere, a hypersphere or a volumetric polygon.

30. The method of claim 13, wherein the query receives as input a spatial region and a time interval, wherein the query returns which of the plurality of moving objects has a highest statistical likelihood of being within the spatial region during the time interval, and wherein the statistical likelihood is based at least in part on the range of spatial and temporal uncertainties for the moving object.

31. The method of claim 30, wherein the spatial region is a convex polygon, a concave polygon, a circle, a sphere, a hypersphere or a volumetric polygon.

32. The method of claim 30, wherein the query additionally returns the statistical likelihood that the moving object will be within the spatial region during the time interval.

33. The method of claim 13, wherein the query receives as input a spatial region and a time interval, wherein the query returns, for each of the moving objects, a respective statistical likelihood that the moving object will be within the spatial region during the time interval, and wherein the respective statistical likelihoods are based at least in part on the range of spatial and temporal uncertainties for the moving objects.

34. The method of claim 33, wherein the spatial region is a convex polygon, a concave polygon, a circle, a sphere, a hypersphere or a volumetric polygon.

35. The method of claim 13, wherein the query receives as input a spatial region, a time interval and a statistical likelihood threshold, wherein the query returns which of the plurality of moving objects have respective statistical likelihoods of being within the spatial region during the time interval that are at least as high as the statistical likelihood threshold, and wherein the respective statistical likelihoods are based at least in part on the range of spatial and temporal uncertainties for the moving objects.

36. The method of claim 35, wherein the spatial region is a convex polygon, a concave polygon, a circle, a sphere, a hypersphere or a volumetric polygon.

37. The method of claim 13, wherein the query receives as input a distance, a time interval and a statistical likelihood threshold, wherein the query returns which of the plurality of moving objects have respective statistical likelihoods of being within the distance of each other during the time interval that are at least an high as the statistical likelihood threshold, and wherein the respective statistical likelihoods are based at least in part on the range of spatial and temporal uncertainties for the moving objects.

38. The method as in any one of claims 15-37, further comprising providing a notification to a user based on results of the query.

39. A method for determining location information about a plurality of moving objects, the method comprising:

for each of a plurality of moving objects, creating a respective trajectory for the moving object, wherein the trajectory defines permissible spatial and temporal uncertainties in a given actual location of the moving object relative to an expected location along a temporal-spatial path for the moving object, wherein the temporal-spatial path is created from an expected starting location, an expected destination location and expected intermediate locations for the moving object;

storing the respective trajectories in a database; and

performing a query using at least two of the trajectories stored in the database in order to determine location information about the plurality of moving objects.

40. A computer readable medium having instructions stored therein for causing a processor to execute the method of claim 39.

41. The method of claim 39, further comprising providing a notification to a user based on a result of the query.

42. The method of claim 39, wherein the query receives as input a location and a time, and wherein the query returns which of the plurality of moving objects has a highest probability of being closest to the location at the time, wherein the probability is based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving object.

43. The method of claim 39, wherein the query receives as input a location and a time, and wherein the query returns, for each of the moving objects, a respective probability that the moving object will be closest to the location at the time, wherein the probability is based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving object.

44. The method of claim 39, wherein the query receives as input a location and a time interval, wherein the query returns which of the plurality of moving objects has a highest probability being closest to the location during the time interval, wherein the probability is based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving object.

45. The method of claim 39, wherein the query receives as input a location, a time interval and a probability threshold, wherein the query returns which of the plurality of moving objects have respective probabilities being closest to the location during the time interval that are at least as high as the probability threshold, and wherein the respective probabilities are based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving objects.

46. The method of claim 39, wherein the query receives as input a spatial region and a time, and wherein the query returns which of the plurality of moving objects has a highest probability of being within the spatial region at the time, wherein the probability is based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving object.

47. The method of claim 39, wherein the query receives as input a spatial region and a time, wherein the query returns, for each of the moving objects, a respective probability that the moving object will be within the spatial region at the time, and wherein the respective probabilities are based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving objects.

48. The method of claim 39, wherein the query receives as input a spatial region, a time and a probability threshold, wherein the query returns which of the plurality of moving objects have respective probabilities of being within the spatial region at the time that are at least as high as the probability threshold, and wherein the respective probabilities are based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving objects.

49. The method of claim 39, wherein the query receives as input a spatial region and a time interval, and wherein the query returns which of the plurality of moving objects has a highest probability of being within the spatial region during the time interval, wherein the probability is based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving object.

50. The method of claim 39, wherein the query receives as input a spatial region and a time interval, wherein the query returns, for each of the moving objects, a respective probability that the moving object will be within the spatial region during the time interval, and wherein the respective probabilities are based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving objects.

51. The method of claim 39, wherein the query receives am input a spatial region, a time interval and a probability threshold, wherein the query returns which of the plurality of moving objects have respective probabilities of being within the spatial region during the time interval that are at least as high as the probability threshold, and wherein the respective probabilities are based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving objects.

52. The method of claim 39, wherein the query receives as input a distance, a time interval and a probability threshold, wherein the query returns which of the plurality of moving objects have respective probabilities of being within the distance of each other during the time interval that are at least as high as the probability threshold, and wherein the respective probabilities are based at least in part on the permissible spatial and temporal uncertainties in actual locations of the moving objects.