Device location history anonymization based on stop detection

• US 9,491,616 B2
• Filed: 10/06/2015
• Issued: 11/08/2016
• Est. Priority Date: 09/18/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Brandt, Eli, Zelinka, Stephen David
• Primary Examiner(s): DOAN, KIET M
• Application Number:
  US14/876,478
• Publication Number:
  US 20160029212A1
• Time in Patent Office: 399 Days
• Field of Search: 455/456.2, 455/456.5, 455/456.3, 455/456.1, 455/411, 455/406, 455/418, 370/252, 370/312, 701/418, 386/230
• US Class Current: 1/1
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 2221/2151 Time stamp
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/027 using movement velocity, acceleration information
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 8/16 selectively restricting mobility data tracking

Abstract

Embodiments described herein may help to protect users'"'"' privacy when storing and/or utilizing location data that is provided by the users'"'"' mobile devices. An example method may involve: (a) determining a location history associated with a first client device, wherein the location history comprises a plurality of time-stamped location reports associated with the first client device, (b) before the location history is exported: (i) identifying at least one stop in the location history, wherein the at least one stop corresponds to a plurality of location reports that indicate a substantial lack of movement by the first client device, and (ii) scrubbing the location history in order to obscure at least one location report that corresponds to the at least one stop, and (c) exporting the scrubbed location history to long-term data storage.

Claims

1. A method comprising:

determining, by a computing device, a location history associated with a first client device, wherein the location history comprises a plurality of time-stamped location reports associated with the first client device;

before the location history is exported, the computing device;

analyzing the location history for any stop that exists within the location history, wherein any group of location reports indicating no movement or movement of less than a threshold distance within a predetermined period of time is defined as a stop;

based on the analysis, detecting all stops that exist in the location history, wherein at least one stop is detected; and

scrubbing the location history in order to obscure at least one location report that corresponds to each detected stop; and

exporting the scrubbed location history to long-term data storage.

2. The method of claim 1, wherein each location report associated with the first client device comprises:

(a) a client-device identifier of the first client device and (b) location data indicative of a location of the first client device at a time of the location report.

3. The method of claim 1, wherein one or more of the location reports each comprise one or more of:

(a) GPS location data, (b) WiFi-based location data, and (c) cell-based location data.

4. The method of claim 1, wherein detecting any stops in the location history comprises, for each location report:

determining one or more subsequent location reports in the location history having a timestamp within a predetermined period of time from the timestamp for the location report;

determining a maximum distance between the location indicated by the location report and the one or more locations indicated by the one or more subsequent location reports;

determining whether or not the maximum distance is less than a threshold distance; and

associating the location report with either a stopped state or a moving state, wherein the association is based at least in part on whether or not the maximum distance is less than the threshold distance.

5. The method of claim 4, wherein associating the location report with either the stopped state or the moving state comprises:

if the maximum distance is less than the threshold distance, then associating the location report with the stopped state; and

if the maximum distance is greater than the threshold distance, then associating the location report with the moving state.

6. The method of claim 4, further comprising:

before associating the location report with either a stopped state or a moving state;

(a) determining a velocity corresponding to the location report, and (b) determining whether or not the velocity is less than a threshold velocity;

wherein associating the location report with either the stopped state or the moving state is further based on whether or not the velocity is less than the threshold velocity.

7. The method of claim 6, wherein associating the location report with either a stopped state or a moving state comprises:

if (a) the maximum distance is greater than the threshold distance or (b) the velocity is greater than the threshold velocity, then associating the location report with the moving state; and

otherwise, associating the location report with the stopped state.

8. The method of claim 1, further comprising, before the location history is exported:

determining a velocity corresponding to the location report;

determining whether or not the velocity is less than a threshold velocity; and

associating the location report with either a stopped state or a moving state, wherein the association is based at least in part on whether or not the velocity is less than the threshold velocity.

9. The method of claim 1, wherein each location report in the location history is associated with either a stopped state or a moving state, wherein detecting any stop in the location history comprises identifying one or more transitions in the location history, wherein each transition comprises consecutive location reports in the location history that correspond to different states, and wherein one of the consecutive location reports corresponds to the stopped state and another of the consecutive location reports corresponds to the moving state.

10. The method of claim 9, wherein scrubbing the location history comprises scrubbing the location history based at least in part on the one or more transitions in the location history.

11. The method of claim 10, wherein scrubbing the location history based at least in part on the one or more transitions comprises:

determining one or more location reports that indicate a location within a threshold distance from a stop location indicated by a first of the consecutive location reports; and

obscuring the one or more location reports that are within the threshold distance from the stop location.

12. The method of claim 10, wherein scrubbing the location history based at least in part on the one or more transitions comprises:

determining one or more location reports that have a timestamp within a threshold period of time from the timestamp of a first of the consecutive location reports; and

obscuring the one or more location reports that have a timestamp within the predetermined period of time from the timestamp of the first of the consecutive location reports.

13. The method of claim 1, wherein scrubbing the location history further comprises scrubbing the location history according to an implied-stop scrubbing policy.

14. The method of claim 1, wherein scrubbing the location history further comprises scrubbing the location history according to a prolonged-stop scrubbing policy.

15. The method of claim 1, wherein scrubbing the location history further comprises scrubbing the location history based at least in part on a measure of spatial privacy risk.

16. The method of claim 1, wherein scrubbing the location history further comprises adjusting parameters for scrubbing around each stop in the location history based on a type of location data included in a location report associated with the stop.

17. The method of claim 1, wherein scrubbing the location history further comprises:

analyzing the location history to detect any location jumps in the location history; and

scrubbing one or more location reports that are associated with each detected location jump.

18. The method of claim 1, further comprising initially applying a time-alignment process to the location reports in the location history.

19. The method of claim 1, wherein the location history is stored in short-term data storage before being exported, the method further comprising:

after exporting the scrubbed location history, deleting the location history from the short-term data storage.

20. The method of claim 1, wherein the short-term data storage is part of a quarantine system for location data.

21. The method of claim 1, wherein at least one location report corresponding to each detected stop is obscured regardless of the data size of the location history to be exported.

22. The method of claim 1, wherein scrubbing the location history comprises deleting all but one location report corresponding to each detected stop.

23. A non-transitory computer readable medium having stored therein instructions executable by a computing device to cause the computing device to perform functions comprising:

determining a location history associated with a first client device, wherein the location history comprises a plurality of time-stamped location reports associated with the first client device;

before the location history is exported;

analyzing the location history for any stop that exists within the location history, wherein any group of location reports indicating no movement or movement of less than a threshold distance within a predetermined period of time is defined as a stop;

based on the analysis, detecting any stops in the location history, wherein at least one stop is detected; and

scrubbing the location history in order to obscure at least one location report that corresponds to each detected stop; and

exporting the scrubbed location history to long-term data storage.

24. A system comprising:

one or more communication interfaces, wherein at least one communication interface is configured to receive location reports that are generated by a plurality of client devices, wherein received location reports are initially stored in a quarantine system;

a location-history module configured to determine, from the location reports stored in the quarantine system, a location history associated with a first client device, wherein the location history comprises a plurality of location reports that are associated with the first client device; and

a scrubber module configured to;

analyze the location history for any stops that exist in the location history, wherein any group of location reports indicating no movement or movement of less than a threshold distance within a predetermined period of time is defined as a stop;

movement by the first client device; and

based on the analysis, detect any stops in the location history; and

scrub the location history to obscure at least one location report that corresponds to each detected stop in the location history; and

export, via at least one of the one or more communication interfaces, the scrubbed location history to long-term data storage.