Adaptive short lists and acceleration of biometric database search

• US 10,025,831 B2
• Filed: 04/02/2015
• Issued: 07/17/2018
• Est. Priority Date: 05/15/2014
• Status: Active Grant

• Current Assignee: Bio-Key International Incorporated
• Original Assignee: Bio-Key International Incorporated
• Inventors: Zhdanov, Renat, Ouchveridze, Alexander
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US14/677,061
• Publication Number:
  US 20150331867A1
• Time in Patent Office: 1,202 Days
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 50/00 ICT programming tools or database systems specially adapted for bioinformatics
• CPC Class Codes: G16B 50/30 Data warehousing; Computing architectures

Abstract

A system for comparing a biometric sample against a biometric dataset is provided. In one embodiment, a system for comparing a biometric sample against a biometric dataset comprises a database storing at least one biometric dataset. The system may also comprise a comparison module configured to iteratively provide a comparison score for each record in the biometric dataset, wherein the comparison score indicates a likelihood of match between an individual record in the biometric dataset and the biometric sample; wherein, during each iteration. The steps in the iteration may comprise retrieving a model of each of the plurality of records. The steps in the iteration may also comprise comparing the model of each of the plurality of records against the biometric sample. The steps in the iteration may also comprise generating the comparison score for each of the plurality of records. The steps in the iteration may also comprise iteratively compare the biometric sample against a plurality of records. The steps in the iteration may also comprise wherein the resolution of the retrieved model increases with each iteration, and where the iterative process continues until a final list of potential match candidates is determined. The system may also comprise a processor configured to receive data indicative of the biometric sample and iteratively engage the comparison model such that results of the first iteration are provided as an input to a second iterator.

Claims

1. A system for comparing a biometric sample against a biometric dataset, the system comprising:

a database, storing a biometric dataset, as well as a series of models for the biometric dataset, wherein each of the series of models comprises a different resolution for the biometric dataset;

a comparison module that iteratively provides a comparison score for each record in the biometric dataset, wherein the comparison score indicates a likelihood of match between an individual record in the biometric dataset and the biometric sample;

wherein, during each iteration, the comparison model completing a series of steps during each iteration comprising;

retrieving a model with a resolution of each of the plurality of records;

comparing the model of each of the plurality of records against the biometric sample;

generating the comparison score for each of the plurality of records;

iteratively compare the biometric sample against a plurality of records; and

wherein the resolution of the retrieved model increases with each iteration, such that, during a second iteration, a second resolution for a second model is higher than a first resolution for a first model, and wherein the results from the first iteration are provided as the input for the second iteration; and

wherein the iterative process continues, with successively fewer results with each iteration, until a final list of potential match candidates is determined, and wherein increasing the resolution with each iteration comprises retrieving a new model with a higher iteration than that used in a previous iteration, and wherein comparing the model of each of the plurality of records occurs in each iteration with the plurality of records left from the previous iteration in an unsorted format; and

a processor configured to receive data indicative of the biometric sample and iteratively engage the comparison model.

2. The system of claim 1, wherein, at the end of each iteration, a shortlist is created of remaining candidates, and wherein each of the shortlists is stored in RAM such that a current shortlist replaces a previous shortlist.

3. The system of claim 1 wherein the model used in a given iteration is generated by the processor at least in part by an indication of iterations needed to get to a size of the final list of potential match candidates.

4. The system of claim 1, wherein the model used in a given iteration is generated by the processor at least in part based on a set of stored parameters.

5. The system of claim 1, and further comprising:

a display configured to display the final list of potential matches.

6. A computer-implemented method for selecting a plurality of potential match candidates from a biometric dataset, the method comprising:

receiving an indication of a biometric sample;

computing a comparison score for each of a plurality of biometric records within the biometric dataset, wherein the comparison score for each of the plurality of records indicates a likelihood of match between each respective biometric record and the biometric sample;

comparing the comparison score for each of the biometric records against a threshold value;

generating a shortlist of potential match candidates to the biometric sample, wherein the shortlist is less than the full set of biometric records;

iteratively repeating the steps of computing the comparison score, comparing the comparison score against a threshold value, and generating the shortlist until the shortlist size is less than or equal to a desired results size;

wherein, for each iteration, the comparison score is computed based on a retrieved model of each of the plurality of biometric records, wherein the retrieved model is one of a plurality of potential models, and wherein, for each iteration, the retrieved model increases in resolution, and wherein the shortlist from the previous iteration is used for the second iteration, such that, for each iteration, a higher resolution model is used on a smaller set of biometric records; and

providing the shortlist as an output once the shortlist size is less than or equal to the desired result size.

7. The computer-implemented method of claim 6, wherein computing the comparison score for each of the plurality of biometric records comprises computing an initial comparison score for each of the plurality of biometric records, calculating a mean, a variance, and a standard deviation for the biometric dataset and normalizing the initial comparison scores for each of the plurality of records.

8. The computer-implemented method of claim 7, wherein, upon detecting a normal distribution of initial comparison scores, the threshold score is calculated based on the normal distribution.

9. The computer-implemented method of claim 7, wherein, upon detecting an abnormal distribution of initial comparison scores, the threshold score is calculated based on the abnormal distribution.

10. The computer-implemented method of claim 6, wherein generating a shortlist of potential candidates comprises discarding a plurality of biometric records with comparison scores lower than the threshold value.

11. The computer-implemented method of claim 6, wherein generating a shortlist of potential candidates comprises adding each biometric record with a comparison score greater than the threshold score to a new shortlist.

12. The computer-implemented method of claim 6, and further comprising:

selecting a model for comparison, wherein the model corresponds to the resolution of each of the biometric records, and wherein the resolution of the selected model increases each time the steps of computing the comparison score, comparing the comparison score against a threshold value, and generating the shortlist are conducted.

13. The computer-implemented method of claim 6, wherein each time the steps of computing the comparison score, comparing the comparison score against a threshold value, and generating the shortlist are conducted, the number of remaining biometric records decreases exponentially.

14. A computer-implemented method for selecting potential match candidates from a biometric dataset, the method comprising:

receiving an indication of a biometric sample;

assigning a plurality of records from the biometric dataset to a plurality of matcher units, wherein each matcher unit is assigned to one of a plurality of processors on the computer;

wherein each matcher iteratively determines a list of potential match candidates for the biometric sample, wherein each iteration comprises the steps of;

computing a comparison score for each of the plurality of records assigned to the matcher, wherein the comparison score is computed by retrieving an iteration model for each of the plurality of records, wherein the iteration model is selected from a set of potential models, each potential module having a different resolution, and wherein each potential model corresponds to each of the plurality of records; and

wherein the iteration module is selected such that a second iteration model is a higher resolution than a first iteration model, wherein the second iteration comprises a second plurality of records, received as a result from the first iteration, the second plurality of records comprising fewer records than the plurality of records;

comparing the comparison score for each of the plurality of records against a threshold score; and

generating a shortlist of potential match candidates to the biometric sample, wherein the shortlist is less than the full set of biometric records assigned to the matcher.

15. The computer-implemented method of claim 14, wherein each of the plurality of processors on a computing device comprises a subprocessor.

16. The computer-implemented method of claim 14, wherein computing the comparison score for each of the plurality of biometric records comprises computing an initial comparison scores for each of the plurality of biometric records, calculating a mean, a variance, and a standard deviation for the biometric dataset and normalizing the initial comparison scores for each of the plurality of records.

17. The computer-implemented method of claim 16, wherein each matcher is further configured to detect distribution type of initial comparison scores and calculate a threshold score, and wherein the distribution type is detected as either normal or abnormal.

18. The computer-implemented method of claim 14, wherein generating a shortlist of potential candidates comprises discarding a plurality of biometric records with comparison scores lower than the threshold value.

19. The computer-implemented method of claim 14, wherein generating a shortlist of potential candidates comprises adding each biometric record with a comparison score greater than the threshold score to a new shortlist.

20. The computer-implemented method of claim 14, and further comprising:

.

selecting a model for comparison, wherein the model corresponds to the resolution of each of the biometric records, and wherein the resolution of the selected model increases each time the steps of computing the comparison score, comparing the comparison score against a threshold value, and generating the shortlist are conducted.