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:
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)