Locality-sensitive hashing: Difference between revisions

Revision as of 15:16, 23 May 2024

Revision as of 13:50, 25 June 2024

Line 7:

==Definitions==

A finite family <math> \mathcal F</math> of functions <math>h\colon M \to S</math> is defined to be an ''LSH family''<ref name=MOMD /><ref name=GIM1999>{{cite journal

| author1 = Gionis, A.

| author2-link = Piotr Indyk | author2 = Indyk, P. | author3-link = Rajeev Motwani | author3 = Motwani, R.

Line 30:

if it satisfies the following condition. For any two points <math>a, b \in M</math> and a hash function <math>h</math> chosen uniformly at random from <math>\mathcal F</math>:

* If <math>d(a,b) \le r</math>, then <math>h(a)=h(b)</math> (i.e., {{mvar|pa}} and {{mvar|qb}} collide) with probability at least <math>p_1</math>,

* If <math>d(a,b) \ge cr</math>, then <math>h(a)=h(b)</math> with probability at most <math>p_2</math>.