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,
              ))
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.