Statistical Speedups for Biometric Identification
David Naccache, Zdeněk Říha

By opposition to biometric matching, biometric identification is a relatively costly process. Let $B=\{b_1,\ldots,b_n\}$ be a database of $n$ biometric templates and let $b$ be a given individual biometric acquisition. The biometric identification problem consist in finding the $b_i$ corresponding to $b$. Whilst in reality matching algorithms usually return a score compared to a threshold, for the sake of simplicity this paper assume the existence of an oracle $\mathfrak{A}$ taking as $b$ and $b_i$, and responding with true or false: $$\mathfrak{A}(b,b_i) \in \{{\sf T},{\sf F}\}$$ Considering $\mathfrak{A}$ as an {\sl atomic} operation, any system-level optimization must necessarily minimize the number of calls to $\mathfrak{A}$ per identification session. This is the parameter that we attempt to optimize in this paper. We show that indeed, by using statistically justified comparison strategies considerable speed gains can be obtained.