Fuzzy database matching

• US 20080097983A1
• Filed: 10/23/2006
• Published: 04/24/2008
• Est. Priority Date: 10/23/2006
• Status: Active Grant

• Current Assignee: FotoNation Limited (Adeia, Inc.)
• Original Assignee: Donald M. Monro
• Inventors: Monro, Donald Martin
• Granted Patent: US 7,809,747 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 the stored records a plurality of characteristics, said characteristics falling within a characteristic space;

for each said characteristic, maintaining a record occurrence list of stored records from which said characteristic and characteristics within a defined proximity to said characteristic within said characteristic space have been extracted;

extracting characteristics from a sample record; and

identifying a given stored record as being a possible match with the sample if it appears in a required number of record occurrence lists.

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 characteristics defines all characteristics within the characteristic space that are extracted from said plurality of stored records.

7. A method as claimed in claim 1 in which said plurality of characteristics defines all possible characteristics within the characteristic space that could be displayed by a sample record.

8. A method as claimed in claim 1 in which the said plurality of 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 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 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 using a plurality of characteristics within a characteristic space, the system comprising:

for each characteristic, a record occurrence list of stored records from which said characteristic and characteristics within a defined proximity to said characteristic within said characteristic space have been extracted;

a processor for extracting characteristics from the sample record; and

a processor for identifying a given stored record as being a possible match with the sample if it appears in a required number of record occurrence lists.

16. A system as claimed in claim 15 in which the processor for extracting and the processor for identifying consist of a common processor.

17. A system as claimed in claim 15 in which the processor for extracting is remote from the processor for identifying.

18. A system as claimed in claim 15 in which the processor for extracting 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.