Depersonalizing location traces

• US 8,463,289 B2
• Filed: 06/17/2011
• Issued: 06/11/2013
• Est. Priority Date: 06/17/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shklarski, Gil, Beckman, Brian, Ofek, Eyal, Cartier, Kenn Daniel, Herzog, Shai, Kimchi, Gur, Johnston, Bernard Lawrence
• Primary Examiner(s): Magloire, Vladimir
• Application Number:
  US13/163,396
• Publication Number:
  US 20120322458A1
• Time in Patent Office: 725 Days
• Field of Search: 4554561-4566, 455/457
• US Class Current: 455/456.1
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 88/08 Access point devices

Abstract

Positional information is provided while minimizing the possibility that personally identifiable information can be derived therefrom. Positional information is received in the form of trails that can be aggregated. Individual cells of a grid reflect a quantity of aggregated trails through those cells, an average intensity and direction of movement through those cells, or a more detailed distribution thereof. Alternatively, individual trails are aggregated to an aggregated trail in the form of a line. Further obfuscation of personally identifiable information occurs by resampling aggregated positional information, by introducing false positional information, or by falsely modifying existing positional information, in a manner that does not impact the overall aggregations, and by pruning, or deleting, positional information, especially around sensitive locations, such as a user'"'"'s home, place of business, or other location that users typically would seek to keep private. Provision of positional information is delayed until a sufficient amount is received.

Claims

1. One or more computer-readable memory comprising computer-executable instructions for removing personally identifiable information from user trails, the computer-executable instructions directed to steps comprising:

receiving a first user trail comprising a first set of discrete locations of a first computing device, the first user trail having personally identifiable information;

modifying the first user trail to generate a new first user trail without the personally identifiable information by removing the personally identifiable information by performing at least one of;

replacing a turn in the first user trail with a sequence of equivalent turns, each of which differs from the identified turn, the sequence of equivalent turns having, in aggregate, a same starting point as the replaced turn and a same ending point as the replaced turn;

replacing at least one segment of the first user trail, the at least one segment being less than the whole first user trail, with one or more segments differing from the replaced at least one segment, the one or more segments having a same starting point as the replaced at least one segment and a same ending point as the replaced at least one segment;

dividing the first user trail into two or more sub-trails and identifying at least one of the two or more sub-trails as having been generated by a different computing device; and

exchanging a portion of the first user trail with a portion of a second user trail intersecting with the first user trail, the exchanged portions of the first and second user trails having the intersection as an endpoint.

2. The computer-readable memory of claim 1, wherein the computer-executable instructions for modifying the first user trail further comprise computer-executable instructions for pruning the first user trail to remove trail segments within a predefined region around at least one of:

a sensitive location and a location particularly useful to the derivation of the personally identifiable information.

3. The computer-readable memory of claim 1, further comprising computer-executable instructions directed to receiving an indication of an area within which user trail information is desired;

wherein the replacing the turn and the replacing the at least one segment are only performed outside of the indicated area.

4. The computer-readable memory of claim 3, wherein the computer-executable instructions for modifying the first user trail further comprise computer-executable instructions for scrambling the first user trail with other user trails outside of the indicated area while maintaining unchanged those segments of the first user trail inside of the indicated area.

5. The computer-readable memory of claim 1, wherein the dividing the first user trail into two or more sub-trails further comprises discarding at least one of the two or more sub-trails to prevent subsequent recombination of the two or more sub-trails into the first user trail.

6. The computer-readable memory of claim 1, wherein the dividing the first user trail into two or more sub-trails further comprises modifying timestamps of ones of the discrete locations that are part of at least one of the two or more sub-trails to prevent subsequent recombination of the two or more sub-trails into the first user trail.

7. The computer-readable memory of claim 1, comprising further computer-executable instructions for:

generating an aggregated trail comprising the new first user trail by aggregating the new first user trail with other user trails and providing access to the aggregated trail to a third party.

8. The computer-readable memory of claim 7, wherein the computer-executable instructions for generating the aggregated trail further comprise computer executable instructions for:

defining a grid comprising grid cells through which the new first user trail and the other user trails pass, generating an indicator for individual ones of the grid cells signifying a quantity of the new first user trail and the other user trails that pass through the individual ones of the grid cells.

9. The computer-readable memory of claim 7, wherein the computer-executable instructions for generating the aggregated trail further comprise computer executable instructions for:

generating a segment between a first point on the new first user trail and a second point on a first aggregated trail comprising an aggregation of at least some of the other user trails, identifying an average point on the generated segment representing a weighted average between the first point and the second point; and

modifying the first aggregated trail to pass through the average point.

10. The computer-readable memory of claim 7, comprising further computer-executable instructions for:

applying at least one of;

a resampling and a re-resolutioning to the aggregated trail to further remove the personally identifiable information prior to providing access to the aggregated trail.

11. The computer-readable memory of claim 7, comprising further computer-executable instructions for:

delaying the providing access to the aggregated trail until the other user trails are of a sufficient quantity to remove the personally identifiable information.

12. One or more computer-readable memory comprising computer-executable instructions for removing personally identifiable information from user trails, the computer-executable instructions directed to steps comprising:

receiving a first user trail comprising a first set of discrete locations of a first computing device, the first user trail having personally identifiable information;

receiving at least two other user trails; and

generating an aggregated trail by aggregating the first user trail with the at least two other user trails by performing at least one of;

defining a grid comprising grid cells through which the first user trail and the at least two other user trails pass and generating an indicator for individual ones of the grid cells signifying a quantity of the first user trail and the at least two other user trails that pass through the individual ones of the grid cells; and

generating a segment between a first point on the first user trail and a second point on a first aggregated trail comprising an aggregation of the at least two other user trails, identifying an average point on the generated segment representing a weighted average between the first point and the second point; and

modifying the first aggregated trail to pass through the average point.

13. The computer-readable memory of claim 12, wherein the generating the indicator for the individual ones of the grid cells comprises generating a vector for individual ones of the grid cells identifying an average direction of motion of the first user trail and the at least two other user trails that pass through the individual ones of the grid cells.

14. The computer-readable memory of claim 13, wherein the generating the vector for the individual ones of the grid cells comprises generating multiple time-dependent vectors for each of the individual ones of the grid cells, the multiple time-dependent vectors identifying the average direction of motion of the first user trail and the at least two other user trails that pass through the individual ones of the grid cells during pre-defined time intervals associated with the multiple time-dependent vectors.

15. The computer-readable memory of claim 14, comprising further computer-executable instructions for applying a random time adjustment to timestamps in the first user trail and the at least two other user trails.

16. The computer-readable memory of claim 12, wherein the generating the indicator for the individual ones of the grid cells comprises generating statistical distributions, for individual ones of the grid cells, the statistical distributions representing a direction of motion of the first user trail and the at least two other user trails that pass through the individual ones of the grid cells.

17. The computer-readable memory of claim 12, wherein the first point on the first user trail is a location point corresponding to one of the discrete locations, and the second point on the first aggregated trail is a point, on the first aggregated trail, that is closest to the first point.

18. The computer-readable memory of claim 12, comprising further computer-executable instructions for tessellating the first aggregated trail;

and wherein the second point on the first aggregated trail is a point on the first aggregated trail at which the first aggregated trail was tessellated, the segment is orthogonal to a tessellated segment of the first aggregated trail at the second point and the first point on the first user trail is a point on the first user trail at which the segment intersects the first user trail.

19. The computer-readable memory of claim 12, comprising further computer-executable instructions for:

applying at least one of;

a resampling and a re-resolutioning to the aggregated trail to further remove the personally identifiable information prior to providing access to the aggregated trail.

20. A method for removing personally identifiable information from user trails, the method comprising the steps of:

receiving a first user trail comprising a first set of discrete locations of a first computing device, the first user trail having personally identifiable information;

modifying the first user trail to generate a new first user trail without the personally identifiable information by removing the personally identifiable information by performing at least one of;

replacing a turn in the first user trail with a sequence of equivalent turns, each of which differs from the identified turn, the sequence of equivalent turns having, in aggregate, a same starting point as the replaced turn and a same ending point as the replaced turn;

replacing at least one segment of the first user trail, the at least one segment being less than the whole first user trail, with one or more segments differing from the replaced at least one segment, the one or more segments having a same starting point as the replaced at least one segment and a same ending point as the replaced at least one segment;

dividing the first user trail into two or more sub-trails and identifying at least one of the two or more sub-trails as having been generated by a different computing device; and

exchanging a portion of the first user trail with a portion of a second user trail intersecting with the first user trail, the exchanged portions of the first and second user trails having the intersection as an endpoint.