1
$\begingroup$

I have been thinking about this problem and reading some related papers for sometime.

The problem can be described as follows:

Suppose that each biometric template is a $d-$dimensional vector. A database is composed of $n$ such templates ( $n$ could be large, like 1 million). Given a query template $q$, the task is to identify the "closest" template according to some distance metric.

Now, since the dimension $d$ and the database size $n$ could be both large, it is not quite efficient to linearly scan the whole database.

So my question is, are there any algorithms to efficiently fulfill the above task? What are the state of the art algorithms for biometric identification?

Through some literature review, I can think of two approaches. But both of them seem to have some limitations.

  1. Building space partitioning index like R-tree. The problem is that such index does not suit for high dimensional data. The final search efficiency would be close to linear search.

  2. Locality sensitive hash. The problem is that this method can only provide approximate searching result. For biometic identification, it is not guaranteed that the matched template could be found.

Improve this question
$\endgroup$
2
  • $\begingroup$ If this is properly stored in a database using indexes might be quite fast to retrieve the $n_i$ template if one variable should be identical. Otherwise it can be reduced to a n-dimensional through PCA techniques, and predict where the query q might fall on the dimensions, thus look on the nearest templates. $\endgroup$
    – llrs
    Sep 22, 2017 at 14:36
  • $\begingroup$ In practice: a) have cluster precompute all pairwise distances, so that you can query similarity to other records b) exploit specifics of your distance metric [with a million records or so this is usually still fast enough if your workstation is large enough to hold full matrix in memory, so that speed doesn't become an annoyance]; note that the possible modifications on the space and strategy and valid simplifications will depend on your distance metric $\endgroup$
    – tsttst
    Oct 1, 2017 at 15:59

1 Answer 1

Reset to default
2
$\begingroup$

I think that a very nice example of what you are talking about saying the word bigger, is probably a microarray transciptional analysis of RNA extracted from a biological sample. Simplifying, in these analyis, each observation is analised on, up to 10000 genes expression levels of different mRNA coding genes. Thus, from these type of molecular biology experiments, we obtain matrices with few observations (d, the samples) respect to the dimensions observed (k, the target gene expression levels). Well, d << k. In this situation, in order to perform a classification-like task, and to reduce the problem of the overfitting related with dimensionality maledition, the ways that we might follow are several:

1) PCA: it is a good tool to visualize multidimensional datasets reducing dimensionality and noise level in the consolidated and standardized data. Problem: it is an unsupervised machine learning algorithm. Alone, it haven't the capacity of class discrimination.

2) PCA-LDA is a good combination, where PCA eliminates hyperdimensionality and background in our data sheets, and than LDA (linear discriminant analysis) finds the directions onto the new subspace of characteristics, that are able to maximize variances between classes and decrease the variances within these. For this reason LDA is known as a kind of supervised machine learning technique. Furthermore, PCA and LDA are usually used together because LDA applied on high dimensional datasets could lead us toward overfitting problems. After the training of PCA-LDA pipeline, being LDA a classificator object trained and shaped on the principal component subspace, you can use this to examine new unknown samples or observation and predict its class by similarity. e.g. recently, Martin et al., on a Nature article talk about PCA-LDA approach to identify and than to predict cancer cells from those are normal, starting from ranman spectra of tissues.

3) PCA-LDA on transpose matrix: to use as better as possible the huge dimensionality, some authors used to transpose the initial matrix in order to force positioning of genes as rows and samples as columns. Then, the subsequent LDA is performed not on PC scores, but on loading factors of the eigenfactor matrix obtaining thus the list of the most important discriminant gene expression levels to segregate normal samples to cancer ones.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.