1 Matching Annotations
 Apr 2015

en.wikipedia.org en.wikipedia.org

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 ANDconstruction or ORconstruction of .[1] To create an ANDconstruction, 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 ORconstruction, 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.
Tags
Annotators
URL
