Estou tentando entender a seção 5. deeste papel sobre o LSH, em particular como fazer o bucket dos hashes gerados. Citando o artigo vinculado:

Dados vetores de bits consistindo em d bits cada, escolhemos N = O (n 1 / (1 + epsilon)) permutações aleatórias dos bits. Para cada permutação aleatória σ, mantemos uma ordem classificada O σ dos vetores de bits, em ordem lexicográfica dos bits permutados por σ. Dado um vetor de bits de consulta q, encontramos o vizinho mais próximo aproximado, fazendo o seguinte: Para cada permissão σ, realizamos uma pesquisa binária em O σ para localizar os dois vetores de bits mais próximos de q (na ordem lexicográfica obtida por bits permutados por σ). Agora, pesquisamos em cada uma das ordens classificadas O σ examinando os elementos acima e abaixo da posição retornada pela pesquisa binária na ordem do comprimento do prefixo mais longo que corresponde a q. Isso pode ser feito mantendo dois ponteiros para cada ordem classificada O σ (uma se move para cima e a outra para baixo). Em cada etapa, movemos um dos ponteiros para cima ou para baixo, correspondendo ao elemento com o prefixo correspondente mais longo. (Aqui, o comprimento do prefixo correspondente mais longo em O σ é calculado em relação a q com seus bits permutados por σ). Examinamos os vetores de 2N = O (n 1 / (1 + epsilon)) bit dessa maneira. De todos os vetores de bits examinados, retornamos o que tem a menor distância de Hamming para q.

Estou confuso com esse algoritmo e acho que não entendi como ele funciona.

Eu já encontreiessa questão no tópico, mas não entendi a resposta nos comentários. Também emesta pergunta no ponto 2, o mesmo algoritmo é descrito, mas novamente, eu não entendo como ele funciona.

Você pode, por favor, tentar me explicar como funciona passo a passo, tentando ser o mais simples possível?

Até tentei fazer uma lista de coisas que não entendo, mas na prática é tão ruim escrever que não entendo a maioria das frases!

EDITAR após a resposta do gsamaras:

Eu entendi a resposta principalmente, mas ainda tenho algumas dúvidas:

É correto dizer que o custo total da execução doN permutações éO(Nnlogn), já que temos que classificar cada um deles?

O processo de permutação + classificação descrito acima é realizado apenas uma vez durante o pré-processamento ou paracada inquerirq? Parece já bastante caroO(Nnlogn) mesmo no pré-processamento, se for necessário fazer isso no momento da consulta, é um desastre: D

No último ponto, onde comparamosv0 ev4 paraq, comparamos a versão permutada ou a original (antes da permutação)?