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:
“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)
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)