Fuzzy database matching

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;

building a histogram as index characteristics are extracted recording matches by stored record;

counting the number of occurrences of respective stored records identified within said record occurrence lists from the histogram; and

identifying a given stored record as being a possible match with the sample if said count from the histogram 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 establishing a plurality of defined proximities, and maintaining a separate record occurrence list for each index characteristic and proximity combination.

10. A method as claimed in claim 9 in which the identifying step uses those lists which relate to a user-selected defined proximity.

11. 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.

12. 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.

13. 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;

build a histogram as index characteristics are extracted recording matches by stored record;

count the number of occurrences of respective stored records identified by said record occurrence lists from the histogram; and

identify a given stored record as being a possible match with the sample record if said count from the histogram for said given stored record exceeds a required threshold.

14. A system as claimed in claim 13 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.

15. A system as claimed in claim 14 in which the first processor is remote from the second processor.

16. A system as claimed in claim 13 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.