Privacy risk metrics in location based services

Patent metadata

Field	Value
Publication number	US-9547845-B2
Application number	US-201313921750-A
Country	US
Kind code	B2
Filing date	Jun 19, 2013
Priority date	Jun 19, 2013
Publication date	Jan 17, 2017
Grant date	Jan 17, 2017

Abstract

The present disclosure relates generally to mechanisms for the estimation of location privacy risk, comprising: building one or more trajectory models from auxiliary information (e.g., one or more maps, one or more routes); capturing common behavioral patterns (e.g., shortest route(s),/fastest route(s)); identifying, given unlinked trajectories for a plurality of users, most likely linkages using the trajectory model(s); eliminating one or more unlikely linkages based on deviation from the shortest route(s) and/or the fastest route(s); measuring privacy as the percentage of linkages correctly identified; and outputting the measured privacy.

First claim

What is claimed is:

1. A method implemented in a computer system for estimating location privacy risk to a plurality of people, the method comprising:
building, with the computer, at least one trajectory model;
obtaining, with the computer, at least one behavioral pattern associated with the plurality of people;
obtaining, with the computer, a plurality of unlinked trajectories associated with the plurality of people, wherein the plurality of unlinked trajectories span across a plurality of mix-zones;
identifying with the computer, based upon the plurality of unlinked trajectories, a plurality of linkages by using the trajectory model;
indicating, with the computer, as unlikely at least one of the linkages based upon deviation from the behavior pattern;
measuring, with the computer, privacy as a percentage of the number of the linkages indicated as unlikely relative to the number of identified linkages; and
outputting, with the computer, the measured privacy;
wherein the number of unlinked trajectories equals the number of people times the number of mix-zones.

2. The method of claim 1 , wherein the trajectory model is built based upon at least one of: (a) one or more maps; (b) one or more routes; and (c) any combination thereof.

3. The method of claim 1 , comprising building, with the computer, a plurality of trajectory models, wherein the identifying is performed by using the plurality of trajectory models.

4. The method of claim 1 , wherein the behavioral pattern comprises at least one of: (a) one or more shortest routes; (b) one or more fastest routes; and (c) any combination thereof.

5. The method of claim 4 , wherein the indicating comprises indicating as unlikely at least one of the linkages based on deviation from at least one of: (a) a shortest route; (b) a fastest route; and (c) any combination thereof.

6. The method of claim 1 , comprising obtaining, with the computer, a plurality of behavioral patterns, wherein the indicating is performed by using the plurality of behavioral patterns.

7. The method of claim 1 , wherein at least one of the linkages is indicated as unlikely based on the deviation from the behavior pattern being above a threshold.

8. The method of claim 1 , wherein the outputting comprises at least one of: (a) an output to a computer monitor; (b) an output to a computer file; (c) a hardcopy output; and (d) any combination thereof.

9. A computer readable storage medium, tangibly embodying a program of instructions executable by the computer for estimating location privacy risk to a plurality of people, the program of instructions, when executing, performing the following steps:
building at least one trajectory model;
obtaining at least one behavioral pattern associated with the plurality of people;
obtaining a plurality of unlinked trajectories associated with the plurality of people, wherein the plurality of unlinked trajectories span across a plurality of mix-zones;
identifying, based upon the plurality of unlinked trajectories, a plurality of linkages by using the trajectory model;
indicating as unlikely at least one of the linkages based upon deviation from the behavior pattern;
measuring privacy as a percentage of the number of the linkages indicated as unlikely relative to the number of identified linkages; and
outputting the measured privacy;
wherein the number of unlinked trajectories equals the number of people times the number of mix-zones.

10. The computer readable storage medium of claim 9 , wherein the trajectory model is built based upon at least one of: (a) one or more maps; (b) one or more routes; and (c) any combination thereof.

11. The computer readable storage medium of claim 9 , wherein the program of instructions, when executing, further performs building a plurality of trajectory models, wherein the identifying is performed by using the plurality of trajectory models.

12. The computer readable storage medium of claim 9 , wherein the behavioral pattern comprises at least one of: (a) one or more shortest routes; (b) one or more fastest routes; and (c) any combination thereof.

13. The computer readable storage medium of claim 12 , wherein the indicating as unlikely comprises indicating at least one of the linkages based on deviation from at least one of: (a) a shortest route; (b) a fastest route; and (c) any combination thereof.

14. The computer readable storage medium of claim 9 , wherein the program of instructions, when executing, further performs obtaining a plurality of behavioral patterns, wherein the indicating is performed by using the plurality of behavioral patterns.

15. A computer-implemented system for estimating location privacy risk to a plurality of people, the system comprising:
a building element configured to build at least one trajectory model;
a first obtaining element configured to obtain at least one behavioral pattern associated with the plurality of people;
a second obtaining element configured to obtain a plurality of unlinked trajectories associated with the plurality of people, wherein the plurality of unlinked trajectories span across a plurality of mix-zones;
an identifying element configured to identify, based upon the plurality of unlinked trajectories, a plurality of linkages by using the trajectory model;
an indicating element configured to indicate as unlikely at least one of the linkages based upon deviation from the behavior pattern;
a measuring element configured to measure privacy as a percentage of the number of the linkages indicated as unlikely relative to the number of identified linkages; and
an outputting element configured to output the measured privacy;
wherein the number of unlinked trajectories equals the number of people times the number of mix-zones.

16. The system of claim 15 , wherein the trajectory model is built based upon at least one of: (a) one or more maps; (b) one or more routes; and (c) any combination thereof.

17. The system of claim 15 , wherein the building element is configured to build a plurality of trajectory models, wherein the identifying is performed by using the plurality of trajectory models.

18. The system of claim 15 , wherein the behavioral pattern comprises at least one of: (a) one or more shortest routes; (b) one or more fastest routes; and (c) any combination thereof.

19. The system of claim 15 , wherein the indicating element is configured to indicate at least one of the linkages as unlikely based on deviation from at least one of: (a) a shortest route; (b) a fastest route; and (c) any combination thereof.

Assignees

• IBM

Inventors

• Agrawal Dakshi
• Ganti Raghu K
• Srivatsa Mudhakar
• Wang Jingjing

Classifications

• G06N7/01 Primary

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06Q10/107 Primary

  Computer-aided management of electronic mailing [e-mailing] · CPC title

• G06F21/00

  Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity · CPC title

• H04L63/04

  for providing a confidential data exchange among entities communicating through data packet networks · CPC title

• H04W12/02

  Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII] · CPC title