Fast database matching

• US 20080097992A1
• Filed: 10/23/2006
• Published: 04/24/2008
• 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:
  US11/585,365
• Publication Number:
  US 20080097992A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence

Abstract

A method of improving the speed with which a sample can be matched against records in a database comprises defining a list (24) of possible characteristics (26), extracting characteristics from the sample and, for each record in the database, counting the number of characteristics that match both the record and the sample. A list of candidate matches is then selected on the basis of that count, for more detailed matching or analysis. Such a method provides very fast matching at the expense of some additional effort when registering a new record within the database.

Claims

1. A method of identifying possible matches between a sample record and a plurality of stored records, the method comprising:

defining a list of characteristics, and associating with each characteristic those stored records which display said characteristic;

extracting characteristics from the sample record; and

identifying a given stored record as being a possible match with the sample if it is associated with a required number of extracted characteristics.

2. A method as claimed in claim 1 in which the required number is a numerical threshold.

3. A method as claimed in claim 1 in which the required number is a function of the average number of matching characteristics per stored record.

4. A method as claimed in claim 1 in which the list of characteristics is user-generated.

5. A method as claimed in claim 1 in which the list of characteristics is automatically generated from the stored records.

6. A method as claimed in claim 1 in which the list of characteristics defines all characteristics within a characteristic space that are displayed by the said plurality of stored records.

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

9. A method as claimed in claim 1 in which the list of characteristics is stored within a database table.

10. A method as claimed in claim 1 in which the list of characteristics is ordered.

11. A method as claimed in claim 1 in which each characteristic is a stored-record fragment.

12. A method as claimed in claim 1 in which the list of characteristics is generated by applying an operation, such as a hash, to the stored records.

13. A method as claimed in claim 1 in which said associating step comprises maintaining a pointer linking each said characteristic to a case occurrence list which contains those stored records which display said characteristic.

14. A method as claimed in claim 13 in which the said pointers are held in a lookup table.

15. A method as claimed in claim 1 in which the extracting step comprises searching the sample record for characteristics which appear in the characteristic list.

16. A method as claimed in claim 1 in which the extracting step comprises applying an operation to the sample record to generate one or more extracted characteristics.

17. A method as claimed in claim 1 in which the extracting step comprises applying an operation to the sample record to generate one or more sample outputs, and searching said sample outputs against said characteristic list.

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

and in which said matching step comprises 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 case occurrence list which records occurrences of each stored record that displays a corresponding characteristic.

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

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

21. A method as claimed in claim 1 in which the said extracting step is divided between a plurality of parallel processors, each forwarding a association result to a consolidator, said consolidator identifying stored records as possible matches in dependence upon said association results.

8. A method as claimed in claim 8 in which the list of characteristics is implicit and is not stored as a separate entity.

22. A system for identifying possible matches between a sample record and a plurality of stored records, the system comprising:

a list of characteristics, each characteristic having associated with it those stored records which display said characteristic;

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 is associated with a required number of extracted characteristics.

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

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

25. A system as claimed in claim 22 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 association results.