Adaptive short lists and acceleration of biometric database search

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.

BACKGROUND

It is often necessary today to retrieve and compare biometric samples, or other exemplary identification samples, in order to properly identify a person. For example, a DNA test may be run in order to determine a person's genetic history, and/or to identify a potential perpetrator of a crime. Biometric data is often kept for comparison and stored in large databases, potentially with millions of other specimens. For example, in one embodiment, the biometric data could comprise fingerprint scans and the database could be filled with fingerprint scans from all of the customers of a mobile phone company, all of the customers for a banking institution, and/or all arrested felons in a given state. The example of fingerprint information as one of the types of biometric data collected and stored is to be understood as exemplary only. Additionally, biometric data may be used for purposes other than identification, for example a user may need to provide a fingerprint or iris scan in order to complete an authentication process.

Biometric databases are often searched to find a match to a given sample input. The purpose of the search may be to confirm the identity of the source of the sample, or to find a source. One of the most important components of a modern biometric application is the comparison module, which supports recognition functionality. Comparison modules provide one way to numerically estimate the quality of a match of a biometric specimen against one kept in a database. Customarily, the quality of a match is called a comparison score.

Typically, large biometric databases can hold up to hundreds of millions of records. As a consequence, the biometric application and the comparison module need to produce and analyze millions of scores in real time. Unfortunately, this can often result in the process of determining a match requiring a lengthy period of time to complete. Determining a match may also require a significant amount of processor power. A solution to these problems is desired.

SUMMARY

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. These and various other features and advantages that characterize the claimed embodiments will become apparent upon reading the following detailed description and upon reviewing the associated drawings.

DETAILED DESCRIPTION

Biometric data can often be stored in large databases. Additionally, a single database may contain a plurality of identification mechanisms. These biometric identification mechanisms may include, for example, fingerprint images, DNA samples, RNA samples, iris scans, or any other mechanism for identifying an individual. Such a database containing biometric data samples may need to be searched against a received inquiry for a match. A database full of biometric data may be searched by a company. For example, a sample may be provided by a customer of that company in order to determine that customer's identity, or to grant access to the account related to that customer.

FIG. 1Aillustrates an exemplary biometric dataset containing a plurality of records. For example, as shown inFIG. 1A, a single database may contain a biometric dataset100. The biometric dataset100may comprise a plurality of biometric data records110, for example, over one million data records. In another embodiment, the dataset100may contain tens or hundreds of millions of data records110.

Searching dataset100may begin by a system receiving a probe102as well as instructions to compare the dataset100to find an exemplary match150to the probe102. The process of searching biometric dataset100for match150may require comparing each biometric data sample110against probe102, which may require a significant amount of time and processor power.

Staged Scoring Procedure

In one embodiment, to accelerate the process of finding a match150to a received probe102, a staged scoring procedure is implemented. The procedure utilizes a very fast but less accurate scoring routine to produce a shortlist of possible match candidates, for example, ten percent of the records originally searched. For a search conducted on dataset100, this may correspond to a first subset120as shown inFIG. 1A. The next step in the procedure could be, for example, using a more accurate scoring routine in order to obtain a second subset of results130, corresponding to a second shortlist. In one embodiment, the second subset of results130comprises ten percent of the results returned in the first subset120, or 1% of the original dataset. This process could continue to return a third subset140and continue further until a match150is identified. A series of more accurate scoring routines is thus used to repeatedly narrow the number of records until a top scoring match, or several top scoring matches, are reached. In one embodiment, the biometric dataset100ofFIG. 1Acould be narrowed to a series of, for example, five to ten fingerprint samples, of which match150is one, the samples then being presented to a user.

In one embodiment, as described above, during each phase of the scoring procedure, 90% of the previous dataset is eliminated, returning a shortlist comprising 10% of the previous dataset. However, in another embodiment, 95% of the previous dataset is eliminated, with 5% returned as a shortlist. In another embodiment, only 80% of the previous dataset is eliminated, with 20% returned as a shortlist. The advantage to returning a larger proportion as the shortlist is that a lower accuracy scoring routine, allowing a given phase of the scoring procedure to proceed more quickly, due to the exponential decrease in remaining records after each round. However, returning a shortlist with fewer results in a given phase may require fewer phases overall. Therefore, in an embodiment with an accuracy factor, A, the number of samples in a shortlist S, from an initial database D, after an nth phase, is dictated by Equation 1, below, where A is the percentage eliminated after each round.

Additionally, in each phase of the scoring procedure, a different percentage may be eliminated, for example 50% in a first phase, 80% in a second, 90% in a third, and 95% in a fourth, resulting in 0.05% of original samples remaining In another embodiment, at least two phases of the scoring procedure may eliminate the same percentage of data samples. Therefore, in an embodiment with accuracy factors A1-An, the number of samples left in a shortlist S, from an initial database D, is shown below:

FIG. 1Billustrates an exemplary computer with a comparison module. In one embodiment, computer10, conducts the staged scoring procedure set forth above. Computer10may comprise, in one embodiment, a random access memory (RAM)14module. In one embodiment, RAM14may store information about an ongoing phase of the staged scoring procedure. Computer10may also comprise, in one embodiment, a processor16which is used by comparison module20in determining whether an input sample22matches a sample in database30. In one embodiment, computer10also comprises a power source18. The computer10may further comprise, in one embodiment, an external display12on which results may be presented to a user. In one embodiment, the user may interact with a user interface90, either to input a sample through input22or to view results in display12.

In one embodiment, the database30comprises an index34and saved settings32. The database may also include, in one embodiment, a secure memory40that includes at least a series of identification data50. In one embodiment, the secure memory40cannot be directly accessed by a user, in order to prevent hacking or other misappropriation of the identification data50.

In one embodiment, the identification data may comprise fingerprint data60. In another embodiment, identification may comprise DNA data70. In a further embodiment, identification data may comprise other biometric data80. In a further embodiment, database30may comprise any combination of fingerprint data60, DNA data70or other data80. Further, while database30is shown with a single secure memory40, it is understood that the methods and systems described herein could apply to a plurality of databases all accessible by the comparison module20.

In one embodiment, each portion of identification data50illustratively includes a plurality of data models. For example, as shown, each portion of fingerprint data60stored in the secure memory includes a first model62, a second model64, up to and including an nth model66. In one embodiment, each of these models comprise an increasingly detailed record, with higher resolution. For example, the first model62may comprise only a few bits of data describing a fingerprint record60, while the nth model of fingerprint data60may comprise several kilobytes worth of data. For DNA data70, models72through76may comprise an increasing number of markers available for comparison. Each of the models may have a corresponding set of parameters that are also stored in the secure memory, for example, model one parameter92, model two parameter94, model three parameter96, up to and including model N parameter98. In this way, the database can be searched through increasingly specific models in series. In one embodiment, the data models62through66are generated according to parameters92through98in response to receipt of a probe102, and are not stored as separate records in the database100. In another embodiment, each time database30receives a new fingerprint data sample60, successively details models are accessed and stored separately as different records in database30.

In an exemplary staged scoring procedure, after a probe102comprising a sample fingerprint is received, a first phase in initiated. In the exemplary first phase of a staged scoring procedure, model one dataset62is used to create a first shortlist from the dataset100. In the second phase of the exemplary, model two dataset64is used against the first shortlist to generate a second shortlist, where model two dataset comprises higher resolution data than model one dataset. Increasingly detailed datasets are used to generate increasingly reduced shortlists until the nth phase, where the nth model dataset66is compared against the (n−1) shortlist, to generate the nth shortlist which, in one embodiment, is the final result set.

The shortlists created during a comparison are typically stored in the RAM14in order to reach maximal possible processing speed. In one embodiment, only one shortlist is generated at a time, such that the second shortlist is generated by eliminating non-matching samples from the first shortlist, and such that the third shortlist is generated by eliminating non-matching samples from the second shortlist, and continuing until the nth shortlist is generated.

FIG. 2Ais a flow diagram of a method for determining a match based on model data.FIG. 2Ashows an exemplary method200for iteratively narrowing a series of samples within a biometric database, for example database100, in order to determine a match to a received probe, for example probe102. In one embodiment, method200is designed to run as an iterative method.

In one embodiment, the method200starts at block210wherein an initial search request is received. This may, for example, be a probe provided by a company in one embodiment. It could also, for example, be a fingerprint entered as part of a search of a police database.

In one embodiment, the method200then moves to a loop comprising blocks220and230. In block220, a matching phase is completed and a shortlist is generated based on the scoring procedure described above. In block230, the list of results is compiled and, in one embodiment, an indication is provided to a user that an iteration has completed. In the first iteration of a staged scoring procedure, the model of the fingerprint comprising the smallest size is used, for example, the first model62as shown inFIG. 1B. The smaller model size allows the first scoring run to be completed very quickly, but with less accuracy as the smallest model has the lowest resolution. The output of this first scoring round (in one embodiment, ten percent of the samples input) is then presented as the list of results230.

In one embodiment, as part of the search request process in block210, a user can input a desired number of matches, for example a top 10 or a top 100 potential matches. If the list returned in block230is greater than the number of the maximum result that a user desires, the process then goes back for another round of matching as shown by arrow232back to block220. When method200returns to block220, in one embodiment an iterator is increased to reflect another iteration has started.

The output of the first scoring round230is, in one embodiment, used as the sample set for the second scoring round. The next smallest size model is used for the second scoring round, for example, the second model64of fingerprint data, resulting in an increased accuracy with the increase in resolution presented by the increase in model size. In one embodiment, the model size corresponds to an iterator, for example iterator2may trigger the use of model dataset64. The second iteration then allows for an increased amount of time per comparison as the analysis time for each sample increases with the increasing resolution. The output of this second scoring round (in one embodiment ten percent of the samples input, or one percent of the original database) is then used for the sample set for the third scoring round, during which a third model size may be used. The model size increases with each iteration until model size N66is used, in the nth iteration.

The use of a staged scoring process, such as that of method200, increases the efficiency of the comparison module as increased analysis time is only required on smaller and smaller sets of biometric records. In one embodiment, the desired number of samples is a single match. In another embodiment, the desired number of samples remaining is less than five, or less than 10, or less than 25. Once the desired number of results is less than a maximum preset number which, for example, is stored in settings32of the database30, the iterative portion of method200ends, and the process moves onto block240, where the results are presented to a user, or otherwise returned to the requestor of the database comparison.

In one embodiment, samples are added to a shortlist or discarded, in method200, based on a scoring and sorting procedure, with all but a top percentage of scores (e.g. the top 50% or 10%, or 5%) being discarded. In another embodiment, samples are scored and kept only if their comparison score is above a threshold elimination score.

FIG. 2Bis a flow diagram of an iterative method for determining a subset of potential matches in accordance with an embodiment of the present invention. Method202involves scoring and optional sorting matches based on comparison scores. Method202, in one embodiment, includes a scoring process during each iteration. Method202starts with a first iteration and continues until an nth iteration results in a final shortlist, which is presented to the requestor of the comparison. In one embodiment, the nth shortlist may comprise a single sample. In another embodiment, the nth shortlist may comprise the top 5 or 10 samples.

Method202begins at block250where a full database, with sample size Z is presented with a query. Method202then starts an iterative process comprising blocks252,254,258,260,262and an optional step256, as shown inFIG. 2B.

Each iteration starts in block252with an iterator updating. In one embodiment, the iterator starts at 1, and increases by 1 each time the method progresses through the loop of blocks252-262. The iterator, then, corresponds to the shortlist number currently being generated. In one embodiment, each successive shortlist replaces a previous shortlist. In another embodiment, an indication of a sample's presence in a specific shortlist is stored with the data sample, or as part of index34. In another embodiment, indications of samples present on a current shortlist are only stored in RAM until the iterative process returns a final set of potential matches.

In block254, a set of I samples is processed, where I corresponds to an input set, which, in one embodiment, is the previously created shortlist. For example, in comparing a probe against a database of 10,000,000 samples, in a first iteration, I corresponds to all 10,000,000 samples of the database. In a second iteration, where the top 10% of samples are kept, I corresponds to the remaining 1,000,000 samples. In a third iteration, I corresponds to the remaining 100,000 samples. The process may continue until, for example, 10 samples are presented to a user as the final result set in block270. The processing of block254may comprise, in one embodiment, comparing a model, corresponding to the iteration number in one embodiment, of each sample of sample set I against a given probe, and assigning a comparison score to each of the samples.

In one embodiment, the scored samples I are sorted, in block256. This may be necessary, for example, in an embodiment where the scores are obtained on multiple processors. However, in an embodiment where scores are normalized, for example the methods discussed inFIGS. 3A-3Bbelow, such a sorting process is not required.

FIG. 2Cdepicts a method for conducting a match round. In one embodiment, each match round of the process ofFIG. 2AorFIG. 2Bcomprises method275. Method275illustratively starts in block276, with a match round starting. This may be the first iteration, or a later iteration in a staged scoring procedure.

In one embodiment, the method275continues in block278, with a model being selected. In one embodiment, for each record102, a series of models is stored within the database30.

In another embodiment, the model to be used in each iteration is generated based on the number of iterations to be conducted. For example, computing device10may determine, based on a database size of 10,000,000 and an accuracy factor of 10% that 6 iterations will need to be conducted in order to return a result set of 10 potential matches. This may determine, in one embodiment, that 6 models of increasing resolution for each given biometric data sample102is generated. These models may be generated on-the-fly such that only when a potential match is added to a shortlist is a successive model generated. In another embodiment, a series of models may be generated based on the stored parameters92-98. The generation of models to be used for a given match round is shown in optional block286.

Once the model has been selected, a comparison is conducted for each biometric sample, in block280. After each comparison, a score is assigned to the biometric sample, as shown in block282. Once all of the biometric samples have been scored, a shortlist is generated in block284. The shortlist of block284may be generated, in one embodiment, in a manner similar to that shown inFIG. 2B. Once the match round is completed, the method either returns to block276, if another iteration is needed, or the results are presented to the requestor, in block288, if the current match round was the last iteration.

In one embodiment, subset O, corresponding to the samples output from a given iteration, is generated in block258. Subset O may be generated, at least in part, based on the scores of sample set I. In one embodiment, subset O is generated by taking a top percentage of scored samples in sample set I. In another embodiment, subset O is generated by taking all samples from sample set I above a given threshold score. Samples from sample set I that do not become part of subset O are discarded in block260.

In one embodiment, subset O is presented to the user as the current shortlist. In another embodiment, the comparison module automatically converts subset O into the next sample set I, and the next iteration begins, as indicated in block262. In one embodiment, the subset O is stored in RAM14during the iterative process. The method then continues until a final result set is provided to a user in block270.

Staged Scoring Without Sorting.

One of the problems of using a conventional comparison model, involving sorting and scoring, is that such a method is difficult to run in parallel, because of the need to recombine and sort the scored samples after each iteration. One difficulty of sorting algorithms is that they are not efficient in high parallelization, as, after each iteration, the scores must be compiled across each of the parallel processors to allow for sorting. This limits the efficiency of the comparison model, increasing the time it takes to complete a comparison, or each iterative stage of a comparison, considerably.

Additionally, an inevitable overhead of the conventional approach is the necessity to keep the shortlists sorted. Given the database size of, for example, ten million, in one embodiment, a shortlist may need to keep a sorted list of one million scored samples. This has a negative impact on the identification speed of the biometric application. This lack of efficiency results as, after each stage, the lists created by the different parallel processors must be recombined and sorted before they can be segmented and run again on the parallel processors.

Another important factor in any biometric application is that scores are, in part, random. The reason for this is that biometric specimens may contain at least some noise. This fact makes it much more difficult in choosing a threshold numerical value in order to determine whether a score should be included in a shortlist. Further, in many cases, biometric scores obey a Gaussian distribution. Typical normalization procedure implies computing an average α, and standard deviation σ, and replacing a given comparison score X for a given sample, with (X−α)/σ. This allows the staged scoring procedure to be run across parallel processors as the need to recombine shortlists after each phase is removed. Instead, the shortlist generated on each parallel processor can be normalized against itself during each stage. This removes the necessary step, in a conventional comparison procedure, of recombining the shortlists of all of the processors in between each iteration of the staged scoring procedure.

Assuming that a score distribution is approximately normal, which is true for at least the first iteration of a staged scoring procedure, and continues to be true as long as the shortlist remains sufficiently large, it may be possible to eliminate the need for sorting during each iteration. A process of scoring without sorting is presented inFIG. 3A, for a biometric database with N samples.

FIG. 3Adepicts a method for creating a shortlist of potential matches. InFIG. 3Aa method of determining a potential match300first starts by retrieving a full set of biometric samples from a database in block302. The method then moves on to a comparison step in block304, where all samples from the full database are compared against the probe102, and scored accordingly. This first step of scoring requires a normalization of scores: each score Xiis replaced with Yi=(Xi−X)/σ, whereXdenotes the score mean value and σ is the corresponding standard deviation.

The next step is to compute a threshold value T, according to block310, that the normalized scores can be compared against in block312. The threshold value T is computed according to equation 3 below.

For example, assume that the database consists of N=one million records, and the goal of a first iteration is to have a shortlist of the length Ns=100,000. In that case, the right hand side of equation is equal to 0.1. Solving this equation yields T=1.28. Solving Equation 3 can be done by using z-score lookup tables. The value of T obtained in this manner is called the adaptive scoring threshold value.

Once the threshold value has been computed, the method then moves to block312where each score in the set of biometric samples is compared against the threshold value. If the score is less than the threshold value, the sample moves to block314where it is discarded. If the score for a specific sample is greater than or equal to the threshold value it is added to the shortlist in block316. In one embodiment, being added to the shortlist comprises remaining on the current list, which becomes the shortlist once all samples with scores below the threshold value are discarded. In another embodiment, a new shortlist is created in each iteration, and all samples with scores above the threshold value are added to the new shortlist.

Once this process has been completed for all of the samples in a given biometric sample set, this size of the newly generated shortlist is then compared to a desired result size. If the shortlist is greater than the desired result size, the method returns to block302for another iteration. The iterative process of blocks302,304,306,308,310,312and316is repeated until the shortlist size is the desired result size. In one embodiment, the shortlist size of each successive iteration is always ten percent of that of the previous iteration. So, for the example above, starting with one million records, the first shortlist size is 100,000, the second shortlist size is 10,000 the third shortlist size is 1,000, the forth shortlist size is 100, and the final shortlist size of 10 may be presented to the user as the final result318. While this example uses 10% as the exemplary accuracy factor, any other appropriate cut-off measure could be used, for example 20%, 5%, 2% or 1%.

Notably, in method300, the samples do not need to be sorted during the various iterations. The expensive sorting process can now be replaced by an elementary comparison of whether or not the score is above or below a given threshold, T. This enables a user of method300to significantly accelerate searching of a biometric database without any impact on accuracy, both by eliminating the time-consuming sorting step, and by the ability to run the process in parallel.

Method300may also be applicable to the sample set where a score distribution is not normal. The equation to be used to determine the threshold value T then reads:

Here p(U) is the empirical probability density for the score distribution. Based on the score statistics, one can calculate lookup tables for threshold values T for a typical range of ratio (Ns/N). In one embodiment, the system automatically detects whether a score distribution fits a normal distribution, for example in block308and calculates threshold value T accordingly in block310.

A significant advantage to method300is that it allows a biometric database to be sorted in parallel. In addition to removing the time taken in a traditional module for sorting, this also allows the process to be further shortened because processors may efficiently run the various iterations in parallel.

FIG. 3Bdepicts a method320of determining a shortlist by running a series of matchers in parallel, across processors1-N. In one embodiment, method320runs across two processors. In another embodiment, the method320runs across four processors. However, method320can be run across any number of processors. In one embodiment, after each iteration, the shortlists of the plurality of matchers1-N are recombined and redistributed among the matchers1-N. In another embodiment, as shown inFIG. 3B, the shortlists are not recombined until they are presented to a user as a final list of results.

In one embodiment, the processors running the various matchers in parallel are separate core processors, part of a multi-core processor. In another embodiment, different cores are segmented such that a plurality of matchers run on a single processor core. In another embodiment, a single processor may be segmented into a series of sub processors, each of which may support one of matchers1-N.

Method320starts in block322with the full set of biometric data samples, of size Z. The records are then split into a series of N record sets in block324. Each of these N record sets are then assigned to a matcher, such that matchers1-N each receive a set of records of roughly the same size. The size of records may be, in one embodiment, determined by evenly distributing the database across the different matchers such that each matcher receives Z/N records.

Block326illustrates Matcher1receiving the first set of records and searching the first set of records for potential matches and assigning a score based on a comparison between each record and a received probe. Matcher2, as shown in block328, receives a second set of records, which Matcher2scores against the received probe. In block330, MatcherN receives an nth set of records, which it scores. In one embodiment, Matcher1-MatcherN conduct their searches simultaneously. In another embodiment, each matcher starts its comparison instantaneously upon receiving its record set, such that a small lag may develop between the Matchers. The process by which each Matcher computes scores for each sample in their record set is similar to that illustrated for a single process inFIG. 3A.

In one embodiment, the scores from all matchers each progress through block332, where a score distribution is computed. In one embodiment, each Matcher individually computes a score distribution. In another embodiment, the distributions from the different matchers are further computed against each other. At this point, each of the Matchers then normalizes its respective scores, as shown in blocks334.

Once the scores have been normalized, method320moves to blocks340, where each Matcher compares its record set to the threshold value. In one embodiment, because each matcher scores, normalizes, and computes its threshold value individually, each matcher keeps the same fraction of records from one iteration to another.

Scores that are not equal to or greater than the threshold value T are discarded from a shortlist for each Matcher, as shown in blocks350. The remaining samples become part of the shortlist for each Matcher, as shown for Matcher1in block362, Matcher2in block364, and MatcherN in block366. If, combined, the number of records in each shortlist is smaller than, or equal to, a preset amount, the results are recombined in block368and presented to the requesting entity. If the shortlists are greater than a preset final result amount, each shortlist becomes the basis for the next iteration.

Although the present invention has been described with reference to preferred embodiments, workers skilled in the art will recognize that changes may be made in form and detail without departing from the spirit and scope of the invention. For example, while embodiments of the present invention have been described with respect to fingerprints, as fingerprints provide a unique and reliable biometric sample for authentication, one skilled in the art would understand that other biometric data could also be used with the systems and methods described, for example iris patterns, DNA, etc.