System and method for distributed privacy preserving data mining

• US 7,305,378 B2
• Filed: 07/16/2004
• Issued: 12/04/2007
• Est. Priority Date: 07/16/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu C., Yu, Philip Shi-Lung
• Primary Examiner(s): Alam; Hosain
• Assistant Examiner(s): Raab; Christopher J
• Application Number:
  US10/892,691
• Publication Number:
  US 20060015474A1
• Time in Patent Office: 1,236 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

Distributed privacy preserving data mining techniques are provided. A first entity of a plurality of entities in a distributed computing environment exchanges summary information with a second entity of the plurality of entities via a privacy-preserving data sharing protocol such that the privacy of the summary information is preserved, the summary information associated with an entity relating to data stored at the entity. The first entity may then mine data based on at least the summary information obtained from the second entity via the privacy-preserving data sharing protocol. The first entity may obtain, from the second entity via the privacy-preserving data sharing protocol, information relating to the number of transactions in which a particular itemset occurs and/or information relating to the number of transactions in which a particular rule is satisfied.

Claims

1. A method of determining at least one large itemset in a privacy-preserving manner in a distributed computing environment including a plurality of entities, comprising the steps of:

a first entity of the plurality of entities exchanging summary information with a second entity of the plurality of entities via a privacy-preserving data sharing protocol such that the privacy of the summary information is preserved, the summary information associated with an entity relating to transactional data stored at the entity; and

the first entity determining at least one large itemset based on at least the summary information obtained from the second entity via the privacy-preserving data sharing protocol;

wherein the summary information exchanging step further comprises;

the first entity transmitting a first random number to the second entity;

the first entity receiving from the second entity a first result, the first result representing a summation of the first random number and a second random number associated with the second entity;

the first entity transmitting a second result to the second entity, the second result representing a summation of the first result and summary information relating to data stored at the first entity;

the first entity receiving a third result from the second entity, the third result representing a summation of the second result and summary information relating to data stored at the second entity;

the first entity transmitting a fourth result to the second entity, the fourth result representing a subtraction of the first random number from the third result; and

the first entity receiving a fifth result from the second entity, the fifth result representing a subtraction of the second random number from the fourth result.

2. The method of claim 1, wherein the summary information exchanging step further comprises the first entity obtaining, from the second entity via the privacy-preserving data sharing protocol, information relating to the number of transactions in which a particular itemset occurs.

3. The method of claim 1, wherein the summary information exchanging step further comprises the first entity obtaining, from the second entity via the privacy-preserving data sharing protocol, information relating to the number of transactions in which a particular rule is satisfied.

4. The method of claim 1, wherein the summary information exchanging step further comprises the first entity adding a random number to a global count and transmitting the global count to the second entity.

5. The method of claim 1, wherein the summary information exchanging step further comprises the first entity subtracting a random number from a global count and transmitting the global count to the second entity.

6. The method of claim 1, wherein the summary information exchanging step further comprises the first entity exchanging summary information with two or more of the plurality of entities and the first entity mining data based on the summary information obtained from the two or more entities.

7. The method of claim 6, wherein the summary information exchanging step further comprises the first entity exchanging summary information with the two or more entities, wherein the summary information relates to a limited subset of items.

8. The method of claim 7, wherein the summary information exchanging step further comprises the first entity defining the limited subset of items for which summary information is to be exchanged.

9. The method of claim 8, wherein the summary information exchanging step further comprises the first entity determining participating entities for each itemset for which summary information is to be exchanged.

10. The method of claim 9, wherein the summary information exchanging step further comprises the first entity transmitting summary information only to a participating entity for a particular itemset.

11. The method of claim 1, further comprising the step of the first entity discarding itemsets having a number of potential participants below a particular threshold value.

12. The method of claim 1, further comprising the step of the first entity generating one or more association rules from one or more itemsets.

13. Apparatus associated with a first entity in a distributed computing environment, including a plurality of entities, for determining at least one large itemset in a privacy-preserving manner, comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) exchange summary information with a second entity of the plurality of entities via a privacy-preserving data sharing protocol such that the privacy of the summary information is preserved, the summary information associated with an entity relating to transactional data stored at the entity; and

(ii) determine at least one large itemset based on at least the summary information obtained from the second entity via the privacy-preserving data sharing protocol;

wherein the summary information exchanging operation further comprises;

the first entity transmitting a first random number to the second entity;

the first entity receiving from the second entity a first result, the first result representing a summation of the first random number and a second random number associated with the second entity;

the first entity transmitting a second result to the second entity, the second result representing a summation of the first result and summary information relating to data stored at the first entity;

the first entity receiving a third result from the second entity, the third result representing a summation of the second result and summary information relating to data stored at the second entity;

the first entity transmitting a fourth result to the second entity, the fourth result representing a subtraction of the first random number from the third result; and

the first entity receiving a fifth result from the second entity, the fifth result representing a subtraction of the second random number from the fourth result.

14. The apparatus of claim 13, wherein the summary information exchanging operation further comprises obtaining, from the second entity via the privacy-preserving data sharing protocol, information relating to the number of transactions in which a particular itemset occurs.

15. The apparatus of claim 13, wherein the summary information exchanging operation further comprises obtaining, from the second entity via the privacy-preserving data sharing protocol, information relating to the number of transactions in which a particular rule is satisfied.

16. The apparatus of claim 13, wherein the summary information exchanging operation further comprises adding a random number to a global count and transmitting the global count to the second entity.

17. The apparatus of claim 13, wherein the summary information exchanging operation further comprises subtracting a random number from a global count and transmitting the global count to the second entity.

18. The apparatus of claim 13, wherein the summary information exchanging operation further comprises exchanging summary information with two or more of the plurality of entities and mining data based on the summary information obtained from the two or more entities.

19. An article of manufacture for use with a first entity in a distributed computing environment, including a plurality of entities, for determining at least one large itemset in a privacy-preserving manner, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

the first entity exchanging summary information with a second entity of the plurality of entities via a privacy-preserving data sharing protocol such that the privacy of the summary information is preserved, the summary information associated with an entity relating to transactional data stored at the entity; and

the first entity determining at least one large itemset based on at least the summary information obtained from the second entity via the privacy-preserving data sharing protocol;

wherein the summary information exchanging step further comprises;

the first entity transmitting a first random number to the second entity;

the first entity receiving from the second entity a first result, the first result representing a summation of the first random number and a second random number associated with the second entity;

the first entity transmitting a second result to the second entity, the second result representing a summation of the first result and summary information relating to data stored at the first entity;

the first entity receiving a third result from the second entity, the third result representing a summation of the second result and summary information relating to data stored at the second entity;

the first entity transmitting a fourth result to the second entity, the fourth result representing a subtraction of the first random number from the third result; and

the first entity receiving a fifth result from the second entity, the fifth result representing a subtraction of the second random number from the fourth result.