Let's consider some other kinds of search
now.
So far, we have been indexing objects,
such as documents, by the features they
contain, which are words.
Or in the case of records in a database,
they are the contents of different
columns.
Our assumption has been that when we
search for a document or a record, our
query is a bag of words.
In other words, features are what we
search with.
But suppose our query is itself an object.
For example, an image, such as in Google
Goggles or Google Image search, or a
bio-metric, such as a fingerprint and iris
scan in the example of the unique
identification project of the Government
of India.
For those of you not familiar with this,
ambitious and equally controversial
project, it aims to...
Every resident of India with the unique
bio-metric ID.
We will return to this in a minute.
But coming back to the question of
searching for an object is in inverted
index of features, whether they are words
or image features, or other features in
the case of fingerprints and irises, the
best way to search for objects.
What do you think?
I would say that, no, it probably is not
the best way to search for objects.
As to why, I encourage you'd all to think
about this.
And discuss this, on the discussion forum.
But, right now we're going to discuss.
Another very powerful method, called
locality sensitive hashing.
In-, invented by Indic and Motwani in the
late'90s, and described in.
Fair detail in the Anand Rajaraman book,
which is a reference for the course.
This technique is particularly important
in all kinds of big data applications
because it somehow manages to compare, at
least approximately, n pair of objects in
linear, that is order and time.
There are n square pairs, but it manages
to tell us which pairs are actually close
together without actually comparing all
pairs.
Sounds like magic, let's see how.
The basic idea of locality sensitive
hashing, LSH as we shall refer to it going
forward.
Is the following.
It's hashing so, an object is obviously
hashed a something called HX.
In a manner so as, that if X and Y are two
objects.
And if X is close to Y.
Then the two hash functions are equal with
high probability.
In this respect its similar to normal
hashing where if X is equal to Y, then X
and Y are hashed with high probabilities
that you are just saying value.
But this deals with, distances and
closeness and not just equality and
that's, that's what makes it interesting.
Its hashing which is sensitive to things
being close together or in the same
locality.
And conversely obviously if x is not close
to y, rather x is far from y, then the two
hash functions will not be equal with a
high probability.
Of course constructing the hash functions
themselves is quite tricky.
And here, we have to.
Do interesting things like.
Take random functions from locally
sensitive family.
And combine them in particular ways.
Allman and Roger Allman's chapter three
described this process.
Fairly well, and in considerable detail.
An example is biometric matching.
In the case of the UID project for
example, more than a billion people are
going to get biometric IDs.
Of these, more than 200,000,000 have
already been enrolled.
At the same let me make the following
disclaimer that, what the UID actually
uses internally is proprietary and I'm not
intending to suggest that they use
locality sensitive hashing.
This is merely a motivating example.