Atualmente estou estudando como encontrar um vizinho mais próximo usando hashing sensível à localidade. No entanto, enquanto estou lendo artigos e pesquisando na web, encontrei dois algoritmos para fazer isso:

1- Use o número L de tabelas hash com o número L de funções LSH aleatórias, aumentando assim a chance de que dois documentos sejam semelhantes para obter a mesma assinatura. Por exemplo, se dois documentos são 80% semelhantes, há uma chance de 80% de obter a mesma assinatura de uma função LSH. No entanto, se usarmos várias funções LSH, haverá uma chance maior de obter a mesma assinatura para os documentos de uma das funções do LSH. Este método é explicado na wikipedia e espero que meu entendimento esteja correto:

http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

2- O outro algoritmo usa um método de um papel (seção 5) chamado: Técnicas de Estimação de Similaridade de Algoritmos de Arredondamento por Moses S. Charikar. É baseado no uso de uma função LSH para gerar a assinatura e, em seguida, aplicar permutações P e, em seguida, ordenar a lista. Na verdade, não entendo muito bem o método e espero que alguém possa esclarecê-lo.

Minha principal questão é: por que alguém usaria o segundo método em vez do primeiro método? Como eu acho, é mais fácil e rápido.

Eu realmente espero que alguém possa ajudar !!!

EDIT: Na verdade eu não tenho certeza se @ Raff.Edward estava misturando entre o "primeiro" eo "segundo". Porque apenas o segundo método usa um raio e o primeiro usa apenas uma nova família hash g composta da família hash F. Por favor, verifique o link wikipedia. Eles apenas usaram muitas funções g para gerar assinaturas diferentes e, em seguida, para cada função g, ele possui uma tabela hash correspondente. Para encontrar o vizinho mais próximo de um ponto, basta deixar o ponto passar pelas funções g e verificar as tabelas de hash correspondentes para colisões. Assim, como eu entendi como mais função ... mais chance de colisões.

Eu não encontrei nenhuma menção sobre raio para o primeiro método.

Para o segundo método, eles geram apenas uma assinatura para cada vetor de recurso e, em seguida, aplicam permutações P neles. Agora temos listas P de permutações, onde cada uma contém n assinaturas. Agora eles ordenam cada lista de P. Depois disso, dado um ponto de consulta q, eles geram a assinatura para ela e então aplicam as permutações P nela e então usam busca binária em cada lista P permutada e ordenada para encontrar a assinatura mais similar a a consulta q. Eu concluí isso depois de ler muitos artigos sobre isso, mas eu ainda não entendo por que alguém iria usar tal método, porque não parece rápido em encontrar a distância de hamming !!!!

Para mim, eu simplesmente faria o seguinte para encontrar o vizinho mais próximo para um ponto de consulta q. Dada uma lista de assinaturas N, eu geraria a assinatura para o ponto de consulta q e, em seguida, examinaria a lista N e calcularia a distância de hamming entre cada elemento em N e a assinatura de q. Assim eu acabaria com o vizinho mais próximo para q. E leva O (N) !!!