Locality-sensitive hashing: Difference between revisions

Revision as of 04:38, 7 November 2023

Revision as of 04:41, 7 November 2023

Line 7:

==Definitions==

Consider aA family <math> \mathcal F</math> of functions <math>h\colon M \to S</math>. Weis saydefined thatto <math> \mathcal F </math> isbe 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 27:

* a threshold <math>r>0</math>,

* an approximation factor <math>c>1</math>,

* and probabilities <math>p_1 > p_2</math>.

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>: