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 é definida para
um espaço métrico , um limiar , um fator de aproximação , e probabilidades e .
Essa família é um conjunto de funções que levam elementos do espaço métrico em buckets . Uma família LSH deve satisfazer as seguintes condições para quaisquer dois pontos e qualquer função hash escolhidos uniformemente ao acaso a partir de :
Se , então (ou seja, e colidem) com probabilidade de pelo menos , Se , então com probabilidade no máximo .
Uma família é interessante quando . Uma tal família é chamada -sensível.
Alternativamente, a definição pode ser data em relação a um universo de itens que possuem uma função de similaridade . Um esquema LSH é uma família de funções hash , juntamente com uma distribuição de probabilidade sobre as funções, tal que uma função escolhido de acordo com satisfaz a propriedade que para qualquer .
Hash de preservação de localidade Um hash que preserva a localidade é uma função hash que leva pontos de um espaço métrico para um valor escalar tal que
para quaisquer três pontos .
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 -sensível , podemos construir novas famílias pela construção AND ou construção OR de .
Para criar uma construção AND, definimos uma nova família de funções hash , em que cada função é construída a partir de funções aleatórias de . Então dizemos que para uma função hash , se, e somente se, para cada . Já que os membros de são escolhidos independentemente para qualquer , é uma família -sensível.
Para criar uma construção OR, definimos uma nova família de funções hash , em que cada função é construída a partir de funções aleatórias de . Então dizemos que para uma função hash , se, e somente se, para um ou mais valores de . Já que os membros da são escolhidos independentemente para qualquer , é uma família -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 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 -dimensionais . Aqui, a família de funções hash é simplesmente a família de todas as projeções de pontos em uma das coordenadas, ou seja, , em que é a -ésima coordenada de . Uma função aleatória de simplesmente seleciona um bit aleatório do ponto de entrada. Esta família tem os seguintes parâmetros: , .
Permutações independentes min-wise
Suponha que seja composto de subconjuntos de algum conjunto básico de itens enumeráveis e que a função de similaridade de interesse seja o índice de Jaccard . Se é uma permutação nos índices de , para seja . Cada escolha possível de define uma única função hash mapeando conjuntos de entrada em elementos de .
Defina a família de funções como o conjunto de todas essas funções e seja a distribuição uniforme. Dados dois conjuntos , o evento que corresponde exatamente ao evento em que o minimizador de sobre encontra-se dentro de . Como foi escolhida uniformemente ao acaso, e define um esquema LSH para o índice Jaccard.
Como o grupo simétrico em elementos tem tamanho !, escolher uma permutação verdadeiramente aleatória do grupo simétrico completo é inviável, mesmo para 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 , 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 . A independência min-wise aproximada difere da propriedade em no máximo um fixo.
Métodos de código aberto
Hash de Nilsimsa
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:
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. 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 alt=Sketch of 1-theta vs. cos(theta)|miniaturadaimagem| Para ângulos pequenos (não muito próximos do ortogonal), é uma boa aproximação para 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 ) no início e usar o hiperplano para fazer o hash dos vetores de entrada.
Dado um vetor de entrada e um hiperplano definido por , define-se . Isto é, dependendo de qual lado do hiperplano está.
Cada escolha possível de define uma única função. Seja o conjunto de todas essas funções e seja , novamente, a distribuição uniforme. Não é difícil provar que, para dois vetores , , em que é o ângulo entre e . O valor está intimamente relacionado com .
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 mapeia um vetor -dimensional no conjunto dos inteiros. Cada função hash na família é indexada por uma escolha aleatória de e , em que é um vetor de dimensão com entradas escolhidas independentemente a partir de uma distribuição estável e é um número real escolhido uniformemente no intervalo [0,r]. Para fixados, a função hash é dada por .
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 . O algoritmo tem dois parâmetros principais: o parâmetro de largura e o número de tabelas hash .
Na primeira etapa, definimos uma nova família de funções hash , em que cada função é obtida pela concatenação de funções de , ou seja, . Em outras palavras, uma função hash aleatória é obtida concatenando funções hash de escolhidas aleatoriamente. O algoritmo então constrói tabelas hash, cada uma correspondendo a uma função hash diferente escolhida aleatoriamente.
Na etapa de pré-processamento, misturamos todos os pontos -dimensionais do conjunto de dados em cada uma das tabelas de hash. Dado que as tabelas de hash resultantes têm apenas entradas diferentes de zero, pode-se reduzir a quantidade de memória usada por cada tabela de hash para usando funções de hash padrão.
Dado um ponto de consulta , o algoritmo itera sobre as funções hash . Para cada considerada, ele recupera os pontos de dados cujo hash está no mesmo bucket que . O processo é interrompido assim que é encontrado um ponto dentro da distância de .
Dados os parâmetros e , o algoritmo tem as seguintes garantias de desempenho:
tempo de pré-processamento: , em que é o tempo para avaliar uma função em um ponto de entrada ; espaço: , além do espaço para armazenar os pontos de dados; tempo de consulta: ; o algoritmo consegue encontrar um ponto dentro da distância de (se existe um ponto dentro da distância ) com probabilidade de pelo menos ;
Para uma razão de aproximação fixa e probabilidades e , pode-se definir e , em que . Obtém-se então as seguintes garantias de desempenho:
tempo de pré-processamento: ; espaço: , além do espaço para armazenar os pontos de dados; tempo de consulta: ;
Melhorias