Privacy risk metrics in location based services

Patent metadata

Field	Value
Publication number	US-11151469-B2
Application number	US-201615375647-A
Country	US
Kind code	B2
Filing date	Dec 12, 2016
Priority date	Jun 19, 2013
Publication date	Oct 19, 2021
Grant date	Oct 19, 2021

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 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;
forming, with the computer, a weighted bipartite graph-matching problem using a weighted bipartite graph having vertices modeling ingress and egress pseudonyms based upon a plurality of unlinked trajectories associated with the plurality of people, wherein the plurality of unlinked trajectories comprises at least one of: shortest routes, fastest routes or combinations thereof spanning across a plurality of mix-zones and said edge weights assigned according to shortest path routing;
solving, with the computer, the weighted bipartite graph-matching problem to identify a plurality of linkages by using the trajectory model;
indicating, with the computer, as unlikely at least one of the plurality of 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
designing, using the computer, a road network to have one or more mix zones, each mix zone having entry points and exit points and a plurality of linkages that link entry points and exit points based on the measured privacy, each said plurality of linkages of a mix zone of the road network accounting for a person's ability to make right turns, a person's shortest path driving behavior, and a presence of a road intersection between a large road and a small road.

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 the number of unlinked trajectories equals the number of people times the number of mix-zones.

8. 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.

9. A non-transitory computer readable storage medium, tangibly embodying a program of instructions executable by the computer for estimating location privacy risk to a plurality 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;
forming a weighted bipartite graph-matching problem using a weighted bipartite graph having vertices modeling ingress and egress pseudonyms based upon a plurality of unlinked trajectories associated with the plurality of people, wherein the plurality of unlinked trajectories comprises at least one of: shortest routes, fastest routes and combinations thereof spanning across a plurality of mix-zones and said edge weights assigned according to shortest path routing;
solving the weighted bipartite graph-matching problem to identify a plurality of linkages by using the trajectory model;
indicating as unlikely at least one of the plurality of 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
designing a road network having one or more mix zones, each mix zone having entry points and exit points and a plurality of linkages that link entry points and exit points based on the measured privacy, each said plurality of linkages of a mix zone of the road network accounting for a person's ability to make right turns, a person's shortest path driving behavior, and a presence of a road intersection between a large road and a small road.

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 people, the system comprising:
a memory for storing instructions;
a hardware processor coupled to said memory for receiving said stored instructions and in response, configuring the hardware processor to;
build at least one trajectory model;
obtain at least one behavioral pattern associated with the plurality of people;
form a weighted bipartite graph-matching problem using a weighted bipartite graph having vertices modeling ingress and egress pseudonyms based upon a plurality of unlinked trajectories associated with the plurality of people, wherein the plurality of unlinked trajectories comprises at least one of: shortest routes, fastest routes and combinations thereof spanning across a plurality of mix-zones and said edge weights assigned according to shortest path routing;
solve the weighted bipartite graph-matching problem to identify a plurality of linkages by using the trajectory model;
indicate as unlikely at least one of the plurality of linkages based upon deviation from the behavior pattern;
measure privacy as a percentage of the number of the linkages indicated as unlikely relative to the number of identified linkages; and
design a road network having one or more mix zones, each mix zone having entry points and exit points and a plurality of linkages that link entry points and exit points based on the measured privacy, each said plurality of linkages of a mix zone of the road network accounting for a person's ability to make right turns, a person's shortest path driving behavior, and a presence of a road intersection between a large road and a small road.

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 t

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

• 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

• G06F2221/2111

  Location-sensitive, e.g. geographical location, GPS · CPC title