Fuzzy Database Matching

• US 20100281043A1
• Filed: 07/16/2010
• Published: 11/04/2010
• Est. Priority Date: 10/23/2006
• Status: Abandoned Application

• Current Assignee: Donald M. Monro
• Original Assignee: Donald M. Monro
• Inventors: Monro, Donald Martin
• Application Number:
  US12/838,109
• Publication Number:
  US 20100281043A1
• Time in Patent Office: Days
• US Class Current: 707/758
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06V 40/197 Matching; Classification
• CPC Class Codes: G06V 40/50 Maintenance of biometric data or enrolment thereof

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.

Claims

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.