ES
La compresión de grafos HNSW reduce el espacio con poco coste de latencia
Lossless Compression of Proximity Graph Indexes for Efficient Approximate Nearest Neighbors Search · arXiv:2610.37176
En palabras sencillas
La búsqueda vectorial encuentra elementos cuyas descripciones numéricas se parecen a una consulta. Un índice HNSW (mundo pequeño navegable jerárquico) también guarda enlaces entre elementos cercanos, y esos enlaces pueden ocupar mucha memoria.
El artículo presenta un método sin pérdida para guardar los enlaces de HNSW en menos espacio y descodificarlos durante la búsqueda. En pruebas con cuatro conjuntos de datos, la latencia se mantuvo cerca de la de la versión sin compresión al comparar la misma precisión de recuperación, mientras los enlaces ocuparon menos espacio.
La investigación
En un índice de búsqueda vectorial, los enlaces del grafo pueden ocupar mucha memoria, sobre todo cuando los vectores se guardan de forma compacta.
Aún no está claro si esos enlaces se pueden comprimir y permitir que una búsqueda en línea descodifique las vecindades visitadas sin añadir una demora costosa.
En índices HNSW (mundo pequeño navegable jerárquico), los autores reordenan los identificadores de los nodos y codifican las listas de vecinos sin pérdida para recuperarlas rápidamente cuando se buscan.
En pruebas con cuatro conjuntos de datos diversos, los autores comparan grafos comprimidos con Stream VByte con Plain, su versión HNSW sin compresión. Miden el espacio de las aristas y la latencia media de consulta con niveles equivalentes de precisión de recuperación.
El almacenamiento se reduce hasta 2.1 veces en Sift1M. En los conjuntos evaluados, la latencia iguala o mejora la de la versión sin compresión en tres, y es solo marginalmente mayor en Sift1M. Esto respalda una ganancia de espacio con poco coste de latencia medido en estas pruebas.
Estos resultados respaldan una relación entre almacenamiento y latencia para las configuraciones de HNSW evaluadas, no para todos los índices de grafos o cargas de trabajo. Los parámetros de búsqueda se ajustaron para alcanzar cada nivel de precisión, y el artículo no establece que fueran idénticos en las pruebas con y sin compresión.
Qué muestran las pruebas
- El equilibrio entre espacio y velocidad
El método sin pérdida para comprimir listas de adyacencia de HNSW reduce la memoria que ocupan los enlaces en un índice HNSW (mundo pequeño navegable jerárquico).
Aborda una tensión: los enlaces del grafo pueden ocupar mucha memoria, especialmente cuando los vectores son compactos, pero la búsqueda debe descodificar las vecindades que visita, y ese trabajo puede aumentar la latencia. La pregunta es si los enlaces pueden ocupar menos espacio sin ralentizar la recuperación.
- Por qué descartaron copiar listas
Los autores prueban primero si las listas pueden ahorrar espacio al referirse a vecinos compartidos en otras listas. Incluso un cálculo idealizado —que ignora el coste de guardar identificadores de referencia y permite cadenas cíclicas ilimitadas— establece un límite de solo el 8.8% del espacio de las aristas en eBayProducts7M.
Como una versión práctica ahorraría menos y añadiría demora al seguir referencias, dejan de lado esta opción y buscan que cada lista se pueda comprimir mejor por separado.
- Reordenar reduce las diferencias
El siguiente paso consiste en reordenar los identificadores de los nodos para que los nodos conectados tiendan a tener identificadores cercanos y luego guardar las diferencias entre identificadores de vecinos. En eBayProducts7M, la entropía global es de 22.62 bits por valor para los identificadores originales de las aristas, de 18.52 tras la codificación por diferencias convencional y de 14.99 para las diferencias tras reordenar con EGB.
Esta medición de todos los valores de las listas de adyacencia muestra cómo el reordenamiento facilita la compresión de las diferencias; por sí sola no indica la velocidad de búsqueda.
- Medir espacio y latencia
Los autores comparan grafos comprimidos con Stream VByte y Plain, la versión sin compresión, en cuatro conjuntos de datos. Accuracy@10 mide qué proporción de los diez vecinos más cercanos reales se encuentra entre los diez resultados, promediada entre consultas; los autores comparan la latencia media con niveles de precisión equivalentes.
Stream VByte reduce hasta 2.1 veces el almacenamiento de aristas en Sift1M, mientras que su latencia se mantiene cerca de la de Plain en los distintos conjuntos. Esto respalda una ganancia de espacio con un coste de latencia medido pequeño en estas pruebas.
- Evidencia en producción
El artículo presenta aparte un resultado del sistema HNSW de búsqueda activa de eBay: el almacenamiento del grafo se redujo un 44.3% con la misma recuperación aproximada de vecinos más cercanos, sin degradación medible de la latencia bajo cargas de trabajo reales.
Esto respalda la utilidad del método en ese sistema concreto. En conjunto, las pruebas con conjuntos de datos y el informe de producción muestran menos almacenamiento con poco coste de latencia medido en los entornos indicados; el artículo no evalúa otros tipos de índices de grafos.
Detalles
- Autores del paper original
- Francesco Benocci, Leonard Dahlmann, Francesco Gargiulo, Tobias Heuer, Silvio Martinico
- Enviado a arXiv
- Licencia
- CC BY 4.0