System and method for spatial point-of-interest generation and automated trip segmentation using location data

• US 8,843,315 B1
• Filed: 06/28/2012
• Issued: 09/23/2014
• Est. Priority Date: 06/28/2011
• 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 J., Winters, Philip L., Perez, Rafael, Labrador, Miguel, Georggi, Nevine, Persad, Narin
• Primary Examiner(s): Jen, Ian
• Application Number:
  US13/536,115
• Time in Patent Office: 817 Days
• Field of Search: 701/1, 701/486
• US Class Current: 701/486
• CPC Class Codes: G01C 21/30 Map- or contour-matching

Abstract

This present invention is a spatial data processing system and method that allows the automatic, rapid, scalable analysis and transformation of large amounts of travel behavior data (e.g., tracking data points) into individual “points-of-interest” and discrete trips stored in a spatial database. Each trip has a point-of-interest as a starting and ending location, and contains multiple positions (e.g. latitude and longitudes) which define the travel path of the user/device during that time period.

Claims

1. A method of generating a travel history for a user from a set of global navigation satellite system (GNSS) data for the user, the method comprising:

acquiring a set of time-stamped GNSS data recorded by a user'"'"'s mobile device, the time-stamped GNSS data comprising spatial and temporal information;

defining a plurality of temporarily ordered points-of-interest (POI) for the user based upon the acquired set of time-stamped GNSS data, wherein each of the plurality of POIs defines a spatial dimension where the user has stopped for a significant amount of time; and

identifying a plurality of trips taken by the user between the plurality of defined POIs to generate a travel history for the user, wherein each of the plurality of trips originates and terminates at one of the plurality of POIs and wherein each of the plurality of trips defines a spatial and temporal property for movement between two of the plurality of POIs.

2. The method of claim 1, wherein defining a plurality of temporarily-ordered POIs for the user based upon the set of time-stamped GNSS data, further comprises:

representing the set of time-stamped GNSS data as a plurality of temporarily ordered balanced binary trees;

determining a minimum distance in the Cartesian product of a first binary tree and a second binary tree of the plurality of balanced binary trees;

merging the first binary tree and the second binary tree if the minimum distance is less than a predetermined value; and

repeating the steps of determining a minimum distance and merging the binary trees to define the plurality of temporarily-ordered POI'"'"'s.

3. The method of claim 2, wherein the merging is performed in logarithmic running time, maintaining a O(n) memory storage requirement.

4. The method of claim 2, wherein the first binary tree and the second binary tree are disjointed.

5. The method of claim 2, wherein the first binary tree and the second binary tree are disjointed and ambiguously-related, wherein the first binary tree and the second binary tree are ambiguously-related if a portion of a time-stamped data range of the second binary tree overlaps a time-stamped data range of the first binary tree.

6. The method of claim 1, wherein identifying a plurality of trips taken by the user further comprises identifying a maximum time-stamp and a minimum time-stamp for each of the plurality of POIs.

7. The method of claim 6, wherein identifying a maximum time-stamp and a minimum time-stamp for each of the plurality of POIs is performed in O(log n) time.

8. The method of claim 2, wherein merging the first binary tree and the second binary tree if the minimum distance is less than a predetermined value further comprises:

identifying an overlapping time range common to the first binary tree and the second binary tree; and

removing the time-stamped GNSS data from the second binary tree prior to merging the first binary tree and the second binary tree.

9. The method of claim 1 further comprising, identifying at least one pseudo-POI within the plurality of POIs.

10. The method of claim 1 further comprising, inserting a record into a spatial database that represents the travel history of the user.

11. A non-transitory computer readable storage medium having a method encoded thereon, the method comprising:

generating a travel history for a user from a set of global navigation satellite system (GNSS) data for the user, the method comprising;

acquiring a set of time-stamped GNSS data recorded by a user'"'"'s mobile device, the time-stamped GNSS data comprising spatial and temporal information;

defining a plurality of temporarily ordered points-of-interest (POI) for the user based upon the acquired set of time-stamped GNSS data, wherein each of the plurality of POIs defines a spatial dimension where the user has stopped for a significant amount of time; and

identifying a plurality of trips taken by the user between the plurality of defined POIs to generate a travel history for the user, wherein each of the plurality of trips originates and terminates at one of the plurality of POIs and wherein each of the plurality of trips defines a spatial and temporal property for movement between two of the plurality of POIs.

12. The non-transitory computer readable storage medium of claim 11, wherein defining a plurality of temporarily-ordered POIs for the user based upon the set of time-stamped GNSS data, further comprises:

representing the set of time-stamped GNSS data as a plurality of temporarily ordered balanced binary trees;

determining a minimum distance in the Cartesian product of a first binary tree and a second binary tree of the plurality of balanced binary trees;

merging the first binary tree and the second binary tree if the minimum distance is less than a predetermined value; and

repeating the steps of determining a minimum distance and merging the binary trees to define the plurality of temporarily-ordered POI'"'"'s.

13. The method of claim 12, wherein the merging is performed in logarithmic running time, maintaining a O(n) memory storage requirement.

14. The non-transitory computer readable storage medium of claim 12, wherein the first binary tree and the second binary tree are disjointed.

15. The non-transitory computer readable storage medium of claim 12, wherein the first binary tree and the second binary tree are disjointed and ambiguously-related, wherein the first binary tree and the second binary tree are ambiguously-related if a portion of a time-stamped data range of the second binary tree overlaps a time-stamped data range of the first binary tree.

16. The non-transitory computer readable storage medium of claim 11, wherein identifying a plurality of trips taken by the user further comprises identifying a maximum time-stamp and a minimum time-stamp for each of the plurality of POIs.

17. The non-transitory computer readable storage medium of claim 16, wherein identifying a maximum time-stamp and a minimum time-stamp for each of the plurality of POIs is performed in O(log n) time.

18. The non-transitory computer readable storage medium of claim 12, wherein merging the first binary tree and the second binary tree if the minimum distance is less than a predetermined value further comprises:

identifying an overlapping time range common to the first binary tree and the second binary tree; and

removing the time-stamped GNSS data from the second binary tree prior to merging the first binary tree and the second binary tree.

19. The non-transitory computer readable storage medium of claim 11, further comprising, identifying at least one pseudo-POI within the plurality of POIs.

20. The non-transitory computer readable storage medium of claim 11, further comprising, inserting a record into a spatial database that represents the travel history of the user.

21. A computer system comprising:

a central processing unit for generating a travel history for a user from a set of global navigation satellite system (GNSS) data for the user by acquiring a set of time-stamped GNSS data recorded by a user'"'"'s mobile device, the time-stamped GNSS data comprising spatial and temporal information, defining a plurality of temporarily ordered points-of-interest (POI) for the user based upon the acquired set of time-stamped GNSS data, wherein each of the plurality of POIs defines a spatial dimension where the user has stopped for a significant amount of time and identifying a plurality of trips taken by the user between the plurality of defined POIs to generate a travel history for the user, wherein each of the plurality of trips originates and terminates at one of the plurality of POIs and wherein each of the plurality of trips defines a spatial and temporal property for movement between two of the plurality of POIs; and

a memory unit coupled to the central processing unit, the memory unit having a an O(n) memory storage requirement.