# How can one quickly look up people from a large database?

## Vocabulary

• Face detection: Finding all faces in an image.
• Face representation: The simplest way to represent a face is as an image (pixels / color values). This is not very space efficient and likely makes follow-up tasks hard. Face embeddings are one other representation. In this case a face is a point on the unit-sphere in $$\mathbb{R}^{128}$$, IIRC.
• Face verification: Given two face representations, deciding if they are the same

## Question

I was just wondering how identifying a person with many potential people can work. So finding a face in an image works quite well and fast enough for most applications. Face verification as well. But I'm not sure how to scale this if you don't compare 1 face against 1 other face, but 1 against millions / billions of faces.

Suppose you have a lot of examples of faces with the identity of the person. Think of Facebook, where many people tagged friends. Or of countries with biometric passports.

In the real applications, the face verification task is easy because you can just brute-force compare against all candidates:

• Facebook: Only candidates are your friends, so ~200 candidates.
• Airport EU fast entry: Your face is compared against the passport. So only one candidate.

But then think about some dystopian books / movies, where cameras identify anybody. While tracking helps to reduce that problem, finding a match from millions / billions of examples is computationally super heavy. Assuming a single face verification takes ~200ms, for a million candidates it would already take 60h. For a billion users it would already be 6 years. For all people on earth who currently live it is 48 years.

So with that many candidates, you don't want to compare against all candidates.

When you use the face-embedding, it becomes a nearest neighbor search in $$\mathbb{R}^{128}$$.

Calculating the euclidean distance of two vectors in $$\mathbb{R}^{128}$$ takes roughly 15μs (see "timing" below). This means a single check over $$7.5 \cdot 10^9$$ people would take 31h. Way better, but still pretty long.

While the face-embedding approach pre-computes a good face representation, going over all examples is still a pretty dumb approach. If it was only $$\mathbb{R}^1$$, one could make a simple binary tree. For few dimensions, I think something like a k-d-tree might work. But what about 128 dimensions?

Is there another approach to get the person quicker?

## Timing

import numpy as np
durations = timeit.repeat('np.linalg.norm(a-b)',
setup='import numpy as np;a=np.random.random(128);b=np.random.random(128)',
repeat=1000,
number=3)
print('min: {min:5.1f}μs, mean: {mean:5.1f}μs, max: {max:6.1f}μs'
.format(min=min(durations) * 10**6,
mean=np.mean(durations) * 10**6,
max=max(durations) * 10**6,
))
• Have you ever employed Siamese Network and triplet loss? There are already many models which are trained for large scale different faces. Apr 19, 2019 at 10:34
• I think you might have overlooked the link where I mention Face Embeddings. With 10^9 candidate identities, this is still pretty slow. Apr 19, 2019 at 10:52
• Well, let's say that in another way. In such context where you need a quick look up, there should be a kind of trade-off between accuracy and speed. A possible solution can be using grouped convolutions and distributing the calculations to different computing units in order to increase the throughput. It can have good accuracy. I don't know whether you are familiar with distributed Tensorflow, but it is possible though the architecture would be changed drastically. Apr 19, 2019 at 11:04
• Are you suggesting to build a neural network with 10^9 classes? If not, please elaborate why you think grouped convolutions / Tensorflow would be of any help. Apr 19, 2019 at 11:07
• Yes exactly, but in such cases that you are sure you have a lot of parameters, you can distribute your calculations in order to increase the number of calculations in a specified period of time. If you have enough computational power, say 10 GPUs, instead of stacking those one after another, you can simply do a subset of calculations on each and then gather them together. The insparation is exactly like AlexNet. It's a common approach for increasing throughput. Apr 19, 2019 at 11:14

## 3 Answers

That is problem is call identification, mapping a percept to a specific entity.

One common option is hashing, take a percept and map it to a specific, unique integer. If two different percepts map to the same integer, they are the same entity. If two different percepts do not map to the same integer, they are different entities. Hashing takes constant time to look-up an entity no matter how many entities.

In the case of facial recognition, the hashing function is best learned through Deep Learning.

You could do this progressively. For example, you could cluster embedding and try to classify ethnicity, gender and age.

Then you only need to search for people in that ethnicity, gender and age.

Similar procedures to reduce the search region. Just by gender, you already reduce your number of comparisons by half, age can help you separate it in (say you use 10 years) about 11 parts (which will be of different size, but still a nice improvement), you can reduce it further by separating by ethnicity.

### Demographics of the world (Wikipedia)

Age: According to the 2006 CIA World Factbook, around 27% of the world's population is below 15 years of age.

• 0–14 years: 26.3% (male 944,987,919/female 884,268,378)1
• 15–64 years: 65.9% (male 2,234,860,865/female 2,187,838,153)1
• 65 years and over: 7.9% (male 227,164,176/female 289,048,221) (2011 est.)1

Gender: This can be approximated by half/half distribution

Ethnicity: The largest ethnicity is Han (Sino-Tibetan -> Chinese) with 1.3 billions of members

So, for the worst case, with a 15-64 years world person, male or female, from Han ethnic group you have

$$1.3 \times 10^9 \times 0.5 \times 65.9\% = 428.35 \times 10^6 \text{ people}$$

Using your time estimate of $$15 \mu s$$ we have:

$$15 \times 10^{-6} \times 428.35 \times 10^6 = 1.78 \text{ hours}$$

The second worst case would be Arabs of the same age, which would take about $$37 \text{ minutes}$$ and for UK it would take about $$18 \text{ minutes}$$

This is still a slow procedure, but you can probably find clusters inside this large groups to reduce the search time even further.

I suppose it is viable to separate age 15-64 into at least 3 groups. If this can be done

• I appreciate the idea to cluster and discard some clusters completely. The problem with the discarding part is that you can't be sure about the cluster membership. A 64-year old can easily look like a 65 year old and some might look like 40 year olds. The problem is not that some people look older/younger, but that you can't clearly decide at the borders of the clusters. And once you make fuzzy clusters the computational advantage vanishes. Apr 19, 2019 at 18:25
• That is true, that might give you a bit of accuracy tradeoff. The ideal approach would be to ignore our knowledge of humans and let a clustering algorithm divide human population into clusters. Apr 19, 2019 at 18:29
• Other thing that can be done, is to limit by known location, for example if someone is known to be highly likely to be in Asia you don't need to compare to someone in America, that could give us a nice reduction. Something else you need to put in mind is that this is a algorithm that is capable of recognizing humans better than humans itself, we are a race that is known for a face-processing capabilities and to overcome us in this cognitive ability by so much as to know every human in a country or in the world is just ... don't have a word for it hahaha Apr 19, 2019 at 18:34
• Also, by age division someone that looks like 40 and is 65 would be on the 40 cluster since his embedding must have 40-years-old-like-features, and age would only be update by recent photos. Apr 19, 2019 at 18:37

You’ve got the right idea with a k-d tree. The basic idea is that you don’t calculate an embedding for every face every time you do a query - you keep your database up to date and store the embeddings you have already calculated in your index. When you get a “query” (a new photo of a face) you generate the embedding for that and then search the index (possibly a k-d tree) for embeddings nearby that new embedding. You can also have more than one index, so that if the face is spotted in London you can first query the index that only covers faces likely to be seen in London.

The most difficult part of your work is likely to be creating a good embedding, and you’d probably create this by generating a high-dimensional embedding with a neural network and then mapping this to a much smaller embedding using manifold learning (e.g. t-SNE or UMAP).

This article is about a team using a similar approach: https://datascopeanalytics.com/blog/building-a-visual-search-algorithm/

• Due to the curse of dimensionality I really doubt that k-d trees are that helpful (article) Jul 5, 2020 at 20:40
• The Wikipedia article suggests that you need >> 2^k samples to make k-d trees efficient, so as long as you use a sufficiently small embedding (e.g. k = 16) it would be usable. But you might not use k-d trees! Jul 5, 2020 at 21:14
• A common size for face embeddings is k = 128. 2^128 is about 10^38. We have less than 10^10 humans on earth. Jul 6, 2020 at 5:43
• You likely wouldn’t just use an embedding straight out of a neural network designed for classification. I have edited my answer. Jul 6, 2020 at 7:01