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.^[1] (O número de grupos é muito menor que o universo de itens de entrada possíveis.)^[1] 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).^[2]^[3]

Definições

Uma família LSH^[1]^[4]^[5] $ℱ$ é definida para

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

Essa família $ℱ$ é um conjunto de funções $h : 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 $ℱ$ :

Se $d (p, q) \leq R$ , então $h (p) = h (q)$ (ou seja, Predefinição:Mvar e Predefinição:Mvar colidem) com probabilidade de pelo menos $P_{1}$ ,
Se $d (p, q) \geq c R$ , 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 $ℱ$ é chamada $(R, c R, P_{1}, P_{2})$ -sensível.

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

Hash de preservação de localidade

Um hash que preserva a localidade é uma função hash Predefinição:Mvar que leva pontos de um espaço métrico $ℳ = (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.^[7]^[8]

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 $ℱ$ , podemos construir novas famílias $𝒢$ pela construção AND ou construção OR de $ℱ$ .^[1]

Para criar uma construção AND, definimos uma nova família $𝒢$ de funções hash Predefinição:Mvar, em que cada função Predefinição:Mvar é construída a partir de Predefinição:Mvar funções aleatórias $h_{1}, \dots, h_{k}$ de $ℱ$ . Então dizemos que para uma função hash $g \in 𝒢$ , $g (x) = g (y)$ se, e somente se, $h_{i} (x) = h_{i} (y)$ para cada $i = 1, 2, \dots, k$ . Já que os membros de $ℱ$ são escolhidos independentemente para qualquer $g \in 𝒢$ , $𝒢$ é 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 $𝒢$ de funções hash Predefinição:Mvar, em que cada função Predefinição:Mvar é construída a partir de Predefinição:Mvar funções aleatórias $h_{1}, \dots, h_{k}$ de $ℱ$ . Então dizemos que para uma função hash $g \in 𝒢$ , $g (x) = g (y)$ se, e somente se, $h_{i} (x) = h_{i} (y)$ para um ou mais valores de Predefinição:Mvar. Já que os membros da $ℱ$ são escolhidos independentemente para qualquer $g \in 𝒢$ , $𝒢$ é 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^[9]
Agrupamento hierárquico^[10]^[11]
Estudo de associação em todo o genoma^[12]
Identificação de semelhança de imagem
- VisualRank
Identificação de similaridade de expressão gênica Predefinição:Carece de fontes
Identificação de similaridade de áudio
Pesquisa de vizinho mais próximo
Impressão digital de áudio^[13]
Impressão digital de vídeo
Organização de dados físicos em sistemas de gerenciamento de banco de dados^[14]
Treinamento de redes neurais totalmente conectadas^[15]^[16]

Segurança de computadores^[17]

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.^[5] Essa abordagem funciona para a distância de Hamming sobre vetores Predefinição:Mvar -dimensionais ${0, 1}^{d}$ . Aqui, a família $ℱ$ de funções hash é simplesmente a família de todas as projeções de pontos em uma das $d$ coordenadas, ou seja, $ℱ = {h : {0, 1}^{d} \to {0, 1} ∣ h (x) = x_{i} for some i \in {1, \dots, d}}$ , em que $x_{i}$ é a $i$ -ésima coordenada de $x$ . Uma função aleatória $h$ de $ℱ$ 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 - c R / d$ .

Permutações independentes min-wise

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

Defina a família de funções Predefinição:Mvar como o conjunto de todas essas funções e seja Predefinição:Mvar 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 Predefinição:Mvar sobre $A \cup B$ encontra-se dentro de $A \cap B$ . Como Predefinição:Mvar foi escolhida uniformemente ao acaso, $P r [h (A) = h (B)] = J (A, B)$ e $(H, D)$ define um esquema LSH para o índice Jaccard.

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

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 Predefinição:Mvar.^[20] A independência min-wise aproximada difere da propriedade em no máximo um Predefinição:Mvar fixo.^[21]

Métodos de código aberto

Hash de Nilsimsa

Predefinição:Artigo principal O Nilsimsa é um algoritmo de hash sensível à localidade usado em esforços anti-spam.^[22] 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.^[17] 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.^[23]

Projeção aleatória

Sketch of 1-theta vs. cos(theta)

Para ângulos pequenos (não muito próximos do ortogonal),

1 - \frac{θ}{π}

é uma boa aproximação para

\cos (θ)

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

Dado um vetor de entrada Predefinição:Mvar e um hiperplano definido por Predefinição:Mvar, define-se $h (v) = s g n (v \cdot r)$ . Isto é, $h (v) = \pm 1$ dependendo de qual lado do hiperplano Predefinição:Mvar está.

Cada escolha possível de Predefinição:Mvar define uma única função. Seja Predefinição:Mvar o conjunto de todas essas funções e seja Predefinição:Mvar, novamente, a distribuição uniforme. Não é difícil provar que, para dois vetores $u, v$ , $P r [h (u) = h (v)] = 1 - \frac{θ (u, v)}{π}$ , em que $θ (u, v)$ é o ângulo entre Predefinição:Mvar e Predefinição:Mvar . O valor $1 - \frac{θ (u, v)}{π}$ está intimamente relacionado com $\cos (θ (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^[25] $h_{𝐚, b} (υ) : ℛ^{d} \to 𝒩$ mapeia um vetor Predefinição:Mvar-dimensional $υ$ no conjunto dos inteiros. Cada função hash na família é indexada por uma escolha aleatória de $𝐚$ e $b$ , em que $𝐚$ é um vetor de dimensão Predefinição:Mvar 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 $𝐚, b$ fixados, a função hash $h_{𝐚, b}$ é dada por $h_{𝐚, b} (υ) = ⌊ \frac{𝐚 \cdot υ + b}{r} ⌋$ .

Outros métodos de construção para funções de hash foram propostos um melhor ajuste dos dados.^[26] 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.^[27] 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 $ℱ$ . O algoritmo tem dois parâmetros principais: o parâmetro de largura Predefinição:Mvar e o número de tabelas hash Predefinição:Mvar.

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

Na etapa de pré-processamento, misturamos todos os Predefinição:Mvar pontos Predefinição:Mvar-dimensionais do conjunto de dados Predefinição:Mvar em cada uma das Predefinição:Mvar tabelas de hash. Dado que as tabelas de hash resultantes têm apenas Predefinição:Mvar 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 Predefinição:Mvar, o algoritmo itera sobre as Predefinição:Mvar funções hash Predefinição:Mvar. Para cada Predefinição:Mvar considerada, ele recupera os pontos de dados cujo hash está no mesmo bucket que Predefinição:Mvar. O processo é interrompido assim que é encontrado um ponto dentro da distância $c R$ de Predefinição:Mvar.

Dados os parâmetros Predefinição:Mvar e Predefinição:Mvar, o algoritmo tem as seguintes garantias de desempenho:

tempo de pré-processamento: $O (n L k t)$ , em que Predefinição:Mvar é o tempo para avaliar uma função $h \in ℱ$ em um ponto de entrada Predefinição:Mvar;
espaço: $O (n L)$ , além do espaço para armazenar os pontos de dados;
tempo de consulta: $O (L (k t + d n P_{2}^{k}))$ ;
o algoritmo consegue encontrar um ponto dentro da distância $c R$ de Predefinição:Mvar (se existe um ponto dentro da distância Predefinição:Mvar) com probabilidade de pelo menos $1 - (1 - P_{1}^{k})^{L}$ ;

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

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

Melhorias

Quando Predefinição:Mvar é grande, é possível tornar o tempo de hash menor inferior a $O (n^{ρ})$ . Isso foi mostrado por^[28] e^[29] que deram

tempo de consulta: $O (t \log^{2} (1 / P_{2}) / P_{1} + n^{ρ} (d + 1 / P_{1})$ ;
espaço: $O (n^{1 + ρ} / 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^[30] foi mostrado como reduzir o tempo de consulta para $O (n^{ρ} / P_{1}^{1 - ρ})$ (sem incluir os custos de hash) e, da mesma forma, o uso do espaço.

Ver também

Referências

↑ ^1,0 ^1,1 ^1,2 ^1,3 Predefinição:Citar web
↑ Predefinição:Citar conferência
↑ Predefinição:Citar livro
↑ Predefinição:Citar periódico
↑ ^5,0 ^5,1 Predefinição:Citar conferência
↑ ^6,0 ^6,1 Predefinição:Citar conferência
↑ Predefinição:Citar tese
↑ Predefinição:Citar periódico
↑ Predefinição:Citation.
↑ Predefinição:Citation.
↑ Predefinição:Citation.
↑ Predefinição:Citation
↑ Predefinição:Citation
↑ Predefinição:Citation
↑ Predefinição:Citar arXiv
↑ Predefinição:Citation
↑ ^17,0 ^17,1 Predefinição:Citar conferência
↑ Predefinição:Citar conferência
↑ Predefinição:Citar periódico
↑ Predefinição:Citar periódico
↑ Predefinição:Citar periódico
↑ Predefinição:Citar web
↑ Predefinição:Citar web
↑ Predefinição:Citar periódico
↑ Predefinição:Citar periódico
↑ Predefinição:Citar periódico
↑ Predefinição:Citar periódico
↑ Dahlgaard, Søren, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. "Fast similarity sketching." 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017.
↑ Christiani, Tobias. "Fast locality-sensitive hashing frameworks for approximate near neighbor search." International Conference on Similarity Search and Applications. Springer, Cham, 2019.
↑ Ahle, Thomas Dybdahl. "On the Problem of $$ p_1^{-1} $$ in Locality-Sensitive Hashing." International Conference on Similarity Search and Applications. Springer, Cham, 2020.
↑ Gorman, James, and James R. Curran. "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.

Leitura complementar

Samet, H. (2006) Fundamentos de Estruturas de Dados Métricas e Multidimensionais . Morgan Kaufmann. ISBN 0-12-369446-9
Predefinição:Citar conferência
Predefinição:Citar periódico

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

[MOMD-1] 1,0 ^1,1 ^1,2 ^1,3 Predefinição:Citar web

[2] Predefinição:Citar conferência

[3] Predefinição:Citar livro

[GIM1999-4] Predefinição:Citar periódico

[IndykMotwani98-5] 5,0 ^5,1 Predefinição:Citar conferência

[Charikar2002-6] 6,0 ^6,1 Predefinição:Citar conferência

[Chin1991-7] Predefinição:Citar tese

[Chin1994-8] Predefinição:Citar periódico

[9] Predefinição:Citation.

[10] Predefinição:Citation.

[11] Predefinição:Citation.

[12] Predefinição:Citation

[13] Predefinição:Citation

[14] Predefinição:Citation

[15] Predefinição:Citar arXiv

[16] Predefinição:Citation

[TLSH-17] 17,0 ^17,1 Predefinição:Citar conferência

[Broder1998-18] Predefinição:Citar conferência

[19] Predefinição:Citar periódico

[Matousek2002-20] Predefinição:Citar periódico

[Saks2000-21] Predefinição:Citar periódico

[22] Predefinição:Citar web

[23] Predefinição:Citar web

[Andoni2008-24] Predefinição:Citar periódico

[DIIM04-25] Predefinição:Citar periódico

[PJA10-26] Predefinição:Citar periódico

[27] Predefinição:Citar periódico

[28] Dahlgaard, Søren, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. "Fast similarity sketching." 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2017.

[29] Christiani, Tobias. "Fast locality-sensitive hashing frameworks for approximate near neighbor search." International Conference on Similarity Search and Applications. Springer, Cham, 2019.

[30] Ahle, Thomas Dybdahl. "On the Problem of $$ p_1^{-1} $$ in Locality-Sensitive Hashing." International Conference on Similarity Search and Applications. Springer, Cham, 2020.

[31] Gorman, James, and James R. Curran. "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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

Hashing sensível à localidade

Índice

Definições

Hash de preservação de localidade

Amplificação

Aplicações

Métodos

Amostragem de bits para a distância de Hamming

Permutações independentes min-wise

Métodos de código aberto

Hash de Nilsimsa

TLSH

Projeção aleatória

Distribuições estáveis

Hashing semântico

Algoritmo LSH para a busca do vizinho mais próximo

Melhorias

Ver também

Referências

Leitura complementar

Ligações externas

Menu de navegação

Hashing sensível à localidade

Definições

Hash de preservação de localidade

Amplificação

Aplicações

Métodos

Amostragem de bits para a distância de Hamming

Permutações independentes min-wise

Métodos de código aberto

Hash de Nilsimsa

TLSH

Projeção aleatória

Distribuições estáveis

Hashing semântico

Algoritmo LSH para a busca do vizinho mais próximo

Melhorias

Ver também

Referências

Leitura complementar

Ligações externas

Menu de navegação

Pesquisa