Method and apparatus for providing location trajectory compression based on map structure

• US 9,122,702 B2
• Filed: 10/16/2012
• Issued: 09/01/2015
• Est. Priority Date: 10/16/2012
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Nokia Technologies Oy (Nokia Corporation)
• Inventors: Nefedov, Nikolai, BISWAS, Debmalya
• Primary Examiner(s): Ly, Anh
• Application Number:
  US13/652,820
• Publication Number:
  US 20140108361A1
• Time in Patent Office: 1,050 Days
• Field of Search: 701/200, 701/201, 701/202, 701/208, 701/211, 701/408, 701/537, 701/533, 701/209, 701/213, 701/210, 701/117, 701/207, 701/283, 701/57, 715/764, 715/702, 715/781, 715/788, 455/456.1, 455/456.6, 345/636, 345/419, 707/759, 707/803, 707/737, 707/736, 707/693, 707/E17.002, 707/E17.005, 707/E14.014, 707/E17.089, 707/E17.014, 707/754, 707/740, 707/758, 707/752, 707/E17.009, 707/E17.058, 709/219, 381/56
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

An approach is provided for compressing location trajectories based on map structure. A compression platform causes, at least in part, a mapping of at least one location trajectory to at least one map to determine one or more intersections traveled along the at least one location trajectory. The compression platform further determines at least one compression key based, at least in part, on one or more outgoing roads of the one or more intersections. The compression platform also causes, at least in part, a compression of the at least one location trajectory based, at least in part, on the at least one compression key.

Claims

1. A method comprising:

causing, at least in part, a mapping of at least one location trajectory to at least one map to determine one or more intersections traveled along the at least one location trajectory, wherein the at least one location trajectory comprises a sequence of roads that follow a route previously taken by a user applied to roads of the at least one map;

determining, by at least one processor, at least one compression key based, at least in part, on one or more outgoing roads of the one or more intersections;

causing, at least in part, a compression of the at least one location trajectory based, at least in part, on the at least one compression key;

determining one or more intermediate intersections, one or more intermediate roads, or a combination thereof associated with the at least one location trajectory,

wherein the compression of the at least one location trajectory is a partial compression based, at least in part, on the one or more intermediate intersections, the one or more intermediate roads, or a combination thereof.

2. A method of claim 1, further comprising:

determining a total number of outgoing roads of at least one intersection of the one or more intersections;

causing, at least in part, a selection of a number of the outgoing roads for the at least one intersection; and

determining the at least one compression key based, at least in part, on the number of the selected outgoing roads.

3. A method of claim 2, wherein the number of the selected outgoing roads is one less than the total number of outgoing roads.

4. A method of claim 2, wherein the selected outgoing roads are selected randomly.

5. A method of claim 2, further comprising:

determining an intended anonymity level associated with the compression of the at least one location trajectory; and

causing, at least in part, a modification of the at least one compression key based, at least in part, on including one or more roads associated with above a threshold number of outgoing roads,

wherein the at least one location trajectory contains historical location information.

6. A method of claim 1, further comprising:

determining one or more roads associated with the at least one location trajectory; and

causing, at least in part, a removal of at least one road associated with the at least one location trajectory if the at least one road is excluded within the at least one compression key to compress the at least one location trajectory.

7. A method of claim 1, further comprising:

determining whether one or more of the outgoing roads are common outgoing roads based, at least in part, on context information associated with the user, user profile information, user preference information, or a combination thereof; and

determining the at least one compression key based, at least in part, on one or more common outgoing roads.

8. A method of claim 7, further comprising:

causing, at least in part, a monitoring of context information associated with the user to determine one or more changes to the one or more common outgoing roads; and

determining one or more other compression keys based, at least in part, on the one or more changes.

9. A method of claim 8, further comprising:

causing, at least in part, a storing of the at least one compression key and the one or more other compression keys.

10. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs,

the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,

cause, at least in part, a mapping of at least one location trajectory to at least one map to determine one or more intersections traveled along the at least one location trajectory, wherein the at least one location trajectory comprises a sequence of roads that follow a route previously taken by a user applied to roads of the at least one map;

determine at least one compression key based, at least in part, on one or more outgoing roads of the one or more intersections;

cause, at least in part, a compression of the at least one location trajectory based, at least in part, on the at least one compression key;

determine one or more intermediate intersections, one or more intermediate roads, or a combination thereof associated with the at least one location trajectory,

wherein the compression of the at least one location trajectory is a partial compression based, at least in part, on the one or more intermediate intersections, the one or more intermediate roads, or a combination thereof.

11. An apparatus of claim 10, wherein the apparatus is further caused to:

determine a total number of outgoing roads of at least one intersection of the one or more intersections;

cause, at least in part, a selection of a number of the outgoing roads for the at least one intersection; and

determine the at least one compression key based, at least in part, on the number of the selected outgoing roads.

12. An apparatus of claim 11, wherein the number of the selected outgoing roads is one less than the total number of outgoing roads.

13. An apparatus of claim 11, wherein the selected outgoing roads are selected randomly.

14. An apparatus of claim 11, wherein the apparatus is further caused to:

determine an intended anonymity level associated with the compression of the at least one location trajectory; and

cause, at least in part, a modification of the at least one compression key based, at least in part, on including one or more roads associated with above a threshold number of outgoing roads,

wherein the at least one location trajectory contains historical location information.

15. An apparatus of claim 10, wherein the apparatus is further caused to:

determine one or more roads associated with the at least one location trajectory; and

cause, at least in part, a removal of at least one road associated with the at least one location trajectory if the at least one road is excluded within the at least one compression key to compress the at least one location trajectory.

16. An apparatus of claim 10, wherein the apparatus is further caused to:

determine whether one or more of the outgoing roads are common outgoing roads based, at least in part, on context information associated with the user, user profile information, user preference information, or a combination thereof; and

determine the at least one compression key based, at least in part, on one or more common outgoing roads.

17. An apparatus of claim 16, wherein the apparatus is further caused to:

cause, at least in part, a monitoring of context information associated with the user to determine one or more changes to the one or more common outgoing roads; and

determine one or more other compression keys based, at least in part, on the one or more changes.

18. An apparatus of claim 17, wherein the apparatus is further caused to:

cause, at least in part, a storing of the at least one compression key and the one or more other compression keys.