An LSH family [1] [2] [3] is defined for a metric space , a threshold and an approximation factor . This family is a family of functions which map elements from the metric space to a bucket . The LSH family satisfies the following conditions for any two points , using a function which is chosen uniformly at random: 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[4] 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 . Amplification[edit] Given a -sensitive family , we can construct new families by either the AND-construction or OR-construction of .[1] To create an AND-construction, we define a new family of hash functions , where each function is constructed from random functions from . We then say that for a hash function , if and only if all for . Since the members of are independently chosen for any , is a -sensitive family. To create an OR-construction, we define a new family of hash functions , where each function is constructed from random functions from . We then say that for a hash function , if and only if for one or more values of . Since the members of are independently chosen for any , is a -sensitive family.