Method for determining critical points in location data generated by location-based applications

• US 8,249,807 B1
• Filed: 08/22/2008
• Issued: 08/21/2012
• Est. Priority Date: 08/22/2007
• Status: Active Grant

• Current Assignee: University of South Florida (State University System of Florida)
• Original Assignee: University of South Florida (State University System of Florida)
• Inventors: Barbeau, Sean, Winters, Philip L., Perez, Rafael, Labrador, Miguel, Georggi, Nevine
• Primary Examiner(s): O'Connor, Gerald J.
• Assistant Examiner(s): Ng, Jonathan K
• Application Number:
  US12/196,673
• Time in Patent Office: 1,460 Days
• Field of Search: 701/117, 701/200, 701/433, 701/431, 701/467, 701/508, 455/418, 455/456, 340/990, 342/357.51
• US Class Current: 701/490
• CPC Class Codes: G01S 5/0027 of actual mobile position, i.e. position determined on mobile
• CPC Class Codes: G07C 5/0808 Diagnosing performance data testing of vehicles G01M17/00; testing of electrical installation on vehicles G01R31/005
• CPC Class Codes: H04W 64/006 with additional information processing, e.g. for direction or speed determination
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Provided is a critical point method used to determine the points of a real-time stream of location data, such as Global Positioning System (GPS) data, that should be retained based on their importance in reconstructing the travel path of a mobile device. The method may run on a mobile device or on a server. When run on a mobile device, the method reduces the amount of data transferred between mediums by only transferring points that are critical to reconstructing the path of travel of the mobile device. This reduction saves power used in the wireless transmission and reception of the non-critical data and the bandwidth used while transmitting non-critical data. The method may be run every time a new position is calculated. When a new position is determined to be a critical point, the point is transmitted. If the new position is not a critical point, then the point is discarded.

Claims

1. A method of identifying critical points in travel path of a mobile device, the method comprising:

acquiring location data with a location positioning system of the mobile device to identify a travel path of the mobile device, the location data comprising a plurality of location data points;

identifying a first critical point in the travel path of the mobile device;

identifying a first location data point in the location data;

determining a first azimuth value for the first critical point and the first location data point;

identifying a second location data point in the location data;

determining a second azimuth value for the first critical point and the second location data point;

determining a speed of the mobile device;

determining a mode of transportation of the mobile device based upon the speed of the mobile device;

setting an azimuth threshold value based at least in part upon the determined mode of transportation of the mobile device;

identifying the second location data point as a second critical point in the travel path of the mobile device if the absolute value of a difference between the first azimuth value and the second azimuth value is greater than the azimuth threshold value determined by the mode of transportation of the mobile device.

2. The method of claim 1, wherein the second location data point is identified as a non-critical point in the travel path of the mobile device if the absolute value of the difference between the first azimuth value and the second azimuth value is not greater than the azimuth threshold value determined by the mode of transportation of the mobile device.

3. The method of claim 1, wherein the azimuth threshold value increases as the speed of the mobile device decreases and the azimuth threshold value decreases as the speed of the mobile device increases.

4. The method of claim 1, wherein the first azimuth value is equal to an angle measurement between a projected vector extending between the first critical point and the first location data point relative to a reference vector and the second azimuth value is equal to an angle measurement between a projected vector extending between the first critical point and the second location data point relative to the reference vector.

5. The method of claim 1, wherein the plurality of location data points each comprise data selected from the group consisting of latitude, longitude, time-stamp information, altitude, estimated accuracy uncertainty, speed, heading and combinations thereof.

6. The method of claim 1, wherein the critical points are identified by the mobile device.

7. The method of claim 1, further comprising transmitting the critical points to an application server.

8. The method of claim 1, further comprising tracking a duration of time after the first critical point has been identified, and if the duration of time exceeds a predetermined threshold, identifying the second data location point as a second critical point.

9. The method of claim 1, further comprising tracking a distance traveled by the mobile device after the first critical point has been identified, and if the distance traveled exceeds a predetermined threshold, identifying the second data location point as a second critical point.

10. The method of claim 1, further comprising, polling the mobile device and upon polling the mobile device, identifying the second data location point as a second critical point.

11. The method of claim 1, wherein the mode of transportation is selected from the group consisting of walking, bicycling and driving.

12. The method of claim 1, wherein determining the mode of transportation of the mobile device further comprises:

establishing a maximum speed associated with a first mode of transportation;

establishing a maximum speed associated with a second mode of transportation, wherein the maximum speed for the second mode of transportation is greater than the maximum speed for the first mode of transportation;

comparing the speed of the mobile device to the maximum speed associated with the first mode transportation and determining the mode of transportation to be the first mode of transportation if the speed of the mobile device is less than the maximum speed of the first mode of transportation; and

comparing the speed of the mobile device to the maximum speed associated with the second mode of transportation and determining the mode of transportation to be the second mode of transportation if the speed of the mobile device is less than the maximum speed associated with the second mode of transportation.

13. The method of claim 12, further comprising comparing the speed of the mobile device with the maximum speed associated with the second mode of transportation and determining the mode of transportation to be a third mode of transportation if the speed of the mobile device is greater than the maximum speed associated with the second mode of transportation.

14. The method of claim 12, wherein an azimuth threshold value associated with the first mode of transportation is greater than an azimuth threshold value associated with the second mode of transportation and the azimuth threshold value associated with the second mode of transportation is greater than an azimuth threshold value associated with the third mode of transportation.

33. The method of claim 1 wherein the location data acquired with the location positioning system of the mobile device is transmitted to an application server and the steps of identifying a first critical point in the travel path of the mobile device, identifying a first location data point in the location data, determining a first azimuth value for the first critical point and the first location data point, identifying a second location data point in the location data, determining a second azimuth value for the first critical point and the second location data point, determining a speed of the mobile device, determining a mode of transportation of the mobile device based upon the speed of the mobile device, setting an azimuth threshold value based at least in part upon the determined mode of transportation of the mobile device, and identifying the second location data point as a second critical point in the travel path of the mobile device if the absolute value of a difference between the first azimuth value and the second azimuth value is greater than the azimuth threshold value determined by the mode of transportation of the mobile device are performed by the application server.

15. A mobile device, comprising:

a positioning system, comprising a global positioning system device, configured to acquire location data for a travel path of the mobile device, the location data comprising a plurality of location data points;

a critical point identification system, comprising a processor, in communication with the positioning system, the critical point identification system configured to locate a first critical point in the travel path of the mobile device, to identify a first location data point in the location data, to determine a first azimuth value for the first critical point and the first location data point, to identify a second location data point in the location data,

to determine a second azimuth value for the first critical point and the second location data point, to determine the speed of the mobile device, to determine a mode of transportation of the mobile device based upon the determined speed of the mobile device, to set an azimuth threshold value based at least in part upon the determined mode of transportation of the mobile device, and to identify the second location data point as a second critical point in the travel path of the mobile device if the absolute value of a difference between the first azimuth value and the second azimuth value is greater than the azimuth threshold value determined by the mode of transportation and if the speed of the mobile device is greater than a predetermined speed threshold value.

16. The mobile device of claim 15, wherein the azimuth threshold value increases as the speed of the mobile device decreases and the azimuth threshold value decreases as the speed of the mobile device increases.

17. The mobile device of claim 15, wherein the first azimuth value is equal to an angle measurement between a projected vector extending between the first critical point and the first location data point relative to a reference vector and the second azimuth value is equal to an angle measurement between a projected vector extending between the first critical point and the second location data point relative to the reference vector.

18. The mobile device of claim 15, wherein the plurality of location data points each comprise data selected from the group consisting of latitude, longitude, time-stamp information, altitude, estimated accuracy uncertainty, speed, heading and combinations thereof.

19. The mobile device of claim 15, further comprising a communication system in communication with the critical point identification system, the communication system to transmit the critical points to an application server.

20. A non-transitory, tangible computer readable storage medium bearing software instruction for enabling a computer to identify critical points in a travel path of a mobile device, the software instructions including instructions for:

acquiring location data for the travel path of the mobile device, the location data comprising a plurality of location data points;

identifying a first critical point in the travel path of the mobile device;

identifying a first location data point in the location data;

determining a first azimuth value for the first critical point and the first location data point;

identifying a second location data point in the location data;

determining a second azimuth value for the first critical point and the second location data point;

determining a speed of the mobile device;

determining a mode of transportation of the mobile device based upon the speed of the mobile device

setting an azimuth threshold value based at least in part upon the determined mode of transportation of the mobile device;

identifying the second location data point as a second critical point in the travel path of the mobile device if the absolute value of a difference between the first azimuth value and the second azimuth value is greater than the azimuth threshold value determined by the mode of transportation of the mobile device.

21. The computer readable storage medium of claim 20, wherein the second location data point is identified as a non-critical point in the travel path of the mobile device if the absolute value of the difference between the first azimuth value and the second azimuth value is not greater than the azimuth threshold value determined by the mode of transportation of the mobile device.

22. The computer readable storage medium of claim 20, wherein the azimuth threshold value increases as the speed of the mobile device decreases and the azimuth threshold value decreases as the speed of the mobile device increases.

23. The computer readable storage medium of claim 20, wherein the first azimuth value is equal to an angle measurement between a projected vector extending between the first critical point and the first location data point relative to a reference vector and the second azimuth value is equal to an angle measurement between a projected vector extending between the first critical point and the second location data point relative to the reference vector.

24. The computer readable storage medium of claim 20, wherein the plurality of location data points each comprise data selected from the group consisting of latitude, longitude, time-stamp information, altitude, estimated accuracy uncertainty, speed, heading and combinations thereof.

25. The computer readable storage medium of claim 20, further including instructions for transmitting the critical points to an application server.

26. The computer readable storage medium of claim 20, further including instructions for tracking a duration of time after the first critical point has been identified, and if the duration of time exceeds a predetermined threshold, identifying the second data location point as a second critical point.

27. The computer readable storage medium of claim 20, further including instructions for tracking a distance traveled by the mobile device after the first critical point has been identified, and if the distance traveled exceeds a predetermined threshold, identifying the second data location point as a second critical point.

28. The computer readable storage medium of claim 20, further including instructions for, upon polling the mobile device with an application server, identifying the second data location point as a second critical point.

29. The computer readable storage medium of claim 20, wherein the mode of transportation is selected from the group consisting of walking, bicycling and driving.

30. The computer readable storage medium of claim 20, wherein identifying the mode of transportation of the mobile device further comprises:

establishing a maximum speed associated with a first mode of transportation;

establishing a maximum speed associated with a second mode of transportation, wherein the maximum speed for the second mode of transportation is greater than the maximum speed for the first mode of transportation;

comparing the speed of the mobile device to the maximum speed associated with the first mode transportation and determining the mode of transportation to be the first mode of transportation if the speed of the mobile device is less than the maximum speed of the first mode of transportation; and

comparing the speed of the mobile device to the maximum speed associated with the second mode of transportation and determining the mode of transportation to be the second mode of transportation if the speed of the mobile device is less than the maximum speed associated with the second mode of transportation.

31. The computer readable storage medium of claim 30, further comprising comparing the speed of the mobile device with the maximum speed associated with the second mode of transportation and determining the mode of transportation to be a third mode of transportation if the speed of the mobile device is greater than the maximum speed associated with the second mode of transportation.

32. The computer readable storage medium of claim 30, wherein an azimuth threshold value associated with the first mode of transportation is greater than an azimuth threshold value associated with the second mode of transportation and the azimuth threshold value associated with the second mode of transportation is greater than an azimuth threshold value associated with the third mode of transportation.