Differential privacy and outlier detection within a non-interactive model

Patent metadata

Field	Value
Publication number	US-10445527-B2
Application number	US-201615387052-A
Country	US
Kind code	B2
Filing date	Dec 21, 2016
Priority date	Dec 21, 2016
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

A system for differential privacy is provided. In some implementations, the system performs operations comprising receiving a plurality of indices for a plurality of perturbed data points, which are anonymized versions of a plurality of unperturbed data points, wherein the plurality of indices indicate that the plurality of unperturbed data points are identified as presumed outliers. The plurality of perturbed data points can lie around a first center point and the plurality of unperturbed data points can lie around a second center point. The operations can further comprise classifying a portion of the presumed outliers as true positives and another portion of the presumed outliers as false positives, based upon differences in distances to the respective first and second center points for the perturbed and corresponding (e.g., same index) unperturbed data points. Related systems, methods, and articles of manufacture are also described.

First claim

What is claimed is:

1. A system comprising:
at least one processor; and
at least one memory storing instructions which, when executed by the at least one processor, cause operations comprising:
receiving a plurality of indices for a plurality of perturbed data points from an perturbed data set generated by one or more sensors, wherein the plurality of perturbed data points are anonymized versions of a plurality of unperturbed data points with the same plurality of indices, wherein receiving the plurality of indices indicates that the plurality of unperturbed data points are identified as presumed outliers, wherein the plurality of perturbed data points lie around a first center point, and wherein the plurality of unperturbed data points lie around a second center point;
classifying, based upon distance differences, a first portion of the presumed outliers as true positives, wherein the distance differences include, for each of the plurality of perturbed data points, a difference between a distance of the perturbed data point from the first center point and a distance of a corresponding unperturbed data point from the second center point;
classifying, based upon the distance differences, a second portion of the presumed outliers as false positives, wherein each presumed outlier is classified as a false positive when a corresponding distance difference for the presumed outlier is less than a threshold distance away from the first center point, and wherein each presumed outlier is classified as a true positive when a corresponding distance difference for the presumed outlier is greater than the threshold distance away from the first center point; and
providing, based on the classifying, a list of confirmed outliers.

2. The system of claim 1 , wherein the operations further comprise:
determining the threshold distance from the first center point, and wherein the one or more sensors comprise at least one Internet of Things sensor.

3. The system of claim 2 , wherein the operations further comprise:
ordering each of the distance differences in an ordered list;
identifying a largest change between two consecutive differences in the ordered list; and
setting the threshold distance as the largest change.

4. The system of claim 1 , wherein the plurality of unperturbed data points are held among a plurality of sensor devices.

5. The system of claim 1 , wherein the operations further comprise:
determining whether any of the distance differences are negative; and
classifying each of the plurality of unperturbed data points with a negative distance difference as a false negative.

6. The system of claim 1 , wherein the operations further comprise:
identifying a minimum distance difference from among the true positives;
receiving indices for a plurality of non-outliers with a distance from the first center point that is greater or equal to the minimum distance; and
reclassifying, as false negatives, each of the plurality of non-outliers with a distance difference between zero and the minimum distance difference.

7. The system of claim 1 , wherein the operations further comprise:
identifying a minimum distance difference from among the true positives;
setting an outer boundary value to equal a sum of the minimum distance difference and a width of an outlier layer, wherein the width of the outlier layer is a difference between an end and a beginning of an area in a coordinate space that includes the outliers;
receiving indices for a plurality of non-outliers with a distance from the first center point that is greater or equal to the outer boundary value; and
reclassifying, as false negatives, each of the plurality of non-outliers with a distance difference between the threshold distance and the outer boundary.

8. The system of claim 1 , wherein the plurality of perturbed data points are anonymized based upon a noise function, and wherein the noise function comprises a perturbation function.

9. A method for protecting data associated with one or more sensors, the method comprising:
receiving, at a processor, a plurality of indices for a plurality of perturbed data points from an perturbed data set generated by one or more sensors, wherein the plurality of perturbed data points are anonymized versions of a plurality of unperturbed data points with the same plurality of indices, wherein receiving the plurality of indices indicates that the plurality of unperturbed data points are identified as presumed outliers, wherein the plurality of perturbed data points lie around a first center point, and wherein the plurality of unperturbed data points lie around a second center point;
classifying, by the processor and based upon distance differences, a first portion of the presumed outliers as true positives, wherein the distance differences include, for each of the plurality of perturbed data points, a difference between a distance of the perturbed data point from the first center point and a distance of a corresponding unperturbed data point from the second center point;
classifying, by the processor and based upon the distance differences, a second portion of the presumed outliers as false positives, wherein each presumed outlier is classified as a false positive when a corresponding distance difference for the presumed outlier is less than a threshold distance away from the first center point, and wherein each presumed outlier is classified as a true positive when a corresponding distance difference for the presumed outlier is greater than the threshold distance away from the first center point; and
providing, by the processor and based on the classifying, a list of confirmed outliers.

10. The method of claim 9 , further comprising:
ordering each of the distance differences in an ordered list;
identifying a largest change between two consecutive differences in the ordered list; and
setting the threshold distance as the largest change, and
wherein the one or more sensors comprise at least one Internet of Things sensor.

11. The method of claim 9 , further comprising:
determining whether any of the distance differences are negative; and
classifying each of the plurality of unperturbed data points with a negative distance difference as a false negative.

12. The method of claim 9 , further comprising:
identifying a minimum distance difference from among the true positives;
receiving indices for a plurality of non-outliers with a distance from the first center point that is greater or equal to the minimum distance; and
reclassifying, as false negatives, each of the plurality of non-outliers with a distance difference between zero and the minimum distance difference.

13. The method of claim 9 , further comprising:
identifying a minimum distance difference from among the true positives;
setting an outer boundary value to equal a sum of the minimum distance difference and a width of an outlier layer, wherein the width of the outlier layer is a difference between an end and a beginning of an area in a coordinate space that includes the outliers;
receiving indices for a plurality of non-outliers with a distance from the first center point that is greater or equal to the outer boundary value; and
reclassifying, as false negatives, each of the plurality of non-outliers with a distance difference between the threshold distance and the outer boundary.

14. A non-transitory computer program product storing instructions which, when executed by at least one data processor, causes operations comprising:
receiving a plurality of indices for a plurality of perturbed data points from an perturbed data set generated by one or more sens

Assignees

• Sap Se

Inventors

• Boehler Jonas
• Bernau Daniel
• Kerschbaum Florian

Classifications

• H04W12/02

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

• H04W4/70

  Services for machine-to-machine communication [M2M] or machine type communication [MTC] · CPC title

• H04W4/38

  for collecting sensor information · CPC title

• H04L63/0421

  Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer · CPC title

• G06F21/604 Primary

  Tools and structures for managing or administering access control systems · CPC title