METHODS AND APPARATUS TO ANONYMIZE A DATASET OF SPATIAL DATA

• US 20130145473A1
• Filed: 12/05/2011
• Published: 06/06/2013
• Est. Priority Date: 12/05/2011
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Procopiuc, Cecilia M., Srivastava, Divesh, Cormode, Graham R., Shen, Entong
• Granted Patent: US 8,627,488 B2
• Time in Patent Office: Days
• US Class Current: 726/26
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: G06F 2221/2111 Location-sensitive, e.g. geographical location, GPS
• CPC Class Codes: G06F 2221/2145 Inheriting rights or properties, e.g., propagation of permissions or restrictions within a hierarchy
• CPC Class Codes: G11B 20/00086 Circuits for prevention of unauthorised reproduction or copying, e.g. piracy indicating unauthorised use of record carriers in general G11B23/28; scrambling for television signal recording H04N5/913; network architectures or network protocols for network security H04L63/00; cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00

Abstract

Methods and apparatus are disclosed to anonymize a dataset of spatial data. An example method includes generating a spatial indexing structure with spatial data, establishing a height value associated with the spatial indexing structure to generate a plurality of tree nodes, each of the plurality of tree nodes associated with spatial data counts, calculating a localized noise budget value for respective ones of the tree nodes based on the height value and an overall noise budget, and anonymizing the plurality of tree nodes with a anonymization process, the anonymization process using the localized noise budget value for respective ones of the tree nodes.

Claims

1. A method to anonymize a dataset of spatial data, comprising:

generating a spatial indexing structure with spatial data;

establishing a height value associated with the spatial indexing structure to generate a plurality of tree nodes, each of the plurality of tree nodes associated with spatial data counts;

calculating a localized noise budget value for respective ones of the tree nodes based on the height value and an overall noise budget; and

anonymizing the plurality of tree nodes with an anonymization process, the anonymization process using the localized noise budget value for respective ones of the tree nodes.

5. A method as described in claim 1, wherein the localized noise budget value is set to zero for a first one of the plurality of tree nodes when a noisy data count associated with the first tree node is below a threshold value.

7. A method as described in claim 1, further comprising generating a plurality of splits to form the spatial indexing structure.

8. A method as described in claim 7, further comprising applying a quadtree spatial indexing structure to generate the plurality of splits independent of the spatial data.

9. A method as described in claim 7, further comprising applying a kd-tree spatial indexing structure to generate the plurality of splits based on the spatial data.

11. A method as described in claim 1, further comprising adjusting noisy counts associated with respective ones of the plurality of tree nodes to reduce a query error.

12. A method as described in claim 11, wherein adjusting the noisy counts comprises computing an ordinary least squares (OLS) estimate of the noisy counts.

13. A method as described in claim 12, further comprising calculating a node transform for all leaves via a first top-down traversal of the spatial indexing structure.

14. A method as described in claim 13, further comprising calculating the node transform of internal nodes via a second bottom-up traversal of the spatial indexing structure based on the node transform of the first top-down traversal.

15. A method as described in claim 14, further comprising calculating the OLS estimate of the noisy counts via a third top down traversal of the spatial indexing structure based on the node transform of the second bottom-up traversal.

2-4. -4. (canceled)

6. (canceled)

10. (canceled)

16. An apparatus to anonymize a dataset of spatial data, comprising:

a spatial decomposition manager to generate a spatial indexing structure with spatial data, the spatial decomposition manager to establish a height value associated with the spatial indexing structure to generate a plurality of tree nodes, each of the plurality of tree nodes associated with spatial data counts;

a privacy budget manager to calculate a localized noise budget value for respective ones of the tree nodes based on the height value and an overall noise budget; and

a noise allocation engine to anonymize the plurality of tree nodes with an anonymization process, the anonymization process using the localized noise budget value for respective ones of the tree nodes.

20. An apparatus as described in claim 16, further comprising a non-uniform calculator to allocate a geometric sequence for the tree nodes.

21. An apparatus as described in claim 16, further comprising a data independent structure manager to generate a plurality of splits to form the spatial indexing structure.

22. An apparatus as described in claim 21, wherein the data independent structure manager generates a quadtree spatial indexing structure to generate the plurality of splits independent of the spatial data.

17-19. -19. (canceled)

23. (canceled)

24. An apparatus as described in claim 23, wherein the data dependent structure manager generates a kd-tree spatial indexing structure to generate the plurality of splits based on a distribution of the spatial data.

25-26. -26. (canceled)

27. A tangible machine accessible medium having instructions stored thereon that, when executed, cause a machine to, at least:

generate a spatial indexing structure with spatial data;

establish a height value associated with the spatial indexing structure to generate a plurality of tree nodes, each of the plurality of tree nodes associated with spatial data counts;

calculate a localized noise budget value for respective ones of the tree nodes based on the height value and an overall noise budget; and

anonymize the plurality of tree nodes with an anonymization process, the anonymization process using the localized noise budget value for respective ones of the tree nodes.

28. A tangible machine accessible medium as described in claim 27 having instructions stored thereon that, when executed, cause a machine to apply a Laplace mechanism to anonymize each one of the plurality of tree nodes.

29. A tangible machine accessible medium as described in claim 27 having instructions stored thereon that, when executed, cause a machine to convert the spatial data counts to noisy data counts.

31. A tangible machine accessible medium as described in claim 27 having instructions stored thereon that, when executed, cause a machine to allocate a geometric sequence for the tree nodes.

35. A tangible machine accessible medium as described in claim 27 having instructions stored thereon that, when executed, cause a machine to adjust noisy counts associated with respective ones of the plurality of tree nodes to reduce a query error.

36. A tangible machine accessible medium as described in claim 35 having instructions stored thereon that, when executed, cause a machine to compute an ordinary least squares (OLS) estimate of the noisy counts to adjust the noisy counts.

30. (canceled)

32-34. -34. (canceled)

37-47. -47. (canceled)