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. (O número de grupos é muito menor que o universo de itens de entrada possíveis.) Como itens semelhantes acabam nos mesmos grupos, essa técnica pode ser usada para agrupamento de dados e busca do vizinho mais próximo. Ela difere das 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).

Definições

Uma família LSH ${\mathcal {F}}$ é definida para

• um espaço métrico ${\mathcal {M}}=(M,d)$,
• um limiar $R>0$,
• um fator de aproximação $c>1$,
• e probabilidades $P_{1}$ e $P_{2}$.

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

• Se $d(p,q)\leq R$, então $h(p)=h(q)$ (ou seja, p e q colidem) com probabilidade de pelo menos $P_{1}$,
• Se $d(p,q)\geq cR$, então $h(p)=h(q)$ com probabilidade no máximo $P_{2}$.

Uma família é interessante quando $P_{1}>P_{2}$. Uma tal família ${\mathcal {F}}$ é chamada $(R,cR,P_{1},P_{2})$-sensível.

Alternativamente, a definição pode ser data em relação a um universo de itens U que possuem uma função de similaridade $\phi \colon U\times U\to [0,1]$. Um esquema LSH é uma família de funções hash H, juntamente com uma distribuição de probabilidade D sobre as funções, tal que uma função $h\in H$ escolhido de acordo com D satisfaz a propriedade que $Pr_{h\in H}[h(a)=h(b)]=\phi (a,b)$ para qualquer $a,b\in U$.

Hash de preservação de localidade

Um hash que preserva a localidade é uma função hash f que leva pontos de um espaço métrico ${\mathcal {M}}=(M,d)$ para um valor escalar tal que

$d(p,q)<d(q,r)\Rightarrow |f(p)-f(q)|<|f(q)-f(r)|$

para quaisquer três pontos $p,q,r\in M$.

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 criptográficas e as somas de verificação, que são projetadas para ter uma 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 pipelining de dados em implementações de algoritmos de 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.

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

Amplificação

Dada uma família $(d_{1},d_{2},p_{1},p_{2})$-sensível ${\mathcal {F}}$, podemos construir novas famílias ${\mathcal {G}}$ pela construção AND ou construção OR de ${\mathcal {F}}$.

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

Para criar uma construção OR, definimos uma nova família ${\mathcal {G}}$ de funções hash g, em que cada função g é construída a partir de k funções aleatórias $h_{1},\ldots ,h_{k}$ de ${\mathcal {F}}$. Então dizemos que para uma função hash $g\in {\mathcal {G}}$, $g(x)=g(y)$ se, e somente se, $h_{i}(x)=h_{i}(y)$ para um ou mais valores de i. Já que os membros da ${\mathcal {F}}$ são escolhidos independentemente para qualquer $g\in {\mathcal {G}}$, ${\mathcal {G}}$ é uma família $(d_{1},d_{2},1-(1-p_{1})^{k},1-(1-p_{2})^{k})$-sensível.

Aplicações

O LSH foi aplicado a vários domínios de problemas, incluindo:

• Detecção de quase duplicatas
• Agrupamento hierárquico
• Estudo de associação em todo o genoma
• Identificação de semelhança de imagem
  • VisualRank
• Identificação de similaridade de expressão gênica ^{[carece de fontes]}
• Identificação de similaridade de áudio
• Pesquisa de vizinho mais próximo
• Impressão digital de áudio
• Impressão digital de vídeo
• Organização de dados físicos em sistemas de gerenciamento de banco de dados
• Treinamento de redes neurais totalmente conectadas

• Segurança de computadores

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. Essa abordagem funciona para a distância de Hamming sobre vetores d -dimensionais $\{0,1\}^{d}$. Aqui, a família ${\mathcal {F}}$ de funções hash é simplesmente a família de todas as projeções de pontos em uma das $d$ coordenadas, ou seja, ${\mathcal {F}}=\{h\colon \{0,1\}^{d}\to \{0,1\}\mid h(x)=x_{i}{\text{ for some }}i\in \{1,\ldots ,d\}\}$, em que $x_{i}$ é a $i$-ésima coordenada de $x$. Uma função aleatória $h$ de ${\mathcal {F}}$ simplesmente seleciona um bit aleatório do ponto de entrada. Esta família tem os seguintes parâmetros: $P_{1}=1-R/d$, $P_{2}=1-cR/d$.

Permutações independentes min-wise

Ver artigo principal: Nilsimsa Hash

Suponha que U seja composto de subconjuntos de algum conjunto básico de itens enumeráveis S e que a função de similaridade de interesse seja o índice de Jaccard J. Se π é uma permutação nos índices de S, para $A\subseteq S$ seja $h(A)=\min _{a\in A}\{\pi (a)\}$. Cada escolha possível de π define uma única função hash h mapeando conjuntos de entrada em elementos de S .

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

Como o grupo simétrico em n elementos tem tamanho n!, escolher uma permutação verdadeiramente aleatória do grupo simétrico completo é inviável, mesmo para 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 π escolhida aleatoriamente. Foi estabelecido que uma família min-wise independente de permutações é pelo menos de tamanho $\operatorname {lcm} \{\,1,2,\ldots ,n\,\}\geq e^{n-o(n)}$, e que esse limite é ótimo.

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 k. A independência min-wise aproximada difere da propriedade em no máximo um ε fixo.

Métodos de código aberto

Hash de Nilsimsa

Ver artigo principal: Nilsimsa Hash

O Nilsimsa é um algoritmo de hash sensível à localidade usado em esforços anti-spam. 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:

1. O resumo que identifica cada mensagem não deve variar significativamente para alterações que podem ser produzidas automaticamente.
2. A codificação deve ser robusta contra ataques intencionais.
3. 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. 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.

Projeção aleatória

Sketch of 1-theta vs. cos(theta)

Para ângulos pequenos (não muito próximos do ortogonal), $1-{\frac {\theta }{\pi }}$ é uma boa aproximação para $\cos(\theta )$

O método de projeção aleatória de LSH devido a Moses Charikar chamado SimHash (também chamado às vezes de arccos) é 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 r ) no início e usar o hiperplano para fazer o hash dos vetores de entrada.

Dado um vetor de entrada v e um hiperplano definido por r, define-se $h(v)=sgn(v\cdot r)$ . Isto é, $h(v)=\pm 1$ dependendo de qual lado do hiperplano v está.

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

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 $h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}$ mapeia um vetor d-dimensional ${\boldsymbol {\upsilon }}$ no conjunto dos inteiros. Cada função hash na família é indexada por uma escolha aleatória de $\mathbf {a}$ e $b$, em que $\mathbf {a}$ é um vetor de dimensão d com entradas escolhidas independentemente a partir de uma distribuição estável e $b$ é um número real escolhido uniformemente no intervalo [0,r]. Para $\mathbf {a} ,b$ fixados, a função hash $h_{\mathbf {a} ,b}$ é dada por $h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }})=\left\lfloor {\frac {\mathbf {a} \cdot {\boldsymbol {\upsilon }}+b}{r}}\right\rfloor$.

Outros métodos de construção para funções de hash foram propostos um melhor ajuste dos dados. 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. Os hashcodes são encontrados através do treinamento de uma rede neural artificial ou 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 ${\mathcal {F}}$. O algoritmo tem dois parâmetros principais: o parâmetro de largura k e o número de tabelas hash L.

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

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

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

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

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

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

• tempo de pré-processamento: $O(n^{1+\rho }P_{1}^{-1}kt)$;
• espaço: $O(n^{1+\rho }P_{1}^{-1})$, além do espaço para armazenar os pontos de dados;
• tempo de consulta: $O(n^{\rho }P_{1}^{-1}(kt+d))$;

Melhorias

Quando t é grande, é possível tornar o tempo de hash menor inferior a $O(n^{\rho })$. Isso foi mostrado por e que deram

• tempo de consulta: $O(t\log ^{2}(1/P_{2})/P_{1}+n^{\rho }(d+1/P_{1})$;
• espaço: $O(n^{1+\rho }/P_{1}+\log ^{2}(1/P_{2})/P_{1})$;

Às vezes também acontece de o fator $1/P_{1}$ 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 foi mostrado como reduzir o tempo de consulta para $O(n^{\rho }/P_{1}^{1-\rho })$ (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
• Transformações relacionadas a Fourier
• Geohash
• Aprendizado de subespaço multilinear
• Análise de componentes principais
• Indexação aleatória
• Hash deslizante
• Decomposição em valores singulares
• Memória distribuída esparsa
• Compressão por wavelet

Leitura complementar

• Samet, H. (2006) Fundamentos de Estruturas de Dados Métricas e Multidimensionais . Morgan Kaufmann. ISBN 0-12-369446-9
• Indyk, Piotr; Motwani, Rajeev; Raghavan, Prabhakar; Vempala, Santosh (1997). Locality-preserving hashing in multidimensional spaces. STOC '97. pp. 618–625. CiteSeerX 10.1.1.50.4927. ISBN 978-0-89791-888-6. doi:10.1145/258533.258656 
• Chin, Andrew (1994). «Locality-preserving hash functions for general purpose parallel computation» (PDF). Algorithmica. 12 (2–3): 170–181. doi:10.1007/BF01185209 

Ligações externas

• Página inicial do LSH de Alex Andoni
• LSHKIT: uma biblioteca de hash sensível à localidade C++
• Uma biblioteca Python Locality Sensitive Hashing que opcionalmente oferece suporte à persistência via redis
• 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.
• Slash: Uma biblioteca C++ LSH, implementando Spherical LSH por Terasawa, K., Tanaka, Y
• 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.
• 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
• Código aberto TLSH no Github
• Porta JavaScript de TLSH (Trend Micro Locality Sensitive Hashing) agrupada como módulo node.js
• Porta Java de TLSH (Trend Micro Locality Sensitive Hashing) agrupada como pacote maven