Anonymization of geographic route trace data

Patent metadata

Field	Value
Publication number	US-10664616-B2
Application number	US-201815925755-A
Country	US
Kind code	B2
Filing date	Mar 19, 2018
Priority date	Mar 20, 2017
Publication date	May 26, 2020
Grant date	May 26, 2020

Abstract

A trace comprising location data about a computing device is received at a mapping server, where the trace stores the location data about the computing device in an ordered set of points. The origin and destination of the trace are obscured. Then, the trace is then separated into a set of subtraces by dividing the received points of location data into a set of subtraces, and removing the links between subtraces of the set of subtraces. For example, subtraces can be divided based on size, distance, elapsed time, or features of interest present in the location data.

First claim

What is claimed is:

1. A method comprising:
receiving, at a mapping server from a client device, a first trace comprising a set of location data, the location data comprising an origin point, a plurality of intermediate points, and a destination point in an ordered sequence, wherein the first trace comprises identifying information associated with the client device; and
anonymizing the first trace by:
selecting, at the mapping server, an origin section for the first trace, the origin section comprising the origin point and one or more intermediate points;
removing the origin section from the first trace;
selecting, at the mapping server, a destination section for the first trace, the destination section comprising the destination point and one or more intermediate points;
removing the destination section from the first trace; and
dividing, at the mapping server, the first trace into a plurality of subtraces, each subtrace comprising a plurality of consecutive intermediate points of the location data.

2. The method of claim 1 , wherein anonymizing the first trace further comprises:
removing, from each subtrace, location data connecting the subtrace to any other subtraces of the set of subtraces; and
storing, by the mapping server, each subtrace independently of each other subtrace in the set of subtraces.

3. The method of claim 1 , wherein removing, from each subtrace, location data connecting the subtrace to any other subtraces of the set of subtraces further comprises:
selecting, at the mapping server, an origin section for a first subtrace of the set of subtraces;
removing the origin section from the first subtrace;
selecting, at the mapping server, a destination section for the first subtrace; and
removing the destination section from the first subtrace.

4. The method of claim 1 , wherein dividing the first trace into a set of subtraces comprises randomly selecting a size for each subtrace of the set of subtraces.

5. The method of claim 4 , wherein the size of a subtrace is determined based on a measure of the time or distance associated with the subtrace.

6. The method of claim 1 , wherein anonymizing the first trace further comprises:
determining one or more features of interest in the first trace, each feature of interest associated with one or more intermediate points of the first trace;
and wherein dividing the first trace into a set of subtraces is based on the one or more features of interest.

7. The method of claim 1 , wherein each subtrace of the set of subtraces includes one or more intermediate points associated with a feature of interest.

8. The method of claim 1 , wherein each subtrace of the set of subtraces is a predetermined size.

9. The method of claim 1 , wherein selecting an origin section for the first trace further comprises:
determining a random size of the origin section.

10. The method of claim 1 , wherein the first trace comprises device metadata identifying the computing device and wherein anonymizing the first trace further comprises:
removing, at the mapping server from the first trace, the device metadata.

11. The method of claim 10 , wherein the device metadata is a device identifier of the computing device.

12. The method of claim 1 , further comprising:
receiving, at a mapping server from a client device, a plurality of traces, each trace comprising a set of location data, each set of location data comprising an origin point, a plurality of intermediate points, and a destination point in an ordered sequence;
selecting, at the mapping server, an origin section for each trace of the plurality of traces, the origin section for a trace comprising the origin point and one or more intermediate points of that trace;
removing, from each trace of the plurality of traces, the origin section;
selecting, at the mapping server, a destination section for each trace of the plurality of traces, the destination section comprising the destination point and one or more intermediate points of that trace;
removing, from each trace of the plurality of traces, the destination section; and
dividing, at the mapping server, each trace of the plurality of traces into a second plurality of subtraces, each subtrace comprising a plurality of consecutive intermediate points of the location data.

13. The method of claim 1 , further comprising:
storing, by the mapping server, each subtrace of the plurality of subtraces and the second plurality of subtraces independently of each other subtrace in the set of subtraces; and
aggregating the plurality of subtraces and the second plurality of subtraces into aggregated telemetry data.

14. The method of claim 1 , wherein dividing the first trace into a plurality of subtraces comprises dividing the first trace into a plurality of subtraces based on measures of times or distances associated with the plurality of subtraces.

15. A non-transitory computer readable storage medium comprising instructions which, when executed by a processor, cause the processor to perform the steps of:
receiving, at a mapping server from a client device, a first trace comprising a set of location data, the location data comprising an origin point, a plurality of intermediate points, and a destination point in an ordered sequence, wherein the first trace comprises identifying information associated with the client device; and
anonymizing the first trace by:
selecting, at the mapping server, an origin section for the first trace, the origin section comprising the origin point and one or more intermediate points;
removing the origin section from the first trace;
selecting, at the mapping server, a destination section for the first trace, the destination section comprising the destination point and one or more intermediate points;
removing the destination section from the first trace; and
dividing, at the mapping server, the first trace into a plurality of subtraces, each subtrace comprising a plurality of consecutive intermediate points of the location data.

16. The non-transitory computer readable storage medium of claim 15 , wherein anonymizing the first trace further comprises:
removing, from each subtrace, location data connecting the subtrace to any other subtraces of the set of subtraces; and
storing, by the mapping server, each subtrace independently of each other subtrace in the set of subtraces.

17. The non-transitory computer readable storage medium of claim 15 , wherein dividing the first trace into a set of subtraces comprises randomly selecting a size for each subtrace of the set of subtraces.

18. The non-transitory computer readable storage medium of claim 15 , wherein anonymizing the first trace further comprises:
determining one or more features of interest in the first trace, each feature of interest associated with one or more intermediate points of the first trace;
and wherein dividing the first trace into a set of subtraces is based on the one or more features of interest.

19. The non-transitory computer readable storage medium of claim 15 , wherein each subtrace of the set of subtraces is a predetermined size.

20. The non-transitory computer readable storage medium of claim 15 , wherein dividing the first trace into a plurality of subtraces comprises dividing the first trace into a plurality of subtraces based on measures of times or distances associated with the plurality of subtraces.

Assignees

• Mapbox Inc

Inventors

• Herlocker Morgan
• Rochon Laurier
• Thompson David Michael

Classifications

• G06F21/6254 Primary

  by anonymising data, e.g. decorrelating personal data from the owner's identification · CPC title

• G01S5/0027

  of actual mobile position, i.e. position determined on mobile · CPC title

• G01S19/42

  Determining position · CPC title

• G01C21/34

  Route searching; Route guidance · CPC title

• G01S19/13

  Receivers · CPC title