Fuzzy Database Matching

Abstract

A method of improving the speed with which a sample such as a biometric sample can be fuzzily matched against records in a database, comprises extracting characteristics from the sample, and using those extracted characteristics as indexes ( 70 ) to address a lookup table ( 25 ). Each row within the lookup table points to an individual record occurrence list ( 28, 30, 32 ) which contain details of not only the stored records from which the given characteristic can be extracted, but also those records having an extracted characteristic which are within a defined proximity to the said characteristic. Characteristics are extracted from the sample record, and a given stored record is identified as being a possible match with the sample if it appears in a required number of record occurrence lists.

1 . A method of identifying possible matches between a sample record and a plurality of stored records, the method comprising:
 extracting from each of the stored records a plurality of index characteristics, said index characteristics falling within an index characteristic space;   maintaining a look-up table defining said index characteristic space, said look-up table having a plurality of rows, each row corresponding to a unique index characteristic within said index characteristic space;   maintaining a plurality of record occurrence lists, each said list being linked from a specific row in said look-up table corresponding to a specific index characteristic, and each said list identifying those stored records from which said specific index characteristic and index characteristics within a defined proximity to said specific index characteristics within said index characteristic space have been extracted;   extracting sample index characteristics from a sample record;   using said sample index characteristics as indexes to address said look-up table to look up a corresponding plurality of record occurrence lists which are associated with said sample index characteristics;   counting the number of occurrences of respective stored records identified within said record occurrence lists; and   identifying a given stored record as being a possible match with the sample if said count for said given stored record exceeds a required threshold.   
     
     
         2 . A method as claimed in  claim 1  in which the defined proximity is a defined Hamming distance. 
     
     
         3 . A method as claimed in  claim 2  in which the defined Hamming distance is user-selectable. 
     
     
         4 . A method as claimed in  claim 1  in which the required number is a numerical threshold. 
     
     
         5 . A method as claimed in  claim 1  in which the required number is a function of the average number of record occurrence lists per stored record. 
     
     
         6 . A method as claimed in  claim 1  in which said plurality of index characteristics defines all index characteristics within the index characteristic space that are extracted from said plurality of stored records. 
     
     
         7 . A method as claimed in  claim 1  in which said plurality of index characteristics defines all possible index characteristics within the index characteristic space that could be displayed by a sample record. 
     
     
         8 . A method as claimed in  claim 1  in which the said plurality of index characteristics is generated by applying an operation, such as a hash, to the stored records. 
     
     
         9 . A method as claimed in  claim 1 , including applying an operation to the sample record to generate one or more sample outputs, and using the sample outputs to address a lookup table, each row in said lookup table pointing to a record occurrence list. 
     
     
         10 . A method as claimed in  claim 1  in which as index characteristics are extracted a histogram is built up recording matches by stored record; and identifying records as possible matches from the histogram. 
     
     
         11 . A method as claimed in  claim 1  including establishing a plurality of defined proximities, and maintaining a separate record occurrence list for each index characteristic and proximity combination. 
     
     
         12 . A method as claimed in  claim 11  in which the identifying step uses those lists which relate to a user-selected defined proximity. 
     
     
         13 . A method as claimed in  claim 1  including the additional step of further analyzing the relationship between the sample record and each of the said possible matches. 
     
     
         14 . A method as claimed in  claim 1  in which the said identifying step is divided between a plurality of parallel processors, each forwarding an association result to a consolidator, said consolidator identifying stored records as possible matches in dependence upon said association results. 
     
     
         15 . A system for identifying possible matches between a sample record and a plurality of stored records, the system comprising:
 a computer processor coupled to a database containing a plurality of index characteristics extracted from said stored records, said index characteristics falling within an index characteristic space;   a look-up table defining said characteristic space, said look-up table having a plurality of rows, each row corresponding to a unique index characteristic within said index characteristic space;   a plurality of record occurrence lists, each said list being linked from a specific row in said look-up table corresponding to a specific index characteristic, and each said list identifying those stored records from which said specific index characteristic and index characteristics within a defined proximity to said specific index characteristics within said index characteristic space have been extracted;   and whereby the system is configured to:   extract sample index characteristics from a sample record, and use said sample index characteristics as indexes to address said look-up table to look up a corresponding plurality of record occurrence lists which are associated with said sample index characteristics;   count the number of occurrences of respective stored records identified by said record occurrence lists; and   identify a given stored record as being a possible match with the sample record if said count for said given stored record exceeds a required threshold.   
     
     
         16 . A system as claimed in  claim 15  in which the computer processor includes a first processor for extracting sample index characteristics from a sample record and a second processor for identifying a given stored record as being a possible match with the sample record. 
     
     
         17 . A system as claimed in  claim 16  in which the first processor is remote from the second processor. 
     
     
         18 . A system as claimed in  claim 15  in which the first processor comprises a plurality of parallel processors, each forwarding an association result to a consolidator, said consolidator identifying stored records as possible matches in dependence upon said associated results.