Map matched aggregation for K-anonymity in trajectory data

Patent metadata

Field	Value
Publication number	US-10663305-B2
Application number	US-201816036128-A
Country	US
Kind code	B2
Filing date	Jul 16, 2018
Priority date	Jul 16, 2018
Publication date	May 26, 2020
Grant date	May 26, 2020

Abstract

An apparatus for providing anonymity in geographic data for probe devices in a geographic region for a location-based service includes at least a database, a map matcher, and an aggregation calculator. The database is configured to store trajectory data based on sequences of sensor measurements of the probe devices. The map matcher is configured to match a map, including cells, with the trajectory data, and each of the cells includes edges and a face. The aggregation calculator configured to calculate a number of trajectories in the trajectory data that passes through each of the edges and compare the number of trajectories in the trajectory data for at least one of the edges to a threshold. The geographic data is modified in response to the comparison of the number of trajectories in the trajectory data for the at least one of the edges.

First claim

I claim:

1. A method for providing anonymity in geographic data for probe devices in a geographic region for a location-based service, the method comprising:
receiving trajectory data based on sequences of sensor measurements of the probe devices;
generating, by a processor, data representing a map of initial geographic data using a plurality of cells, wherein each of the plurality of cells includes a plurality of edges and a face;
map matching the trajectory data to the plurality of cells;
calculating, by the processor, a number of trajectories in the trajectory data that passes through each of the plurality of edges;
performing, by the processor, a comparison of the number of trajectories in the trajectory data for at least one of the plurality of edges to a threshold;
modifying and filtering, by the processor, the geographic data in response to the comparison of the number of trajectories in the trajectory data for the at least one of the plurality of edges; and outputting, anonymized trajectory data to an external service.

2. The method of claim 1 , wherein the map matching further comprises:
assigning at least one point from the trajectory data to a road link.

3. The method of claim 2 , wherein the road link is a first road link, the method further comprising:
calculating a first probability for the trajectory data and the first road link;
assigning at least one point from the trajectory data to a second road link;
calculating a second probability for the trajectory data and the second road link; and
comparing the first probability and the second probability.

4. The method of claim 2 , wherein modifying and filtering the trajectory data in response to the comparison further comprises:
removing the road link from the geographic data in response to the comparison of the number of trajectories in the trajectory data for the at least one of the plurality of edges.

5. The method of claim 4 , further comprising:
identifying an adjacent road link closest to the removed road link; and
assigning at least one point from the removed road link to the adjacent road link.

6. The method of claim 1 , further comprising:
identifying a plurality of segments for the trajectory data; and
selecting one point from each of the plurality of segments.

7. The method of claim 1 , further comprising:
sorting the trajectory data according to timestamp; and
filtering the trajectory data to the face that includes at least one point of the trajectory data.

8. The method of claim 1 , wherein the anonymized trajectory data includes a list of links for the modified geographic data including fewer links than the map of the initial geographic data.

9. An apparatus for providing anonymity in geographic data for probe devices in a geographic region for a location-based service, the apparatus comprising:
a database configured to store trajectory data based on sequences of sensor measurements of the probe devices;
a map matcher configured to match a map, including a plurality of cells, with the trajectory data, wherein each of the plurality of cells includes a plurality of edges and a face;
an aggregation calculator configured to calculate a number of trajectories in the trajectory data that passes through each of the plurality of edges and compare the number of trajectories in the trajectory data for at least one of the plurality of edges to a threshold,
wherein the geographic data is modified and filtered in response to the comparison of the number of trajectories in the trajectory data for the at least one of the plurality of edges; and an anonymization controller to provide anonymized data representing the trajectory data to one or more external service or external device.

10. The apparatus of claim 9 , wherein the map matcher is configured to assign at least a first point from the trajectory data to a first road link and assign at least a second point from the trajectory data to a second road link, and wherein the map matcher is configured perform a comparison a first probability for the at least the first point and the first road link with a second probability for the at least the second point and the second road link,
wherein the trajectory data is matched to the map based on the comparison.

11. The apparatus of claim 9 , wherein aggregation controller is configured to remove a road link from the geographic data in response to the comparison of the number of trajectories in the trajectory data for the at least one of the plurality of edges.

12. The apparatus of claim 11 , wherein the aggregation calculator is configured to identify an adjacent road link closest to the removed road link and assign at least one point from the removed road link to the adjacent road link.

13. The apparatus of claim 9 , wherein the aggregation calculator is configured to identify a plurality of segments for the trajectory data and select one point from each of the plurality of segments.

14. The apparatus of claim 9 , the aggregation calculator is configured to sort the trajectory data according to timestamp and filter the trajectory data to the face that includes at least one point of the trajectory data.

15. A non-transitory computer readable medium including instructions that when executed by a processor are configured to perform:
map matching trajectory data to a plurality of road segments in a subset of map data;
calculating a number of trajectories in the trajectory data that passes through each of the plurality of road segments;
performing a comparison of the number of trajectories in the trajectory data for at least one of the plurality of road segments to a threshold;
modifying and filtering the subset of map data in response to the comparison of the number of trajectories in the trajectory data for the at least one of the plurality of road segments to the threshold; and outputting anonymized trajectory data to an external service.

16. The non-transitory computer readable medium of claim 15 , the instructions further configured to perform:
assigning at least one point from the trajectory data to a first road segment;
calculating a first probability for the trajectory data and the first road segment;
assigning at least one point from the trajectory data to a second road segment;
calculating a second probability for the trajectory data and the second road segment; and
comparing the first probability and the second probability.

17. The non-transitory computer readable medium of claim 15 , wherein modifying and filtering the subset of map data further comprises:
removing a road segment from the subset of map data in response to the comparison of the number of trajectories in the trajectory data for the at least one of the plurality of road segments to the threshold.

18. The non-transitory computer readable medium of claim 17 , the instructions further configured to perform:
identifying an adjacent road segment closest to the removed road segment; and
assigning at least one point from the removed road segment to the adjacent road segment.

Assignees

• Here Global Bv

Inventors

• Balu Raghavendran

Classifications

• H04L63/0421

  Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer · CPC title

• G06F16/29 Primary

  Geographical information databases · CPC title

• G08G1/065

  by counting the vehicles in a section of the road or in a parking area, i.e. comparing incoming count with outgoing count · CPC title

• G01C21/32 Primary

  Structuring or formatting of map data · CPC title

• G01C21/3841

  Data obtained from two or more sources, e.g. probe vehicles · CPC title