Method and system for determining a measure of overlap between data entries

Abstract

A data analysis system and method for determining a measure of overlap between data entries in a number N of columns in a database. Sorted hash lists are provided. An N×N matrix having cells C ij is provided. A set of N indexed read pointers pointing to the hash lists are provided. Each read pointer points to the first entry of the associated hash list. The value of cells C ij in the matrix having indices i,j, wherein i and j each correspond to any of the index numbers of the read pointers pointing to the lowest value are incremented. The read pointer(s) pointing to the lowest value are incremented to point to the next different hash value(s). This is repeated until the last read pointer(s) points to the last entry of the associated hash list.

What is claimed is: 
     
         1 . A computer implemented method of determining a measure of overlap between data entries in a number N of columns in one or more databases, the method including the computer:
 a) creating for each column a hash list comprising for each data entry in the column a hash value representative of said data entry, the values in the hash list being sorted;   b) creating an N×N matrix, having cells C ij  , wherein i represents the column number and j represents the row number of the cell in the matrix;   c) assigning a set of N indexed read pointers, each read pointer pointing to a single associated sorted hash list;   d) setting each read pointer to the first entry of the associated hash list;   e) determining the index number(s) of the read pointer(s) pointing to the lowest hash value when processing the lists in ascending order, or determining the index number(s) of the read pointer(s) pointing to the highest hash value when processing the lists in descending order;   f) incrementing the value of cells C ij  in the matrix having indices i,j, wherein i and j each correspond to any of the index numbers determined in step e);   g) incrementing the read pointer(s) having the index number(s) determined in step e) to point to the next different hash value(s) and repeating steps e) and f); and   h) repeating step g) until the last read pointer(s) points to the last entry of the associated hash list.   
     
     
         2 . The method of  claim 1  wherein the step a) includes for each hash list discarding identical values. 
     
     
         3 . The method of  claim 1  wherein the step f) includes incrementing the value of the cells C ij  in the matrix having indices i,j, wherein i,j corresponds to each unique combination of the index numbers determined in step e), including the cases i=j. 
     
     
         4 . The method of  claim 1  wherein the step f) includes incrementing the value of all cells C ij  in the matrix having indices i,j, wherein i and j each corresponding to any of the index numbers determined in step e). 
     
     
         5 . The method of  claim 1 , wherein all hash values within a hash list have the same length. 
     
     
         6 . The method of  claim 1 , wherein all hash values in all hash lists have the same length. 
     
     
         7 . The method of  claim 1 , including the step of the computer determining a desired level of accuracy and creating the hash values having a length determined on the basis of the desired level of accuracy. 
     
     
         8 . The method of  claim 1 , further including after step h) the computer determining the cell C ij , with i unequal to j, having the highest value. 
     
     
         9 . The method of  claim 1 , further including after step h) the computer determining the cell(s) C ij  having a value that is higher than a threshold value. 
     
     
         10 . The method of  claim 1 , further including after step h) the computer normalizing the values in the cells of the matrix by dividing the value of each cell C ij  by the value of C. 
     
     
         11 . The method of  claim 10 , further including the computer determining the cell(s) C ij  having a normalized value that is higher than a threshold value. 
     
     
         12 . The method of  claim 1 , wherein the number N of columns is more than 1000, more preferably more than 10000, even more preferably more than 100000. 
     
     
         13 . The method of  claim 1 , further including the computer performing the step of including in the number N of columns at least one column containing data entries of a known type. 
     
     
         14 . The method of  claim 1 , wherein step g) includes:
 when the read pointer was not already pointing to the last entry in the hash list: incrementing the read pointer(s) pointing to the hash value determined in step e) to point to the next entry in the respective hash list, and when the read pointer was already pointing to the last entry in the hash list: not incrementing the read pointer(s) pointing to the hash value determined in step e), or incrementing the read pointer(s) pointing to the hash value determined in step e) to point to outside the respective hash list, and ignoring the index number of that read pointer(s) for subsequent steps f) and g).   
     
     
         15 . The method of  claim 1 , further including after step h) the computer:
 i) receiving a further column and creating a further sorted hash list comprising for each data entry in the further column a hash value representative of said data entry;   j) adding an N+1 th  column and an N+1 th  row to the matrix;   k) assigning a set of N+1 indexed read pointers, each read pointer pointing to a single associated sorted hash list, the N+1 th  read pointer pointing to the further hash list;   l) setting each read pointer to the first entry of the associated hash list;   m) determining the index number(s) of the read pointer(s) pointing to the lowest hash value when processing the lists in ascending order, or determining the index number(s) of the read pointer(s) pointing to the highest hash value when processing the lists in descending order;   n) incrementing the value of cells C ij  in the matrix having indices i,j, wherein i and j each corresponding to any of the index numbers determined in step m) and wherein at least one of i and j is equal to N+1;   o) incrementing the read pointer(s) having the index number(s) determined in step m) and repeating steps m) and n); and   p) repeating step o) until the last read pointer(s) points to the last entry of the associated hash list.   
     
     
         16 . The method of  claim 1 , further including after step h) the computer:
 i) receiving a further number M of columns and creating M further sorted hash lists comprising for each data entry in the further column a hash value representative of said data entry;   j) adding N+1 to N+M th  columns and N+1 to N+M th  rows to the matrix;   k) assigning a set of N+M indexed read pointers, each read pointer pointing to a single associated sorted hash list, the N+1 th  to N+M th  read pointers pointing to the further hash lists;   l) setting each read pointer to the first entry of the associated hash list;   m) determining the index number(s) of the read pointer(s) pointing to the lowest hash value when processing the lists in ascending order, or determining the index number(s) of the read pointer(s) pointing to the highest hash value when processing the lists in descending order;   n) incrementing the value of cells C ij  in the matrix having indices i,j, wherein i and j each correspond to any of the index numbers determined in step m) and wherein at least one of i and j is in the range of N+1 to N+M;   o) incrementing the read pointer(s) having the index number(s) determined in step m) and repeating steps m) and n); and   p) repeating step o) until the last read pointer(s) points to the last entry of the associated hash list.   
     
     
         17 . The method of  claim 1 , wherein a type of data entries in at least one of the columns is one of first name, last name, social security number, phone number, email address, IP-address, street address, postal code, city, country, bank account number, credit card number. 
     
     
         18 . A computer implemented method of determining a measure of overlap between data entries in a number N of columns in one or more databases, the method including the computer:
 a) retrieving for each column a list comprising for each data entry in the column a value representative of said data entry, the values in the list being sorted;   b) creating an N×N matrix, having cells C ij , wherein i represents the column number and j represents the row number of the cell in the matrix;   c) assigning a set of N indexed read pointers, each read pointer pointing to a single associated sorted list;   d) setting each read pointer to the first entry of the associated list;   e) determining the index number(s) of the read pointer(s) pointing to the lowest value when processing the lists in ascending order, or determining the index number(s) of the read pointer(s) pointing to the highest value when processing the lists in descending order;   f) incrementing the value of cells C ij  in the matrix having indices i,j, wherein i and j each correspond to any of the index numbers determined in step e);   g) incrementing the read pointer(s) having the index number(s) determined in step (e) to point to the next different value(s) and repeating steps e) and f); and   h) repeating step g) until the last read pointer(s) points to the last entry of the associated list.   
     
     
         19 . A computer implemented method of determining a type of data entries in a to-be-assessed column in a database, the method including the computer:
 a) creating for the to-be assessed column a to-be-assessed sorted hash list comprising for each data entry in the column a hash value representative of said data entry; and providing one or more sorted hash lists containing hash values representative of data entries of known types thus forming a number N of sorted hash lists;   b) creating an N×N matrix, having cells C ij  , wherein i represents the column number and j represents the row number of the cell in the matrix;   c) assigning a set of N indexed read pointers, each read pointer pointing to a single associated sorted hash list;   d) setting each read pointer to the first entry of the associated hash list;   e) determining the index number(s) of the read pointer(s) pointing to the lowest hash value when processing the lists in ascending order, or determining the index number(s) of the read pointer(s) pointing to the highest hash value when processing the lists in descending order;   f) incrementing the value of cells C ij  in the matrix having indices i,j, wherein i and j each correspond to any of the index numbers determined in step e);   g) incrementing the read pointer(s) having the index number(s) determined in step e) to point to the next different hash value(s) and repeating steps e) and f); and   h) repeating step g) until the last read pointer(s) points to the last entry of the associated hash list;
 determining which cell C pq  and/or C qp  indicates closest conformity between lists p and q, wherein the index p corresponds to the to-be-assessed column; and 
 determining the type of the data entries in the to-be-assessed column to be similar to the known type of the data entries in the hash list corresponding to the other index q. 
   
     
     
         20 . The method of  claim 19 , wherein determining which cell C pq  and/or C qp  indicates closest conformity, includes determining which cell C pq  and/or C qp  has the highest value.