PRIVATE DECAYED SUM ESTIMATION UNDER CONTINUAL OBSERVATION

• US 20130212690A1
• Filed: 08/14/2012
• Published: 08/15/2013
• Est. Priority Date: 08/18/2011
• Status: Active Grant

• Current Assignee: Thomson Licensing (Vantiva SA)
• Original Assignee: Thomson Licensing (Vantiva SA)
• Inventors: Taft, Nina, Fawaz, Nadia, Nikolov, Aleksander Todorov, Bolot, Jean
• Granted Patent: US 9,471,791 B2
• Time in Patent Office: Days
• US Class Current: 726/26
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification

Abstract

Described herein is a method and system for providing privacy guarantees with an improved privacy-accuracy trade-off. Dynamic data can be accessed from a database. A sum model is selected from window sum, exponential decay sum, and polynomial decay sum. An algorithm is initiated that produces polylogarithmic bounded error in the range of a sum function associated with the selected sum model and independent of time steps. The data can be assembled in a dyadic tree structure. A non-linearity component can be added to nodes of the dyadic tree structure. For example, this can be a noise components or a weight applied to the update. This can be done, for example, to different nodes differently. Differential private estimators can be constructed for fixed steps of time. The differential private estimators can be applied to a query means or filtering system to enhance privacy protection from potential adversaries.

Claims

1. A method for providing privacy protection, comprising:

accessing dynamic data from a database;

selecting a decay sum model;

initiating an algorithm adapted to produce a polylogarithmic bounded error in the range of a sum function associated with the selected sum model and time step independent;

assembling the dynamic data in a dyadic tree structure;

adding a non-uniformity component to nodes of the dyadic tree structure;

constructing differentially private estimators for fixed steps of time; and

applying the differentially private estimators to a query to enhance privacy protection from potential adversaries.

2. The method of claim 1, wherein the decay sum model is selected from the group of sum models consisting of window sum, exponential decay sum, and polynomial decay sum.

3. The method of claim 1, wherein the dyadic tree structure is a sequence of dyadic trees.

4. The method of claim 1, wherein the non-uniformity component is a noise component.

5. The method of claim 4, wherein the noise component is a different noise component for different nodes of the dyadic tree structure.

6. The method of claim 1, wherein the non-uniformity component is a weight applied to an update.

7. The method of claim 6, wherein the weight is applied differently for different nodes of the dyadic tree structure.

8. The method of claim 1, wherein multiple instances of a window sum algorithm are run in parallel on a condition that the selected decay sum model is a polynomial decay sum.

9. A system for providing privacy protection, comprising:

a query module configured to access a database having continuously updated data;

an analysis module configured to select a decay sum model;

the analysis module configured to initiate an algorithm adapted to produce polylogarithmic bounded error in the range of a sum function associated with the selected sum model and time step independent;

the analysis module configured to assemble the dynamic data in a dyadic tree structure;

the analysis module configured to add a non-uniformity component to nodes of the dyadic tree structure;

the analysis module configured to construct differentially private estimators for fixed steps of time; and

an output module configured to apply the differentially private estimators to a query to enhance privacy protection from potential adversaries.

10. The system of claim 9, wherein the decay sum model is selected from the group of sum models consisting of window sum, exponential decay sum, and polynomial decay sum.

11. The system of claim 9, wherein the dyadic tree structure is a sequence of dyadic trees.

12. The system of claim 9, wherein the non-uniformity component is a noise component.

13. The system of claim 12, wherein the noise component is a different noise component for different nodes of the dyadic tree structure.

14. The system of claim 9, wherein the non-uniformity component is a weight applied to an update.

15. The system of claim 14, wherein the weight is applied differently for different nodes of the dyadic tree structure.

16. The system of claim 9, wherein multiple instances of a window sum algorithm are run in parallel on a condition that the selected decay sum model is a polynomial decay sum.

17. A computer readable medium bearing instructions for protecting privacy of data, comprising:

instructions for

accessing dynamic data from a database;

selecting a decay sum model;

initiating an algorithm adapted to produce polylogarithmic bounded error in the range of a sum function associated with the selected sum model and time step independent;

assembling the dynamic data in a dyadic tree structure;

adding a non-uniformity component to nodes of the dyadic tree structure;

constructing differentially private estimators for fixed steps of time; and

applying the differentially private estimators to a query to enhance privacy protection from potential adversaries.

18. The computer readable medium of claim 17, wherein the decay sum model is selected from the group of sum models consisting of window sum, exponential decay sum, and polynomial decay sum.

19. The computer readable medium of claim 17, wherein the non-uniformity component is applied differently for different nodes.

20. The computer readable medium of claim 17, wherein multiple instances of a window sum algorithm are run in parallel on a condition that the selected decay sum model is a polynomial decay sum.