Definition
An LSH family is defined for a metric space, a threshold and an approximation factor . An LSH family is a family of functions satisfying the following conditions for any two points, and a function chosen uniformly at random from :
- if, then (i.e., and collide) with probability at least ,
- if, then with probability at most .
A family is interesting when . Such a family is called -sensitive.
Alternatively it is defined with respect to a universe of items that have a similarity function . An LSH scheme is a family of hash functions coupled with a probability distribution over the functions such that a function chosen according to satisfies the property that for any .
Read more about this topic: Locality-sensitive Hashing
Famous quotes containing the word definition:
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)
“One definition of man is “an intelligence served by organs.””
—Ralph Waldo Emerson (1803–1882)