The power of locality sensitive hashing is
closely related to the behavior of this
particular function one minus something to
the power k.
Full, which is then raised.
To the power of b, and then again subtract
it from one.
This particular function, as you can see,
is a very steep one.
With the result that this particular value
pq which is nothing but the probability of
a match in one of the locality sensitive
functions f, is amplified.
So even if this value pq is fairly
moderate, you know, say something close to
0.1 or 0.15, it really becomes amplified
to a very large value giving a very large
probability of match.
At the same time, the false match
probability is driven to zero as long as
it is a little smaller say 0.07.
Fairly close to something like 0.15, but
it gets driven to a very small value as
long it's reasonably smaller than pq.
The place where this steep rise happens
depends on the choices of k and b.
And by suitably adjusting it, these
parameters depending on our values of p
and pq, we can get the required behaviour
all that we want to achieve.
Alesage has many Important applications
which fall under the big data category
these days.
For example, when you have hundreds of
millions of tweets, how do we group
similar tweets without having to compare,
all the pairs?
Which is an impossible task.
But since there is n square pairs and if n
is in the hundreds of millions, it just
becomes impossible.
So LSH which is one way out.
In enterprise search, we saw the problem
of finding near duplicates or versions of
the same root document.
This is another problem which can be
addressed using LSH.
Finding patterns in time series from
sensors where you have multiple sensors
capturing many different parameters such
as from a car or from a piece of machinery
or from a ship, and you want to find
patterns in that time series, then LSH
like concepts turn out to be useful there
as well.
Another example which is also discussed in
the Anand Rajaraman book is resolving
identities of people from different
databases or multiple inputs.
An example of such a problem is, one is
described in the book resolving databases
from different systems, other example is
figuring out which Twitter ID's match
which Facebook ID's and which LinkedIn
ID's and which e-mail ID's now this is
private information which people want to
keep separate but there are many companies
which are engaged in figuring out using
concepts like LSH which identities
actually should be clumped together are
very likely to be from the same person.