Locality-sensitive hashing - Revision history

UrgeSort: Add section for nearest neighbor without fixed dimensionality

2025-06-01T22:41:17Z

Add section for nearest neighbor without fixed dimensionality

← Previous revision		Revision as of 22:41, 1 June 2025
Line 299:		Line 299:
	* space: <math>O(n^{1+\rho}P_1^{-1})</math>, plus the space for storing data points;		* space: <math>O(n^{1+\rho}P_1^{-1})</math>, plus the space for storing data points;
	* query time: <math>O(n^{\rho}P_1^{-1}(kt+d))</math>;		* query time: <math>O(n^{\rho}P_1^{-1}(kt+d))</math>;

			===Finding nearest neighbor without fixed dimensionality===

			To generalize the above algorithm without radius {{mvar\|R}} being fixed, we can take the algorithm and do a sort of binary search over {{mvar\|R}}. It has been shown<ref>{{cite journal \|last1=Har-Peled \|first1=Sariel \|last2=Indyk \|first2=Piotr \|last3=Motwani \|first3=Rajeev \|title=Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality \|journal=Theory of Computing \|date=2012 \|volume=8 \|issue=Special Issue in Honor of Rajeev Motwani \|pages=321-350 \|doi=10.4086/toc.2012.v008a014 \|url=https://theoryofcomputing.org/articles/v008a014/v008a014.pdf \|access-date=23 May 2025}}</ref> that there is a data structure for the approximate nearest neighbor with the following performance guarantees:
			* space: <math>O(n^{1+\rho}P_1^{-1}d\log^2 n)</math>;
			* query time: <math>O(n^{\rho}P_1^{-1}(kt+d)\log n)</math>;
			* the algorithm succeeds in finding the nearest neighbor with probability at least <math>1 - (( 1 - P_1^k ) ^ L\log n)</math>;

	===Improvements===		===Improvements===

Krauss: /* See also */ add

2025-05-19T22:05:36Z

2A02:8070:A186:1880:3593:190:91D5:39FB at 17:28, 16 April 2025

2025-04-16T17:28:55Z

← Previous revision		Revision as of 17:28, 16 April 2025
Line 215:		Line 215:
	===Random projection===		===Random projection===
	{{main\|Random projection}}		{{main\|Random projection}}
	[[File:Cosine-distance.png\| thumb \| <math>\frac{\theta(u,v)}{\pi}</math> is proportional to <math>1-\cos(\theta(u,v))</math> on the interval [0, <math>\pi</math>]]		[[File:Cosine-distance.png\| thumb \| <math>\frac{\theta(u,v)}{\pi}</math> is approximately proportional to <math>1-\cos(\theta(u,v))</math> on the interval [0, <math>\pi</math>]]

	The random projection method of LSH due to [[Moses Charikar]]<ref name=Charikar2002 /> called [[SimHash]] (also sometimes called arccos<ref name=Andoni2008>{{cite journal		The random projection method of LSH due to [[Moses Charikar]]<ref name=Charikar2002 /> called [[SimHash]] (also sometimes called arccos<ref name=Andoni2008>{{cite journal

Astrid224442: added a reference for applications

2025-03-27T15:26:48Z

added a reference for applications

← Previous revision		Revision as of 15:26, 27 March 2025
Line 98:		Line 98:
	\| url = https://github.com/worldveil/dejavu\| date = 2018-12-19}}		\| url = https://github.com/worldveil/dejavu\| date = 2018-12-19}}
	</ref>		</ref>
	*[[Digital video fingerprinting]]		*[[Digital video fingerprinting]]<ref>
			{{citation
			\| title = A Simple Introduction to Locality Sensitive Hashing (LSH)
			\| url =https://www.iunera.com/kraken/fabric/locality-sensitive-hashing-lsh/#7-applications-of-lsh\| date = 2025-03-27}}
			</ref>
	*[[Shared memory]] organization in [[parallel computing]]<ref name=Chin1991 /><ref name=Chin1994 />		*[[Shared memory]] organization in [[parallel computing]]<ref name=Chin1991 /><ref name=Chin1994 />
	*Physical data organization in database management systems<ref>		*Physical data organization in database management systems<ref>

Headbomb: Add: chapter, title. | Use this tool. Report bugs. | #UCB_Gadget

2024-12-29T17:08:31Z

Add: chapter, title. | Use this tool. Report bugs. | #UCB_Gadget

← Previous revision		Revision as of 17:08, 29 December 2024
Line 112:		Line 112:
	{{cite conference		{{cite conference
	\| author1 = Oliver, Jonathan\| author2 = Cheng, Chun \| author3 = Chen, Yanggui		\| author1 = Oliver, Jonathan\| author2 = Cheng, Chun \| author3 = Chen, Yanggui

	\| title = TLSH - a locality sensitive hash
	\| ~~journal~~ = ~~4th~~ Cybercrime and Trustworthy Computing Workshop		\| title = 2013 Fourth Cybercrime and Trustworthy Computing Workshop \| chapter = TLSH -- A Locality Sensitive Hash \| year = 2013
	\| year = 2013
	\| pages = 7–13 \| url = https://www.academia.edu/7833902		\| pages = 7–13 \| url = https://www.academia.edu/7833902
	\| doi = 10.1109/CTC.2013.9		\| doi = 10.1109/CTC.2013.9

2003:C9:7F0F:AB00:CED5:FF84:9AC4:5441: Fix typo (one "]" too many)

2024-12-13T17:33:29Z

Fix typo (one "]" too many)

← Previous revision		Revision as of 17:33, 13 December 2024
Line 212:		Line 212:
	===Random projection===		===Random projection===
	{{main\|Random projection}}		{{main\|Random projection}}
	[[File:Cosine-distance.png\| thumb \| <math>\frac{\theta(u,v)}{\pi}</math> is proportional to <math>1-\cos(\theta(u,v))</math> on the interval [0, <math>\pi</math>]]]		[[File:Cosine-distance.png\| thumb \| <math>\frac{\theta(u,v)}{\pi}</math> is proportional to <math>1-\cos(\theta(u,v))</math> on the interval [0, <math>\pi</math>]]

	The random projection method of LSH due to [[Moses Charikar]]<ref name=Charikar2002 /> called [[SimHash]] (also sometimes called arccos<ref name=Andoni2008>{{cite journal		The random projection method of LSH due to [[Moses Charikar]]<ref name=Charikar2002 /> called [[SimHash]] (also sometimes called arccos<ref name=Andoni2008>{{cite journal

Hou8547: /* Random projection / Correct some typos: (1) the constant is off by a factor of 2; (2) probability of being on different* sides.

2024-12-12T00:26:22Z

Random projection: Correct some typos: (1) the constant is off by a factor of 2; (2) probability of being on *different* sides.

← Previous revision		Revision as of 00:26, 12 December 2024
Line 237:		Line 237:
	:<math>Pr[h(u) = h(v)] = 1 - \frac{\theta(u,v)}{\pi}.</math>		:<math>Pr[h(u) = h(v)] = 1 - \frac{\theta(u,v)}{\pi}.</math>

	Since the ratio between <math>\frac{\theta(u,v)}{\pi}</math> and <math>1-\cos(\theta(u,v))</math> is at least 0.~~87856~~ when <math>\theta(u, v) \in [0, \pi]</math>,<ref name=Charikar2002 /><ref name="Goemans Williamson 1995 pp. 1115–1145">{{cite journal \| last1=Goemans \| first1=Michel X. \| last2=Williamson \| first2=David P. \| title=Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming \| journal=Journal of the ACM \| publisher=Association for Computing Machinery (ACM) \| volume=42 \| issue=6 \| year=1995 \| issn=0004-5411 \| doi=10.1145/227683.227684 \| pages=1115–1145\| s2cid=15794408 \| doi-access=free }}</ref> the probability of two vectors being on ~~the same~~ ~~side~~ of the random hyperplane is approximately proportional to the [[Cosine similarity#Cosine Distance\|cosine distance]] between them.		Since the ratio between <math>\frac{\theta(u,v)}{\pi}</math> and <math>1-\cos(\theta(u,v))</math> is at least 0.439 when <math>\theta(u, v) \in [0, \pi]</math>,<ref name=Charikar2002 /><ref name="Goemans Williamson 1995 pp. 1115–1145">{{cite journal \| last1=Goemans \| first1=Michel X. \| last2=Williamson \| first2=David P. \| title=Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming \| journal=Journal of the ACM \| publisher=Association for Computing Machinery (ACM) \| volume=42 \| issue=6 \| year=1995 \| issn=0004-5411 \| doi=10.1145/227683.227684 \| pages=1115–1145\| s2cid=15794408 \| doi-access=free }}</ref> the probability of two vectors being on different sides of the random hyperplane is approximately proportional to the [[Cosine similarity#Cosine Distance\|cosine distance]] between them.

	===Stable distributions===		===Stable distributions===

190.253.241.1: /* Definitions */

2024-06-25T13:50:28Z

Definitions

← Previous revision		Revision as of 13:50, 25 June 2024
Line 7:		Line 7:

	==Definitions==		==Definitions==
	A 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		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.		\| author1 = Gionis, A.
	\| author2-link = Piotr Indyk \| author2 = Indyk, P. \| author3-link = Rajeev Motwani \| author3 = Motwani, R.		\| author2-link = Piotr Indyk \| author2 = Indyk, P. \| author3-link = Rajeev Motwani \| author3 = Motwani, R.
Line 30:		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 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\|p}} and {{mvar\|q}} collide) with probability at least <math>p_1</math>,		* If <math>d(a,b) \le r</math>, then <math>h(a)=h(b)</math> (i.e., {{mvar\|a}} and {{mvar\|b}} 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>.		* If <math>d(a,b) \ge cr</math>, then <math>h(a)=h(b)</math> with probability at most <math>p_2</math>.

Frietjes: update template syntax

2024-05-23T15:16:30Z

update template syntax

← Previous revision		Revision as of 15:16, 23 May 2024
Line 113:		Line 113:
	\| author1 = Oliver, Jonathan\| author2 = Cheng, Chun \| author3 = Chen, Yanggui		\| author1 = Oliver, Jonathan\| author2 = Cheng, Chun \| author3 = Chen, Yanggui
	\| title = TLSH - a locality sensitive hash		\| title = TLSH - a locality sensitive hash
	\| journal = 4th Cybercrime and Trustworthy Computing Workshop		\| journal = 4th Cybercrime and Trustworthy Computing Workshop
	\| year = 2013		\| year = 2013
	\| pages = 7–13 \| url = https://www.academia.edu/7833902		\| pages = 7–13 \| url = https://www.academia.edu/7833902
	\| doi = 10.1109/CTC.2013.9		\| doi = 10.1109/CTC.2013.9
	\| isbn = 978-1-4799-3076-0		\| isbn = 978-1-4799-3076-0
	}}		}}
	</ref>		</ref>
	*[[Machine Learning]]<ref name="NL">		*[[Machine Learning]]<ref name="NL">
			{{citation
	{{cite 1204.2071
	\| author1 = Fanaee-T, Hadi		\| author1 = Fanaee-T, Hadi
	\| title = Natural Learning		\| title = Natural Learning
	\| year = 2024		\| year = 2024
	\| arxiv = 2404.05903		\| arxiv = 2404.05903
	}}		}}
	</ref>		</ref>

Headbomb: ce

2024-05-22T09:25:05Z

← Previous revision		Revision as of 09:25, 22 May 2024
Line 121:		Line 121:
	</ref>		</ref>
	*[[Machine Learning]]<ref name="NL">		*[[Machine Learning]]<ref name="NL">
	{{cite ~~conference~~		{{cite 1204.2071
	\| author1 = Fanaee-T, Hadi		\| author1 = Fanaee-T, Hadi
	\| title = Natural Learning		\| title = Natural Learning
	\| journal = arXiv
	\| year = 2024		\| year = 2024
	~~\| pages = 1–10~~ \| arxiv = 2404.05903		\| arxiv = 2404.05903
	}}		}}
	</ref>		</ref>

← Previous revision		Revision as of 22:05, 19 May 2025
Line 325:		Line 325:
	* {{Annotated link \|Sparse distributed memory}}		* {{Annotated link \|Sparse distributed memory}}
	* {{Annotated link \|Wavelet compression}}		* {{Annotated link \|Wavelet compression}}
			* {{Annotated link \|Locality of reference}}

	==References==		==References==