Mostrar código-fonte de Hashing sensível à localidade

Na [[ciência da computação]], o '''hashing sensível à localidade''' ('''LSH''', na sigla em inglês) é uma técnica algorítmica que agrupa itens de entrada semelhantes associando-os a um mesmo ''hash'' com alta probabilidade.<ref name="MOMD">{{Citar web|ultimo=Rajaraman|primeiro=A.|ultimo2=Ullman|primeiro2=J.|url=http://infolab.stanford.edu/~ullman/mmds.html|titulo=Mining of Massive Datasets, Ch. 3.|ano=2010}}</ref> (O número de grupos é muito menor que o universo de itens de entrada possíveis.)<ref name="MOMD" /> Como itens semelhantes acabam nos mesmos grupos, essa técnica pode ser usada para [[Clustering|agrupamento de dados]] e busca do vizinho mais próximo. Ela difere das [[Função hash|técnicas de ''hash'' convencionais]] por maximizar, em vez de minimizar, as colisões de ''hash''. Alternativamente, a técnica pode ser vista como uma forma de reduzir a dimensionalidade de dados de alta dimensão; itens de entrada de alta dimensão podem ser reduzidos a versões de baixa dimensão, preservando as distâncias relativas entre os itens.

Os algoritmos de busca do vizinho mais próximo baseados em hash geralmente usam uma das duas categorias principais de métodos de hash: métodos independentes de dados, como hashing sensível à localidade (LSH); ou métodos dependentes de dados, como hashing de preservação de localidade (LPH).<ref>{{Citar conferência |ultimo=Zhao |primeiro=Kang |ultimo2=Lu |primeiro2=Hongtao |url=https://ojs.aaai.org/index.php/AAAI/article/view/9133/8992 |titulo=Locality Preserving Hashing |ano=2014 |paginas=2874–2880 |conferencia=AAAI Conference on Artificial Intelligence |ultimo3=Mei |primeiro3=Jincheng |volume=28}}</ref><ref>{{Citar livro|título=2014 IEEE International Conference on Image Processing (ICIP)|ultimo=Tsai|primeiro=Yi-Hsuan|ultimo2=Yang|primeiro2=Ming-Hsuan|data=outubro de 2014|páginas=2988–2992|capitulo=Locality preserving hashing|doi=10.1109/ICIP.2014.7025604|isbn=978-1-4799-5751-4|issn=1522-4880}}</ref>

== Definições ==
Uma ''família LSH''<ref name="MOMD">{{Citar web|ultimo=Rajaraman|primeiro=A.|ultimo2=Ullman|primeiro2=J.|url=http://infolab.stanford.edu/~ullman/mmds.html|titulo=Mining of Massive Datasets, Ch. 3.|ano=2010}}</ref><ref name="GIM1999">{{Citar periódico |url=http://people.csail.mit.edu/indyk/vldb99.ps |titulo=Similarity Search in High Dimensions via Hashing |periódico=Proceedings of the 25th Very Large Database (VLDB) Conference |ultimo=Gionis, A. |ultimo2=Indyk, P. |ano=1999 |ultimo3=Motwani, R.}}</ref><ref name="IndykMotwani98">{{Citar conferência |ultimo=[[Piotr Indyk|Indyk, Piotr]]. |ultimo2=[[Rajeev Motwani|Motwani, Rajeev]]. |titulo=Proceedings of 30th Symposium on Theory of Computing |ano=1998}}</ref> <math>\mathcal F</math> é definida para

* um [[espaço métrico]] <math>\mathcal M =(M, d)</math>,
* um limiar <math>R>0</math>,
* um fator de aproximação <math>c>1</math>,
* e probabilidades <math>P_1</math> e <math>P_2</math>.

Essa família <math>\mathcal F</math> é um conjunto de funções <math>h\colon M \to S</math> que levam elementos do espaço métrico em ''buckets'' <math>s \in S</math>. Uma família LSH deve satisfazer as seguintes condições para quaisquer dois pontos <math>p, q \in M</math> e qualquer função hash <math>h</math> escolhidos uniformemente ao acaso a partir de <math>\mathcal F</math>:

* Se <math>d(p,q) \le R</math>, então <math>h(p)=h(q)</math> (ou seja, {{Mvar|p}} e {{Mvar|q}} colidem) com probabilidade de pelo menos <math>P_1</math>,
* Se <math>d(p,q) \ge cR</math>, então <math>h(p)=h(q)</math> com probabilidade no máximo <math>P_2</math>.

Uma família é interessante quando <math>P_1>P_2</math>. Uma tal família <math>\mathcal F</math> é chamada ''<math>(R,cR,P_1,P_2)</math>-sensível''.

Alternativamente,<ref name="Charikar2002">{{Citar conferência |ultimo=Charikar |primeiro=Moses S. |autorlink=Moses Charikar |titulo=Proceedings of the 34th Annual ACM Symposium on Theory of Computing |ano=2002 |paginas=380–388 |citeseerx=10.1.1.147.4064 |doi=10.1145/509907.509965}}</ref> a definição pode ser data em relação a um universo de itens {{Mvar|U}} que possuem uma função de similaridade <math>\phi\colon U \times U \to [0,1]</math>. Um esquema LSH é uma família de [[Função hash|funções hash]] {{Mvar|H}}, juntamente com uma [[distribuição de probabilidade]] {{Mvar|D}} sobre as funções, tal que uma função <math>h \in H</math> escolhido de acordo com {{Mvar|D}} satisfaz a propriedade que <math>Pr_{h \in H} [h(a) = h(b)] = \phi(a,b)</math> para qualquer <math>a,b \in U</math>.

=== Hash de preservação de localidade ===
Um '''hash que preserva a localidade''' é uma [[função hash]] {{Mvar|f}} que leva pontos de um [[espaço métrico]] <math>\mathcal M =(M, d)</math> para um valor escalar tal que

: <math>d(p,q) < d(q,r) \Rightarrow |f(p) - f(q)| < |f(q) - f(r)|</math>

para quaisquer três pontos <math>p,q,r \in M</math>.

Em outras palavras, estas são funções de hash onde a distância relativa entre os valores de entrada é preservada na distância relativa entre os valores de hash de saída; valores de entrada mais próximos uns dos outros produzirão valores de hash de saída mais próximos uns dos outros.

Isso contrasta com as funções de hash [[Criptografia|criptográficas]] e as [[Soma de verificação|somas de verificação]], que são projetadas para ter uma [[Efeito avalanche (criptografia)|diferença de saída aleatória entre entradas adjacentes]] .

A primeira família de funções de hash que preservam a localidade foi concebida como uma forma de facilitar o [[Segmentação (informática)|''pipelining'' de dados]] em implementações de algoritmos de [[Máquina de acesso randômico paralelo|máquina paralela de acesso aleatório (PRAM)]] que usam hashing universal para reduzir a contenção de memória e o congestionamento da rede.<ref name="Chin1991">{{Citar tese|sobrenome=Chin|nome=Andrew|titulo=Complexity Issues in General Purpose Parallel Computing|tipo=DPhil|url=https://perma.cc/E47H-WCVP}}</ref><ref name="Chin1994">{{Citar periódico |url=http://unclaw.com/chin/scholarship/hashfunctions.pdf |título=Locality-Preserving Hash Functions for General Purpose Parallel Computation |data=1994 |periódico=Algorithmica |número=2-3 |ultimo=Chin |primeiro=Andrew |paginas=170-181 |doi=10.1007/BF01185209 |volume=12}}</ref>

Os hashes que preservam a localidade estão relacionados a curvas de preenchimento de espaço.

=== Amplificação ===
Dada uma família <math>(d_1, d_2, p_1, p_2)</math>-sensível <math>\mathcal F</math>, podemos construir novas famílias <math>\mathcal G</math> pela construção AND ou construção OR de <math>\mathcal F</math>.<ref name="MOMD">{{Citar web|ultimo=Rajaraman|primeiro=A.|ultimo2=Ullman|primeiro2=J.|url=http://infolab.stanford.edu/~ullman/mmds.html|titulo=Mining of Massive Datasets, Ch. 3.|ano=2010}}</ref>

Para criar uma construção AND, definimos uma nova família <math>\mathcal G</math> de funções hash {{Mvar|g}}, em que cada função {{Mvar|g}} é construída a partir de {{Mvar|k}} funções aleatórias <math>h_1, \ldots, h_k</math> de <math>\mathcal F</math>. Então dizemos que para uma função hash <math>g \in \mathcal G</math>, <math>g(x) = g(y)</math> se, e somente se, <math>h_i(x) = h_i(y)</math> para cada <math>i = 1, 2, \ldots, k</math> . Já que os membros de <math>\mathcal F</math> são escolhidos independentemente para qualquer <math>g \in \mathcal G</math>, <math>\mathcal G</math> é uma família <math>(d_1, d_2, p_{1}^k, p_{2}^k)</math>-sensível.

Para criar uma construção OR, definimos uma nova família <math>\mathcal G</math> de funções hash {{Mvar|g}}, em que cada função {{Mvar|g}} é construída a partir de {{Mvar|k}} funções aleatórias <math>h_1, \ldots, h_k</math> de <math>\mathcal F</math>. Então dizemos que para uma função hash <math>g \in \mathcal G</math>, <math>g(x) = g(y)</math> se, e somente se, <math>h_i(x) = h_i(y)</math> para um ou mais valores de {{Mvar|i}}. Já que os membros da <math>\mathcal F</math> são escolhidos independentemente para qualquer <math>g \in \mathcal G</math>, <math>\mathcal G</math> é uma família <math>(d_1, d_2, 1- (1 - p_1)^k, 1 - (1 - p_2)^k)</math>-sensível.

== Aplicações ==
O LSH foi aplicado a vários domínios de problemas, incluindo:

* Detecção de quase duplicatas<ref>
{{Citation|último=Das, Abhinandan S.|título=Google news personalization: scalable online collaborative filtering|periódico=Proceedings of the 16th International Conference on World Wide Web|páginas=271|ano=2007|doi=10.1145/1242572.1242610|display-authors=etal|isbn=9781595936547}}.</ref>
* Agrupamento hierárquico<ref>
{{Citation|último=Koga, Hisashi|último2=Tetsuo Ishibashi|último3=Toshinori Watanabe|título=Fast agglomerative hierarchical clustering algorithm using Locality-Sensitive Hashing|periódico=Knowledge and Information Systems|volume=12|número=1|páginas=25–53|ano=2007|doi=10.1007/s10115-006-0027-5}}.</ref><ref>
{{Citation|último=Cochez, Michael|último2=Mou, Hao|título=Twister Tries: Approximate Hierarchical Agglomerative Clustering for Average Distance in Linear Time|periódico=Proceeding SIGMOD '15 Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data|páginas=505–517|ano=2015|doi=10.1145/2723372.2751521|isbn=9781450327589|url=https://jyx.jyu.fi/bitstream/123456789/46537/1/cochezmousigmod15finalcameraready.pdf}}.</ref>
* [[Estudo de associação do genoma completo|Estudo de associação em todo o genoma]]<ref>
{{Citation|último=Brinza, Dumitru|título=RAPID detection of gene–gene interactions in genome-wide association studies|periódico=Bioinformatics|volume=26|número=22|ano=2010|páginas=2856–2862|doi=10.1093/bioinformatics/btq529|pmid=20871107|display-authors=etal|pmc=3493125}}
</ref>
* Identificação de semelhança de imagem
** [[VisualRank]]
* Identificação de similaridade de [[Expressão génica|expressão gênica]] {{carece de fontes|data=outubro de 2013}}
* Identificação de similaridade de áudio
* Pesquisa de vizinho mais próximo
* Impressão digital de áudio<ref>
{{Citation|título=dejavu - Audio fingerprinting and recognition in Python|url=https://github.com/worldveil/dejavu|data=2018-12-19}}
</ref>
* Impressão digital de vídeo
* Organização de dados físicos em sistemas de gerenciamento de banco de dados<ref>
{{Citation|último=Aluç, Güneş|último2=Özsu, M. Tamer|último3=Daudjee, Khuzaima|título=Building self-clustering RDF databases using Tunable-LSH|periódico=The VLDB Journal|ano=2018|volume=28|número=2|páginas=173–195|doi=10.1007/s00778-018-0530-9}}
</ref>
* Treinamento de redes neurais totalmente conectadas<ref>{{Citar arXiv|arxiv=1903.03129|classe=cs.DC|nome=Beidi|sobrenome=Chen|nome2=Tharun|sobrenome2=Medini|titulo=SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems|data=2020-02-29}}</ref><ref>{{Citation|último=Chen|primeiro1=Beidi|último2=Liu|primeiro2=Zichang|último3=Peng|primeiro3=Binghui|último4=Xu|primeiro4=Zhaozhuo|último5=Li|primeiro5=Jonathan Lingjie|último6=Dao|primeiro6=Tri|último7=Song|primeiro7=Zhao|último8=Shrivastava|primeiro8=Anshumali|último9=Re|primeiro9=Christopher|título=MONGOOSE: A Learnable LSH Framework for Efficient Neural Network Training|periódico=International Conference on Learning Representation|ano=2021|url=https://openreview.net/forum?id=wWK7yXkULyh}}
</ref>

* Segurança de computadores<ref name="TLSH">
{{Citar conferência |ultimo=Oliver, Jonathan |ultimo2=Cheng, Chun |url=https://www.academia.edu/7833902 |titulo=TLSH - a locality sensitive hash |ano=2013 |doi=10.1109/CTC.2013.9 |isbn=978-1-4799-3076-0 |ultimo3=Chen, Yanggui}}
</ref>

== Métodos ==

=== Amostragem de bits para a distância de Hamming ===
Uma das maneiras mais fáceis de construir uma família LSH é por amostragem de bits.<ref name="IndykMotwani98">{{Citar conferência |ultimo=[[Piotr Indyk|Indyk, Piotr]]. |ultimo2=[[Rajeev Motwani|Motwani, Rajeev]]. |titulo=Proceedings of 30th Symposium on Theory of Computing |ano=1998}}</ref> Essa abordagem funciona para a [[distância de Hamming]] sobre vetores {{Mvar|d}} -dimensionais <math>\{0,1\}^d</math>. Aqui, a família <math>\mathcal F</math> de funções hash é simplesmente a família de todas as projeções de pontos em uma das <math>d</math> coordenadas, ou seja, <math>{\mathcal F}=\{h\colon \{0,1\}^d\to \{0,1\}\mid h(x)=x_i \text{ for some } i\in \{1, \ldots, d\}\}</math>, em que <math>x_i</math> é a <math>i</math>-ésima coordenada de <math>x</math>. Uma função aleatória <math>h</math> de <math>{\mathcal F}</math> simplesmente seleciona um bit aleatório do ponto de entrada. Esta família tem os seguintes parâmetros: <math>P_1=1-R/d</math>, <math>P_2=1-cR/d</math>.

=== Permutações independentes ''min-wise'' ===
{{Artigo principal|Nilsimsa Hash}}
Suponha que {{Mvar|U}} seja composto de subconjuntos de algum conjunto básico de itens enumeráveis {{Mvar|S}} e que a função de similaridade de interesse seja o índice de Jaccard {{Mvar|J}}. Se {{Mvar|&pi;}} é uma permutação nos índices de {{Mvar|S}}, para <math>A \subseteq S</math> seja <math>h(A) = \min_{a \in A} \{ \pi(a) \}</math>. Cada escolha possível de {{Mvar|&pi;}} define uma única função hash {{Mvar|h}} mapeando conjuntos de entrada em elementos de {{Mvar|S}} .

Defina a família de funções {{Mvar|H}} como o conjunto de todas essas funções e seja {{Mvar|D}} a distribuição uniforme. Dados dois conjuntos <math>A,B \subseteq S</math>, o evento que <math>h(A) = h(B)</math> corresponde exatamente ao evento em que o minimizador de {{Mvar|&pi;}} sobre <math>A \cup B</math> encontra-se dentro de <math>A \cap B</math>. Como {{Mvar|h}} foi escolhida uniformemente ao acaso, <math>Pr[h(A) = h(B)] = J(A,B)\,</math> e <math>(H,D)\,</math> define um esquema LSH para o índice Jaccard.

Como o grupo simétrico em {{Mvar|n}} elementos tem tamanho {{Mvar|n}}!, escolher uma [[Permutação aleatória|permutação verdadeiramente aleatória]] do grupo simétrico completo é inviável, mesmo para {{Mvar|n}} de tamanho moderado. Devido a esse fato, tem havido um trabalho significativo para encontrar uma família de permutações que seja "min-wise independente" - uma família de permutações para a qual cada elemento do domínio tem a mesma probabilidade de ser o mínimo sob uma {{Mvar|&pi;}} escolhida aleatoriamente. Foi estabelecido que uma família min-wise independente de permutações é pelo menos de tamanho <math>\operatorname{lcm}\{\,1, 2, \ldots, n\,\} \ge e^{n-o(n)}</math>,<ref name="Broder1998">{{Citar conferência |ultimo=Broder |primeiro=A.Z. |ultimo2=Charikar |primeiro2=M. |titulo=Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing |acessodata=2007-11-14 |ano=1998 |paginas=327–336 |citeseerx=10.1.1.409.9220 |doi=10.1145/276698.276781 |ultimo3=Frieze |primeiro3=A.M. |ultimo4=Mitzenmacher |primeiro4=M. |autorlink4=Michael Mitzenmacher}}</ref> e que esse limite é ótimo.<ref>
{{Citar periódico |título=An optimal construction of exactly min-wise independent permutations |periódico=Technical Report COMP98-62, IEICE, 1998 |ultimo=Takei, Y. |ultimo2=Itoh, T. |ultimo3=Shinozaki, T.}}
</ref>

Como famílias ''min-wise'' independentes são muito grandes para aplicações práticas, duas variantes da noção de independência ''min-wise'' são introduzidas: famílias de permutações ''min-wise'' independentes restritas e famílias ''min-wise'' independentes aproximadas. A independência min-wise restrita é a propriedade de independência min-wise restrita a certos conjuntos de cardinalidade no máximo {{Mvar|k}}.<ref name="Matousek2002">{{Citar periódico |url=http://citeseer.ist.psu.edu/689217.html |título=On Restricted Min-Wise Independence of Permutations |acessodata=2007-11-14 |periódico=Preprint |ultimo=[[Jiří Matoušek (mathematician)|Matoušek]], J. |ultimo2=Stojakovic, M. |ano=2002}}</ref> A independência min-wise aproximada difere da propriedade em no máximo um {{Mvar|&epsilon;}} fixo.<ref name="Saks2000">{{Citar periódico |url=http://citeseer.ist.psu.edu/saks99low.html |título=Low discrepancy sets yield approximate min-wise independent permutation families |acessodata=2007-11-14 |periódico=Information Processing Letters |número=1–2 |ultimo=Saks |primeiro=M. |ultimo2=Srinivasan |primeiro2=A. |ano=2000 |paginas=29–32 |citeseerx=10.1.1.20.8264 |doi=10.1016/S0020-0190(99)00163-5 |ultimo3=Zhou |primeiro3=S. |ultimo4=Zuckerman |primeiro4=D. |volume=73}}</ref>

=== Métodos de código aberto ===

==== Hash de Nilsimsa ====
{{Artigo principal|Nilsimsa Hash}}
O '''Nilsimsa''' é um [[algoritmo]] de hash sensível à localidade usado em esforços anti-spam.<ref>{{Citar web|ultimo=Damiani|url=http://spdp.di.unimi.it/papers/pdcs04.pdf|titulo=An Open Digest-based Technique for Spam Detection|acessodata=2013-09-01|ano=2004|numero-autores=et al}}</ref> O objetivo do Nilsimsa é gerar um resumo de uma mensagem de e-mail por um hash de modo que os resumos de duas mensagens semelhantes sejam semelhantes entre si. O artigo sugere que o Nilsimsa satisfaz três requisitos:

# O resumo que identifica cada mensagem não deve variar significativamente para alterações que podem ser produzidas automaticamente.
# A codificação deve ser robusta contra ataques intencionais.
# A codificação deve suportar um risco extremamente baixo de falsos positivos.

==== TLSH ====
O '''TLSH''' é um algoritmo de hash sensível à localidade projetado para uma variedade de aplicações forenses de segurança e digitais.<ref name="TLSH">
{{Citar conferência |ultimo=Oliver, Jonathan |ultimo2=Cheng, Chun |url=https://www.academia.edu/7833902 |titulo=TLSH - a locality sensitive hash |ano=2013 |doi=10.1109/CTC.2013.9 |isbn=978-1-4799-3076-0 |ultimo3=Chen, Yanggui}}
</ref> O objetivo do TLSH é gerar resumos de hash para mensagens de modo que baixas distâncias entre os resumos indiquem que as mensagens correspondentes provavelmente serão semelhantes.

Os testes realizados no artigo em uma variedade de tipos de arquivo identificaram que o hash Nilsimsa tem uma taxa de falsos positivos significativamente maior quando comparado a outros esquemas de resumo de similaridade, como o TLSH, o Ssdeep e o Sdhash.

Uma implementação do TLSH está disponível como [[software de código aberto]].<ref>{{Citar web|url=https://github.com/trendmicro/tlsh|titulo=TLSH|acessodata=2014-04-10}}</ref>

=== Projeção aleatória ===
[[Imagem:One_minus_theta_over_pi_vs_cos_of_theta.gif|alt=Sketch of 1-theta vs. cos(theta)|miniaturadaimagem| Para ângulos pequenos (não muito próximos do ortogonal), <math>1 - \frac{\theta}{\pi}</math> é uma boa aproximação para <math>\cos(\theta)</math>]]
O método de projeção aleatória de LSH devido a Moses Charikar<ref name="Charikar2002">{{Citar conferência |ultimo=Charikar |primeiro=Moses S. |autorlink=Moses Charikar |titulo=Proceedings of the 34th Annual ACM Symposium on Theory of Computing |ano=2002 |paginas=380–388 |citeseerx=10.1.1.147.4064 |doi=10.1145/509907.509965}}</ref> chamado SimHash (também chamado às vezes de arccos<ref name="Andoni2008">{{Citar periódico |título=Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions |periódico=Communications of the ACM |número=1 |ultimo=Alexandr Andoni |ultimo2=Indyk, P. |ano=2008 |paginas=117–122 |citeseerx=10.1.1.226.6905 |doi=10.1145/1327452.1327494 |volume=51}}</ref>) é projetado para aproximar a [[similaridade por cosseno]] entre os vetores. A ideia básica dessa técnica é escolher um [[hiperplano]] aleatório (definido por um vetor unitário normal {{Mvar|r}} ) no início e usar o hiperplano para fazer o hash dos vetores de entrada.

Dado um vetor de entrada {{Mvar|v}} e um hiperplano definido por {{Mvar|r}}, define-se <math>h(v) = sgn(v \cdot r)</math> . Isto é, <math>h(v) = \pm 1</math> dependendo de qual lado do hiperplano {{Mvar|v}} está.

Cada escolha possível de {{Mvar|r}} define uma única função. Seja {{Mvar|H}} o conjunto de todas essas funções e seja {{Mvar|D}}, novamente, a distribuição uniforme. Não é difícil provar que, para dois vetores <math>u,v</math>, <math>Pr[h(u) = h(v)] = 1 - \frac{\theta(u,v)}{\pi}</math>, em que <math>\theta(u,v)</math> é o ângulo entre {{Mvar|u}} e {{Mvar|v}} . O valor <math>1 - \frac{\theta(u,v)}{\pi}</math> está intimamente relacionado com <math>\cos(\theta(u,v))</math>.

Neste caso, o hashing produz apenas um único bit. Os bits de dois vetores combinam com probabilidade proporcional ao cosseno do ângulo entre eles.

=== Distribuições estáveis ===
A função hash<ref name="DIIM04">{{Citar periódico |url=http://theory.csail.mit.edu/~mirrokni/pstable.ps |título=Locality-Sensitive Hashing Scheme Based on p-Stable Distributions |periódico=Proceedings of the Symposium on Computational Geometry |ultimo=Datar, M. |ultimo2=Immorlica, N. |ano=2004 |ultimo3=Indyk, P. |ultimo4=Mirrokni, V.S.}}</ref> <math>h_{\mathbf{a},b} (\boldsymbol{\upsilon}) :
\mathcal{R}^d
\to \mathcal{N} </math> mapeia um vetor {{Mvar|d}}-dimensional <math>\boldsymbol{\upsilon}</math> no conjunto dos inteiros. Cada função hash na família é indexada por uma escolha aleatória de <math>\mathbf{a}</math> e <math>b</math>, em que <math>\mathbf{a}</math> é um vetor de dimensão {{Mvar|d}} com entradas escolhidas independentemente a partir de uma distribuição estável e <math>b</math> é um [[número real]] escolhido uniformemente no intervalo [0,r]. Para <math>\mathbf{a},b</math> fixados, a função hash <math>h_{\mathbf{a},b}</math> é dada por <math>h_{\mathbf{a},b} (\boldsymbol{\upsilon}) = \left \lfloor
\frac{\mathbf{a}\cdot \boldsymbol{\upsilon}+b}{r} \right \rfloor </math>.

Outros métodos de construção para funções de hash foram propostos um melhor ajuste dos dados.<ref name="PJA10">{{Citar periódico |url=http://hal.inria.fr/inria-00567191/en/ |título=Locality sensitive hashing: A comparison of hash function types and querying mechanisms |periódico=Pattern Recognition Letters |número=11 |ultimo=Pauleve, L. |ultimo2=Jegou, H. |ano=2010 |paginas=1348–1358 |doi=10.1016/j.patrec.2010.04.004 |ultimo3=Amsaleg, L. |volume=31}}</ref> Em particular, funções hash ''k-means'' são melhores na prática do que funções hash baseadas em projeção, mas sem qualquer garantia teórica.

=== Hashing semântico ===
O hashing semântico é uma técnica que tenta mapear itens de entrada em endereços de forma que as entradas mais próximas tenham maior similaridade [[semântica]].<ref>{{Citar periódico |url=https://linkinghub.elsevier.com/retrieve/pii/S0888613X08001813 |título=Semantic hashing |data=2008 |periódico=International Journal of Approximate Reasoning |número=7 |ultimo=Salakhutdinov |primeiro=Ruslan |ultimo2=Hinton |primeiro2=Geoffrey |paginas=969–978 |lingua=en |doi=10.1016/j.ijar.2008.11.006 |volume=50 |doi-access=free}}</ref> Os ''hashcodes'' são encontrados através do treinamento de uma [[rede neural artificial]] ou [[Modelos probabilísticos gráficos|modelo gráfico]].

== Algoritmo LSH para a busca do vizinho mais próximo ==
Uma das principais aplicações do LSH é fornecer um método para algoritmos de busca do vizinho mais próximo aproximados eficientes. Considere uma família LSH <math>\mathcal F</math>. O algoritmo tem dois parâmetros principais: o parâmetro de largura {{Mvar|k}} e o número de tabelas hash {{Mvar|L}}.

Na primeira etapa, definimos uma nova família <math>\mathcal G</math> de funções hash {{Mvar|g}}, em que cada função {{Mvar|g}} é obtida pela concatenação de {{Mvar|k}} funções <math>h_1, \ldots, h_k</math> de <math>\mathcal F</math>, ou seja, <math>g(p) = [h_1(p), \ldots, h_k(p)]</math>. Em outras palavras, uma função hash aleatória {{Mvar|g}} é obtida concatenando {{Mvar|k}} funções hash de <math>\mathcal F</math> escolhidas aleatoriamente. O algoritmo então constrói {{Mvar|L}} tabelas hash, cada uma correspondendo a uma função hash diferente {{Mvar|g}} escolhida aleatoriamente.

Na etapa de pré-processamento, misturamos todos os {{Mvar|n}} pontos {{Mvar|d}}-dimensionais do conjunto de dados {{Mvar|S}} em cada uma das {{Mvar|L}} tabelas de hash. Dado que as tabelas de hash resultantes têm apenas {{Mvar|n}} entradas diferentes de zero, pode-se reduzir a quantidade de memória usada por cada tabela de hash para <math>O(n)</math> usando [[Função hash|funções de hash]] padrão.

Dado um ponto de consulta {{Mvar|q}}, o algoritmo itera sobre as {{Mvar|L}} funções hash {{Mvar|g}}. Para cada {{Mvar|g}} considerada, ele recupera os pontos de dados cujo hash está no mesmo ''bucket'' que {{Mvar|q}}. O processo é interrompido assim que é encontrado um ponto dentro da distância <math>cR</math> de {{Mvar|q}}.

Dados os parâmetros {{Mvar|k}} e {{Mvar|L}}, o algoritmo tem as seguintes garantias de desempenho:

* tempo de pré-processamento: <math>O(nLkt)</math>, em que {{Mvar|t}} é o tempo para avaliar uma função <math>h \in \mathcal F</math> em um ponto de entrada {{Mvar|p}};
* espaço: <math>O(nL)</math>, além do espaço para armazenar os pontos de dados;
* tempo de consulta: <math>O(L(kt+dnP_2^k))</math>;
* o algoritmo consegue encontrar um ponto dentro da distância <math>cR</math> de {{Mvar|q}} (se existe um ponto dentro da distância {{Mvar|R}}) com probabilidade de pelo menos <math>1 - ( 1 - P_1^k ) ^ L</math>;

Para uma razão de aproximação fixa <math>c=1+\epsilon</math> e probabilidades <math>P_1</math> e <math>P_2</math>, pode-se definir <math>k=\big\lceil{\tfrac{\log n}{\log 1/P_2}}\big\rceil</math> e <math>L = \lceil P_1^{-k}\rceil = O(n^{\rho}P_1^{-1})</math>, em que <math>\rho={\tfrac{\log P_1}{\log P_2}}</math> . Obtém-se então as seguintes garantias de desempenho:

* tempo de pré-processamento: <math>O(n^{1+\rho}P_1^{-1}kt)</math>;
* espaço: <math>O(n^{1+\rho}P_1^{-1})</math>, além do espaço para armazenar os pontos de dados;
* tempo de consulta: <math>O(n^{\rho}P_1^{-1}(kt+d))</math>;

=== Melhorias ===
Quando {{Mvar|t}} é grande, é possível tornar o tempo de hash menor inferior a <math>O(n^{\rho})</math>. Isso foi mostrado por<ref>Dahlgaard, Søren, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. [https://arxiv.org/pdf/1704.04370 "Fast similarity sketching."] 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017.</ref> e<ref>Christiani, Tobias. [https://arxiv.org/pdf/1708.07586 "Fast locality-sensitive hashing frameworks for approximate near neighbor search."] International Conference on Similarity Search and Applications. Springer, Cham, 2019.</ref> que deram

* tempo de consulta: <math>O(t\log^2(1/P_2)/P_1 + n^{\rho}(d + 1/P_1)</math>;
* espaço: <math>O(n^{1+\rho}/P_1 + \log^2(1/P_2)/P_1)</math>;

Às vezes também acontece de o fator <math>1/P_1</math> ser muito grande. Isso acontece, por exemplo, com dados de similaridade de Jaccard, em que mesmo o vizinho mais semelhante geralmente tem uma similaridade de Jaccard bastante baixa com a consulta. Em<ref>Ahle, Thomas Dybdahl. "On the Problem of $$ p_1^{-1} $$ in Locality-Sensitive Hashing." International Conference on Similarity Search and Applications. Springer, Cham, 2020.</ref> foi mostrado como reduzir o tempo de consulta para <math>O(n^\rho/P_1^{1-\rho})</math> (sem incluir os custos de hash) e, da mesma forma, o uso do espaço.

== Ver também ==

* [[Filtro Bloom]]
* [[Maldição da dimensionalidade]]
* [[Hash de características]]
* [[Lista de transformadas relacionadas à transformada de Fourier|Transformações relacionadas a Fourier]]
* [[Geohash]]
* [[Aprendizado de subespaço multilinear]]
* [[Análise de componentes principais]]
* [[Indexação aleatória]]<ref>Gorman, James, and James R. Curran. [https://aclanthology.org/P06-1046.pdf "Scaling distributional similarity to large corpora."] Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics. Association for Computational Linguistics, 2006.</ref>
* [[Hash deslizante]]
* [[Decomposição em valores singulares]]
* [[Memória distribuída esparsa]]
* [[Transformada wavelet|Compressão por wavelet]]

== Referências ==
<references responsive="1"></references>

== Leitura complementar ==

* Samet, H. (2006) ''Fundamentos de Estruturas de Dados Métricas e Multidimensionais'' . Morgan Kaufmann. ISBN 0-12-369446-9
* {{Citar conferência |ultimo=Indyk |primeiro=Piotr |ultimo2=Motwani |primeiro2=Rajeev |titulo=Locality-preserving hashing in multidimensional spaces |ano=1997 |paginas=618–625 |conferencia=[[Symposium on Theory of Computing|STOC '97]] |citeseerx=10.1.1.50.4927 |doi=10.1145/258533.258656 |isbn=978-0-89791-888-6 |ultimo3=Raghavan |primeiro3=Prabhakar |ultimo4=Vempala |primeiro4=Santosh |autorlink4=Santosh Vempala}}
* {{Citar periódico |url=http://www.unclaw.com/chin/scholarship/hashfunctions.pdf |título=Locality-preserving hash functions for general purpose parallel computation |periódico=[[Algorithmica]] |número=2–3 |ultimo=Chin |primeiro=Andrew |ano=1994 |paginas=170–181 |doi=10.1007/BF01185209 |volume=12}}

== Ligações externas ==

* [http://web.mit.edu/andoni/www/LSH/index.html Página inicial do LSH de Alex Andoni]
* [http://lshkit.sourceforge.net/ LSHKIT: uma biblioteca de hash sensível à localidade C++]
* [https://github.com/simonemainardi/LSHash Uma biblioteca Python Locality Sensitive Hashing que opcionalmente oferece suporte à persistência via redis]
* [https://web.archive.org/web/20101203074412/http://www.vision.caltech.edu/malaa/software/research/image-search/ Caltech Large Scale Image Search Toolbox] : uma caixa de ferramentas Matlab que implementa várias funções de hash LSH, além de Kd-Trees, Hierarchical K-Means e algoritmos de pesquisa de arquivo invertido.
* [https://github.com/salviati/slash Slash: Uma biblioteca C++ LSH, implementando Spherical LSH por Terasawa, K., Tanaka, Y]
* [https://github.com/RSIA-LIESMARS-WHU/LSHBOX LSHBOX: Uma caixa de ferramentas C++ de código aberto de hash sensível à localidade para recuperação de imagens em larga escala, também oferece suporte a Python e MATLAB.]
* [https://github.com/DBWangGroupUNSW/SRS SRS: Uma implementação em C++ de um algoritmo de processamento de consulta de vizinho mais próximo eficiente em memória e com eficiência de espaço baseado em projeção aleatória p-estável]
* [https://github.com/trendmicro/tlsh Código aberto TLSH no Github]
* [https://github.com/idealista/tlsh-js Porta JavaScript de TLSH (Trend Micro Locality Sensitive Hashing) agrupada como módulo node.js]
* [https://github.com/idealista/tlsh Porta Java de TLSH (Trend Micro Locality Sensitive Hashing) agrupada como pacote maven]

[[Categoria:Algoritmos de classificação]]
[[Categoria:Algoritmos de busca]]
[[Categoria:Redução de dimensionalidade]]
[[Categoria:Hashing]]