Proving that a user profile satisfies selection criteria for targeted data delivery

• US 7,894,448 B1
• Filed: 05/24/2006
• Issued: 02/22/2011
• Est. Priority Date: 05/24/2006
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lillibridge, Mark David, Lukose, Rajan Mathew
• Primary Examiner(s): Ryman; Daniel J
• Assistant Examiner(s): Patel; Jay P
• Application Number:
  US11/440,560
• Time in Patent Office: 1,735 Days
• Field of Search: 370/389, 370/395.21, 711/216, 776/98, 380/277
• US Class Current: 370/395.21
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 12/1859 adapted to provide push services, e.g. data channels
• CPC Class Codes: H04L 67/306 User profiles

Abstract

Methods and systems for targeted data delivery are described. A user profile that includes information about a user is accessed. A root hash of a hash-based directed acyclic graph (HDAG) is computed. The HDAG includes hashed values of items of information in the user profile. The root hash is used in proving that the user profile satisfies selection criteria associated with an offer to deliver data. The user is eligible to be presented with the offer of data provided the user profile satisfies the selection criteria. The data is targeted to the user based on the user profile without requiring a release of any of the information in the user profile.

Claims

1. A computer-implemented method for targeted data delivery, said method comprising:

accessing, by said computer, a user profile comprising information about a user collected from at least one electronic device associated with said user; and

computing, by said computer, a root hash of a hash-based directed acyclic graph (HDAG), said HDAG including hashed values of items of information in said user profile, wherein said root hash is computed before an offer of data is presented to said user, and is used in proving that said user profile satisfies selection criteria associated with said offer to deliver said data, wherein said user is eligible to be presented with said offer of data provided said user profile satisfies said selection criteria and produces one or more proofs that said root hash satisfied said selection criteria at the time said root hash was computed, wherein each of said proofs are calculated after said user commits to said user profile, and said proofs calculated after said user commits to said user profile and said root hash computed before said offer of data is presented to said user are used to determine whether said user profile satisfies said selection criteria, wherein said data is targeted to said user based on said user profile without requiring a release of any of said information in said user profile.

2. The method of claim 1 wherein said HDAG comprises a plurality of nodes, wherein at least one of said nodes has multiple parents and wherein said nodes comprise a root node and a plurality of leaf nodes.

3. The method of claim 2 further comprising producing said one or more proofs about said user profile, wherein a combination of all of said proofs does not reveal information about which of said nodes has multiple parents, each of said proofs comprising a trace comprising nodes and node pointers traversed between said root node and one of said leaf nodes.

4. The method of claim 2 wherein said user profile is proved to satisfy said selection criteria in part by demonstrating that an item was in said user profile at the time said root hash was computed by producing a proof comprising a trace from said root node to a leaf node associated with said item.

5. The method of claim 2 wherein said user profile is proved to satisfy said selection criteria in part by demonstrating that an item was not in said user profile at the time said root hash was computed by producing a non-membership proof comprising a trace from said root node to a leaf node associated with said item.

6. The method of claim 1 further comprising receiving, at a coordinator of distribution of said data, said root hash before said data is presented to said user, receiving, at said coordinator, said one or more proofs about said user profile, and verifying, by said coordinator, said proofs against said root hash received earlier from said user.

7. The method of claim 1 wherein producing said one or more proofs is provided by a device upon which said user profile is maintained.

8. The method of claim 1 wherein said user profile is committed to by said user by a deadline before said offer of data is presented to said user.

9. The method of claim 1 wherein said selection criteria comprise an approximate feature, wherein a selection criterion is satisfied if an item of information in said user profile includes a non-approximate feature that matches said approximate feature.

10. The method of claim 1 wherein producing said one or more proofs about said user profile prevent a user from altering a user profile to satisfy selection criteria associated with an offer of data after said offer has been issued.

11. A computer-implemented method for targeted data delivery, said method comprising:

receiving, by said computer, a root hash of a hash-based directed acyclic graph (HDAG), said HDAG including hashed values of items of information in a user profile, wherein said root hash is computed before an offer of data is issued to said user, wherein said user profile comprises information about a user collected from at least one electronic device associated with said user, wherein said HDAG comprises a plurality of nodes wherein at least one of said nodes has multiple parents and wherein said nodes comprise a root node and a plurality of leaf nodes;

receiving, by said computer, one or more proofs about said user profile, wherein a combination of all of said proofs does not reveal information about which of said nodes has multiple parents, each of said proofs calculated after said user commits to said user profile and comprising a trace comprising nodes and node pointers traversed between said root node and one of said leaf nodes; and

using, by said computer, said proofs calculated after said user commits to said user profile and said root hash computed before said offer of data is issued to said user to determine whether said user profile satisfies selection criteria associated with said offer to deliver said data.

12. The method of claim 11 wherein said user profile is proved to satisfy said selection criteria in part by demonstrating that an item was in said user profile at the time said root hash was computed by verifying a proof comprising a trace from said root node to a leaf node associated with said item.

13. The method of claim 11 wherein said user profile is proved to satisfy said selection criteria in part by demonstrating that an item was not in said user profile at the time said root hash was computed by verifying a non-membership proof comprising a trace from said root node to a leaf node associated with said item.

14. The method of claim 11 further comprising providing compensation to said user provided said user profile satisfies said selection criteria and produces one or more proofs that said root hash satisfied said selection criteria at the time said root hash was computed.

15. Application instructions on a non-transitory computer-usable medium where said instructions when executed effect a method for targeted data delivery, said method comprising:

accessing a user profile comprising information about a user collected from at least one electronic device associated with said user;

computing a root hash of a hash-based directed acyclic graph (HDAG), said HDAG including hashed values of items of information in said user profile, wherein said root hash is computed before an offer of data is presented to said user; and

using said root hash in proving that said user profile satisfies selection criteria associated with said offer to deliver said data, wherein said user is eligible to be presented with said offer of data provided said user profile satisfies said selection criteria and produces one or more proofs that said root hash satisfied said selection criteria at the time said root hash was computed, wherein each of said proofs are calculated after said user commits to said user profile, and said proofs calculated after said user commits to said user profile and said root hash computed before said offer of data is presented to said user are used to determine whether said user profile satisfies said selection criteria, wherein said data is targeted to said user based on said user profile without requiring a release of any of said information in said user profile.

16. The application instructions of claim 15 wherein said HDAG comprises a plurality of nodes, wherein at least one of said nodes has multiple parents and wherein said nodes comprise a root node and a plurality of leaf nodes.

17. The application instructions of claim 16 wherein said method further comprises producing said one or more proofs about said user profile, wherein a combination of all of said proofs does not reveal information about which of said nodes has multiple parents, each of said proofs comprising a trace comprising nodes and node pointers traversed between said root node and one of said leaf nodes.

18. The application instructions of claim 16 wherein said user profile is proved to satisfy said selection criteria in part by demonstrating that an item was in said user profile at the time said root hash was computed by producing a proof comprising a trace from said root node to a leaf node associated with said item.

19. The application instructions of claim 16 wherein said user profile is proved to satisfy said selection criteria in part by demonstrating that an item was not in said user profile at the time said root hash was computed by producing a non-membership proof comprising a trace from said root node to a leaf node associated with said item.

20. The application instructions of claim 19 wherein said leaf node has multiple parents and wherein said non-membership proof conceals information about the presence or absence of other items of information in said user profile.