Hashing sensible a consultas y localización para búsqueda aproximada de vecinos más cercanos

El Hashing Sensible a la Localización (LSH) y sus variantes son los esquemas de indexación bien conocidos para el problema de búsqueda c -Vecinos Más Cercanos Aproximados (c -ANN) en espacio euclidiano de alta dimensión. Tradicionalmente, las funciones LSH se construyen de manera que ignoran las consultas, en el sentido de que los cubos se dividen antes de que llegue cualquier consulta. Sin embargo, los objetos más cercanos a una consulta pueden ser divididos en cubos diferentes, lo cual es indeseable. Debido al uso de la partición de cubos que ignora la consulta, los esquemas LSH de vanguardia para memoria externa, a saber, C2LSH y LSB-Forest, solo funcionan con una razón de aproximación de c entero ≥ 2. En este artículo, introducimos un concepto novedoso de partición de cubos sensible a consultas, que utiliza una consulta dada como el "ancla" para la partición de cubos. En consecuencia, una función LSH sensible a consultas es una proyección aleatoria acompañada de partición de cubos sensible a consultas, que elimina el desplazamiento aleatorio requerido por las funciones LSH tradicionales que ignoran las consultas. Notablemente, la partición de cubos sensible a consultas puede ser implementada fácilmente para garantizar el rendimiento de las consultas. Proponemos un nuevo esquema LSH sensible a consultas llamado QALSH para la búsqueda c -ANN sobre memoria externa. Nuestros estudios teóricos muestran que QALSH ofrece una garantía sobre la calidad de la consulta. El uso de la función LSH sensible a consultas permite que QALSH funcione con cualquier razón de aproximación c > 1. Experimentos extensivos muestran que QALSH supera a C2LSH y LSB-Forest, especialmente en espacio de alta dimensión. Específicamente, al usar una razón c < 2, QALSH puede lograr una calidad de consulta mucho mejor.