Method and apparatus for discovering social ties based on cloaked trajectories

1. A method, comprising:

transforming cloaked regions of a first trajectory of a first user and cloaked regions of a second trajectory of a second user to corresponding semantic regions, respectively, wherein a semantic region is expressed with a semantic meaning of a corresponding cloaked region;

mapping the semantic regions to nodes of a hierarchical semantic tree, wherein each node of the hierarchical semantic tree corresponds to a semantic region; and

determining that a social tie exists between the first user and the second user based on relationships between nodes mapped to semantic regions of the first trajectory and nodes mapped to semantic regions of the second trajectory.

2. A method of claim 1 , wherein the social tie between the first user and the second user comprises a social relationship between the first user and the second user, and wherein transforming the cloaked regions to the corresponding semantic regions comprises:

selecting more than one sample location in a cloaked region of the cloaked regions;

deriving semantic meanings associated to each of the more than one sample locations; and

concluding the semantic region of the cloaked region from the semantic meaning associated to the each of the more than one sample locations.

3. A method of claim 2 , wherein the concluding the semantic region of the cloaked region comprises:

selecting a semantic region which has a semantic meaning covering all of the semantic meanings associated to the more than one sample locations, as the semantic region of the cloaked region.

4. A method of claim 2 , wherein a semantic meaning associated to a sample location is derived by a reverse geocoding based on geographic coordinates of the sample location.

5. A method of claim 1 , further comprising:

identifying the semantic regions on the first trajectory and the second trajectory, which occurred within a same time period, as pair regions;

computing similarities between nodes mapped to the semantic regions of each pair of identified pair regions; and

deducing a similarity between the first trajectory and the second trajectory from the computed similarities.

6. A method of claim 5 , wherein the computed similarities between the nodes mapped to the semantic regions of one pair of the identified pair regions are computed based on factors in at least one of the following three aspects:

a level of lowest common ancestor node of the nodes mapped to the semantic regions of the one pair of the pair regions in the hierarchical semantic tree;

a shortest length path between the nodes mapped to the semantic regions of the one pair of the pair regions in the hierarchical tree; and

a level of a node mapped to the semantic regions of the one pair of the pair regions in the hierarchical tree.

7. A method of claim 1 , wherein the cloaked regions of the first trajectory and the cloaked regions of the second trajectory are cloaked through a k-anonymity algorithm according to different privacy levels.

8. An apparatus comprising:

at least one processor; and

at least one memory including computer program code,

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

transform cloaked regions of a first trajectory of a first user and cloaked regions of a second trajectory of a second user to corresponding semantic regions, respectively, wherein a semantic region is expressed with a semantic meaning of a corresponding cloaked region;

map the transformed semantic regions to nodes of a hierarchical semantic tree, wherein each node of the hierarchical semantic tree corresponds to a semantic region; and

determine that a social tie exists between the first user and the second user based on relationships between nodes mapped to semantic regions of the first trajectory and nodes mapped to semantic regions of the second trajectory.

9. An apparatus of claim 8 , wherein the social tie between the first user and the second user comprises a social relationship between the first user and the second user, and wherein to transform the cloaked regions to the corresponding semantic regions, the apparatus is further caused to at least:

select more than one sample location in a cloaked region of the cloaked regions;

derive semantic meanings associated to each of the more than one sample locations; and

conclude the semantic region of the cloaked region from the semantic meanings associated to the each of the more than one sample locations.

10. An apparatus of claim 9 , wherein to conclude the semantic region of the cloaked region, the apparatus is further caused to at least:

select a semantic region which has a semantic meaning covering all of the semantic meanings associated to the more than one sample locations, as the semantic region of the cloaked region.

11. An apparatus of claim 9 , wherein a semantic meaning associated to a sample location is derived by a reverse geocoding based on geographic coordinates of the sample location.

12. An apparatus of claim 8 , wherein the apparatus is further caused to at least:

identify the semantic regions on the first trajectory and the second trajectory, which occurred within a same time period, as pair regions;

compute similarities between the nodes mapped to semantic regions of each pair of identified pair regions; and

deduce a similarity between the first trajectory and the second trajectory from the computed similarities.

13. An apparatus of claim 12 , wherein the computed similarities between the nodes mapped to the semantic regions of one pair of the identified pair regions are computed based on factors in at least one of the following three aspects:

a level of the lowest common ancestor node of the nodes mapped to the semantic regions of the one pair of the pair regions in the hierarchical semantic tree;

the shortest length path between the nodes mapped to the semantic regions of the one pair of pair regions in the hierarchical tree; and

a level of a node mapped to the semantic regions of the one pair of the pair regions in the hierarchical tree.

14. An apparatus of claim 8 , wherein the cloaked regions of the first trajectory and the cloaked regions of the second trajectory are cloaked through a k-anonymity algorithm according to different privacy levels.

15. A non-transitory computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, causing an apparatus to:

transform cloaked regions of a first trajectory of a first user and cloaked regions of a second trajectory of a second user to corresponding semantic regions, respectively, wherein a semantic region is expressed with a semantic meaning of a corresponding cloaked region;

map the semantic regions to nodes of a hierarchical semantic tree, wherein each node of the hierarchical semantic tree corresponds to a semantic region; and

determine that a social tie exists between the first user and the second user based on relationships between nodes mapped to semantic regions of the first trajectory and nodes mapped to semantic regions of the second trajectory.

16. The non-transitory computer-readable storage medium of claim 15 , when executed by one or more processors, causing the apparatus to transform the cloaked regions to a corresponding semantic region further comprises:

select more than one sample location in a cloaked region of the cloaked regions;

derive semantic meanings associated to each of the more than one sample locations; and

conclude the semantic region of the cloaked region from the semantic meanings associated to the each of the more than one sample locations.

17. The non-transitory computer-readable storage medium of claim 16 , when executed by one or more processors, causing the apparatus to conclude the semantic region of the cloaked region further comprises, select a semantic region which has a semantic meaning covering all of the semantic meanings associated to the more than one sample locations, as the semantic region of the cloaked region.

18. The non-transitory computer-readable storage medium of claim 16 , when executed by one or more processors, causing the apparatus further to derive the semantic meaning associated to a sample location a reverse geocoding based on geographic coordinates of the sample location.

19. The non-transitory computer-readable storage medium of claim 15 , when executed by one or more processors, causing the apparatus further to:

identify the semantic regions on the first trajectory and the second trajectory, which occurred within a same time period, as pair regions;

compute similarities between nodes mapped to the semantic regions of each pair of identified pair regions; and

deduce a similarity between the first trajectory and the second trajectory from the computed similarities.

20. The non-transitory computer-readable storage medium of claim 19 , when executed by one or more processors, causing the apparatus further to compute similarities between the nodes mapped to the semantic regions of one pair of the identified pair regions based on factors in at least one of the following three aspects:

a level of lowest common ancestor node of the nodes mapped to the semantic regions of the one pair of the pair regions in the hierarchical semantic tree;

a shortest length path between the nodes mapped to the semantic regions of the one pair of the pair regions in the hierarchical tree; and

a level of a node mapped to the semantic regions of the one pair of the pair regions in the hierarchical tree.