Hashing que preserva a vizinhança e consultas aproximadas

Deixe D ⊆ Σn ser um dicionário. Procuramos estruturas de dados e algoritmos eficientes para resolver o seguinte problema de consulta aproximada: Dada uma consulta u ∈ Σ n, liste todas as palavras v ∈ D que estão próximas a u em distância de Hamming. O problema se reduz ao seguinte problema combinatório: Faça hash dos vértices do hipercubo n-dimensional em baldes, de modo que (1) a c-vizinhança de cada vértice seja mapeada em no máximo k baldes e (2) nenhum balde seja muito grande. Limites inferiores e superiores são dados para a compensação entre k e o tamanho do maior balde. Esses resultados são usados para derivar limites para o problema de consulta aproximada.