System and method for data quality analysis between untrusted parties

• US 9,413,760 B2
• Filed: 09/05/2014
• Issued: 08/09/2016
• Est. Priority Date: 09/05/2014
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Freudiger, Julien, Rane, Shantanu, Brito, Alejandro E., Uzun, Ersin
• Primary Examiner(s): Hirl, Joseph P
• Assistant Examiner(s): BELL, KALISH K
• Application Number:
  US14/479,242
• Publication Number:
  US 20160072805A1
• Time in Patent Office: 704 Days
• Field of Search: 726/26, 713/193, 713/159, 713/931
• US Class Current: 1/1
• CPC Class Codes: H04L 63/0407 wherein the identity of one or more communicating identities is hidden cryptographic mechanisms or cryptographic arrangements for anonymous credentials or for identity based cryptographic systems H04L9/00
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0853 using an additional device, e.g. smartcard, SIM or a different communication terminal cryptographic mechanisms or cryptographic arrangements for entity authentication involving additional secure or trusted devices H04L9/3234
• CPC Class Codes: H04L 63/0876 based on the identity of the terminal or configuration, e.g. MAC address, hardware or software configuration or device fingerprint
• CPC Class Codes: H04L 67/01 Protocols

Abstract

A system and method for data quality analysis between untrusted parties is provided. A dataset having attributes each associated with one or more elements is maintained. An encrypted request is received from a client regarding data quality for one of the attributes. The encrypted request includes an interest vector of separately encrypted values identifying those elements of interest for the attribute. A condensed data vector representing the elements is generated for the attribute and is the same length as the interest vector. An aggregate of the elements of interest is determined by calculating for each element in the condensed data vector, an encrypted product of that element and a corresponding element of the interest vector and by determining a total product of all the encrypted products. A data quality value is assigned to the elements of the attribute in the dataset based on the aggregate.

Claims

1. A system for data quality analysis, comprising:

memory storing a dataset comprising attributes each associated with one or more elements;

a client comprising;

a first vector generating module to generate an interest vector of separately encrypted values identifying elements of interest for at least one attribute;

a request module to send an encrypted request to a server, wherein the encrypted request comprises the interest vector; and

a first determination module to send an acquisition determination to the server, wherein the acquisition determination is based on a data quality value; and

the server, comprising;

a receipt module to receive the encrypted request from the client regarding data quality for the at least one attribute;

a second vector generating module to generate a condensed data vector representing the elements for the at least one attribute, wherein the condensed data vector is the same length as the interest vector;

a condensed data vector module to determine the condensed data vector as one of a counting hashmap when the data quality comprises data completeness and a histogram when the data quality comprises data validity, comprising at least one of;

a hashmap module to determine the condensed data vector as the counting hashmap, comprising;

a calculation module to calculate a hash value for each of the elements for the at least one attribute;

an occupancy determination module to determine a number of times each hash value occurs in the dataset as an occurrence value; and

placement module to place the occurrence values in an element of the vector indexed by the hash values; and

a histogram module to determine the condensed data vector as the histogram, comprising;

determination module to set a maximum and minimum value for the elements of the at least one attribute;

a graph module to generate the histogram based on the set maximum and minimum values for the elements along an x-axis and frequency occurrences of the elements along the y-axis; and

a placement module to place the frequency of occurrences along the condensed data vector;

an aggregator module to determine an aggregate of the elements of interest by determining for each of the elements in the condensed data vector, an encrypted product of that element and a corresponding element of the interest vector and by calculating the aggregate as an encrypted value by determining a total product of all the encrypted products, wherein the aggregate is used to assign the data quality value to the elements of the at least one attribute in the dataset; and

a provider module to provide the dataset based on the acquisition determination.

2. A system according to claim 1, wherein the aggregator module calculates the aggregate based on properties of a homomorphic cryptosystem.

3. A system according to claim 1, wherein the data quality comprises at least one of data completeness, data validity, data consistency, and data timeliness.

4. A system according to claim 1, wherein the client determines an interest vector, comprising:

a second receipt module to receive from the server a total number of unique elements for the at least one attribute;

a hash module to hash the elements of interest;

an assignment module to assign a value of one to each of the elements of interest and a value of zero to each of the elements not of interest; and

a third placement module to place the values along the interest vector at a location identified by the corresponding hashed element of interest.

5. A system according to claim 1, wherein the client determines the interest vector as a binary vector by assigning a value of one to each of the elements of interest and a value of zero to each of the elements not of interest.

6. A system according to claim 5, wherein the client determines the interest vector as a binary vector for the elements from the at least one attribute and the elements for another attribute when the data quality comprises data consistency, comprising:

a second graph module to represent on a graph element pairs of interest each comprising one of the elements of the at least one attribute and one of the elements of the other attributes by assigning a value of one;

an assignment module to assign a value of zero to the remaining element pairs that are not of interest; and

a transformation module to transform the graph to an interest vector by placing the values of one and zero along the interest vector.

7. A system according to claim 1, wherein the server determines the condensed data vector as a binary vector for elements from the at least one attribute and elements from another one of the attributes when the data quality comprises data consistency, comprising:

a second graph module to represent element pairs of interest each comprising one of the elements of the at least one attribute and one of the elements of the other attribute that are present in the dataset on a graph by assigning a value of one to the pairs of interest that are present and a value of zero to the pairs of interest that are not present; and

a third placement module to place the values of the graph along the condensed data vector.

8. A system according to claim 6, further comprising:

a matrix module to transform each of the interest vector and the condensed data vector to a matrix prior to generating the vectors.

9. A method for data quality analysis, comprising:

maintaining, by a memory, a dataset comprising attributes each associated with one or more elements;

generating, by a client an interest vector of separately encrypted values identifying elements of interest for at least one attribute;

sending, from the client to a server, an encrypted request comprising the interest vector;

receiving, by the server, the encrypted request from the client regarding data quality for the at least one attribute;

generating, by the server, a condensed data vector representing the elements for the at least one attribute, wherein the condensed data vector is the same length as the interest vector;

determining, by the server, the condensed data vector as one of a counting hashmap when the data quality comprises data completeness and a histogram when the data quality comprises data validity, comprising at least one of;

determining the condensed vector as the hashmap, comprising;

calculating a hash value for each of the elements for the at least one attribute;

determining a number of times each hash value occurs in the dataset as an occurrence value; and

placing the occurrence values in an element of the vector indexed by the hash values; and

determining the condensed data vector as the histogram, comprising;

setting a maximum and minimum value for the elements of the at least one attribute;

generating the histogram based on the set maximum and minimum values for the elements along an x-axis and frequency occurrences of the elements along the y-axis; and

placing the frequency of occurrences along the condensed data vector;

determining, by the server, an aggregate of the elements of interest, comprising;

determining for each of the elements in the condensed data vector, an encrypted product of that element and a corresponding element of the interest vector; and

calculating the aggregate as an encrypted value by determining a total product of all the encrypted products; and

assigning, by the server, a data quality value to the elements of the at least one attribute in the dataset based on the aggregate;

sending an acquisition determination to the server, wherein the acquisition determination is based on the data quality value; and

providing the dataset based on the acquisition determination.

10. A method according to claim 9, further comprising:

calculating the aggregate based on properties of a homomorphic cryptosystem.

11. A method according to claim 9, wherein the data quality comprises at least one of data completeness, data validity, data consistency, and data timeliness.

12. A method according to claim 9, further comprising:

determining the interest vector by the client, comprising;

receiving from the server a total number of unique elements for the at least one attribute;

hashing the elements of interest;

assigning a value of one to each of the elements of interest and a value of zero to each of the elements not of interest; and

placing the values along the interest vector at a location identified by the corresponding hashed element of interest.

13. A method according to claim 9, further comprising:

determining by the client, the interest vector as a binary vector, comprising;

assigning a value of one to each of the elements of interest; and

assigning a value of zero to each of the elements not of interest.

14. A method according to claim 9, further comprising:

determining the condensed data vector as a binary vector for the elements from the at least one attribute and the elements for another one of the attributes when the data quality comprises data consistency, comprising;

representing element pairs of interest each comprising one of the elements of the at least one attribute and one of the elements of the other attribute that are present in the dataset on a graph by assigning a value of one to the pairs of interest that are present and a value of zero to the pairs of interest that are not present; and

placing the values of the graph along the condensed data vector.

15. A method according to claim 14, further comprising:

determining the interest vector as a binary vector for the elements from the at least one attribute and the elements from the other attribute when the data quality comprises data consistency, comprising;

representing on a graph element pairs of interest each comprising one of the elements of the at least one attribute and one of the elements of the other attribute by assigning a value of one;

assigning a value of zero to the remaining element pairs that are not of interest; and

transforming the graph to an interest vector by placing the values of one and zero along the interest vector.

16. A method according to claim 15, further comprising:

transforming each of the interest vector and the condensed data vector to a matrix prior to generating the vector.