He estado leyendo sobre la literatura sobre hashing sensible a la localidad, y creo que entiendo bastante bien cómo funciona. Considerando el caso más simple de una sola tabla hash donde cada documento está en un solo cubo, mi pregunta es:

¿Cómo encuentro k vecinos más cercanos donde k es mayor que la cantidad de documentos en ese depósito?

He visto varios métodos para lograr esto. Algunos usan un árbol de prefijos . Otros clasifican todos los cubos por su distancia de martillo.

Mis limitaciones:

Tengo mis ID de documentos almacenados en PostgreSQL junto con sus respectivos cubos. Un escaneo completo de la tabla para calcular la distancia de hamming con cada cubeta no es factible (tengo cientos de millones de documentos ). El hash de mi cubo probablemente será de 24 o 32 bits (a menos que haya una sugerencia en contra de esto). ¿Alguien tiene experiencia o enfoques sugeridos sobre cómo proceder?