When Does a Partitioned ANN Index Need Active Re-Partitioning Under Drift?  A Characterization and Benchmark 

Resumen Técnico: ¿Cuándo necesita un índice ANN particionado una re-partición activa bajo deriva?

Declaración del Problema
Los índices de vecinos más cercanos aproximados (ANN) sirven cada vez más a corpus no estacionarios donde las distribuciones de datos cambian debido a inserciones, eliminaciones continuas y actualizaciones de modelos. Una premisa prevalente en la investigación de sistemas (p. ej., Quake, Ada-IVF, GTI, CrackIVF, SPFresh, DeDrift) postula que las particiones estáticas se vuelven obsoletas ante la deriva de datos, causando un colapso en el recall a menos que el índice sea activamente re-particionado (mediante división, fusión, re-clustering o cracking). Este artículo desafía la universalidad de esta premisa, preguntando: bajo qué condiciones específicas de deriva es realmente necesaria la re-partición activa, frente a cuándo la deriva puede ser absorbida por un índice estático con un presupuesto de sondeo ligeramente ajustado.

Metodología
Los autores no realizan un benchmark comparativo directo de los sistemas existentes. En su lugar, construyen un entorno de control de recall emparejado para caracterizar la compensación entre los costos de mantenimiento y reconstrucción. Los componentes metodológicos clave incluyen:

• Protocolo de Recall Emparejado (Matched-Recall Protocol): A diferencia de los benchmarks que fijan un control de costo (p. ej., presupuesto de sondeo $b$) y miden el recall, este protocolo fija un piso de recall (0.90) y mide el presupuesto de sondeo mínimo ($b_{needed}$) y la latencia requeridos para lograrlo. Esto aisla el costo del mantenimiento del efecto de confusión del cambio en la cobertura (p. ej., dividir particiones reduce la masa cubierta por un $b$ fijo).
• Generadores de Carga de Trabajo: El estudio utiliza ejes de deriva parametrizados:
  • Turnover ($\tau$): Fracción del conjunto vivo reemplazado.
  • Tasa de Actualización ($u$): Ratio de actualizaciones respecto a las consultas.
  • Correlación ($\rho$): Desacoplamiento de la deriva de datos de la deriva de consultas.
  • Ventana Acotada (Bounded Window): Un modo donde la cardinalidad permanece constante mientras la distribución rota, aislando la deriva de los efectos de escala.
• Verdad de Terreno Compartida (Shared Ground Truth): Se computa una verdad de terreno exacta basada en claves de contenido una vez por checkpoint y se comparte entre todos los brazos experimentales (estático, split/merge, recluster, rebuild) para asegurar una comparación justa.
• Puertas de Salida Pre-Registradas (Pre-Registered Kill-Gates): El estudio emplea una secuencia de criterios falsables para evitar el "rescate" de una hipótesis. Si una hipótesis (p. ej., "graph-in-leaf es una victoria estática") falla en una puerta, el trabajo pivota en lugar de ajustar los parámetros para forzar un resultado positivo.
• Brazos Probados:
  • Estático (C0): Sin mantenimiento, con eliminaciones mediante tombstones.
  • Variantes de Mantenimiento: Split/merge disparado por deriva, split disparado por cardinalidad y re-centrado incremental.
  • Referencia (R): Un recluster completo dentro de la arquitectura (reconstrucción desde cero) que sirve como línea base de calidad.
  • Verificación Externa: El artefacto real de Quake (OSDI'25) se ejecutó en el mismo trazo para validación externa.

Resultados Clave

1. Suficiencia Estática en Deriva Moderada:
   En conjuntos de datos con crecimiento/turnover moderado (SIFT1M, GIST1M), una partición estática con eliminaciones por tombstone mantiene el piso de recall de 0.90 con el mismo presupuesto de sondeo que las variantes mantenidas. El mantenimiento activo es innecesario en este régimen; el "margen" (slack) en el presupuesto de sondeo absorbe la deriva.

2. Graph-in-Leaf no es una Victoria Estática:
   El índice híbrido graph-in-leaf (que motiva el trabajo original) está dominado en Pareto por un HNSW plano en la frontera de recall estático–QPS. No ofrece ninguna ventaja de búsqueda estática, solo un tiempo de construcción más rápido.

3. El Límite del Régimen (Deriva Rotacional):
   En una ventana rotatoria de escala controlada (MS-Turing-10M), una partición estática se degrada materialmente. Su presupuesto de sondeo requerido ($b_{needed}$) aumenta de 64 a 112+ a medida que la distribución rota. En este régimen, el re-centrado es genuinamente necesario para mantener la eficiencia.

4. Re-centrado Incremental vs. Reconstrucción Completa:
   En el régimen de deriva rotacional, un re-centrado incremental económico iguala la calidad de recall de un recluster completo (idéntico $b_{needed}$) a aproximadamente 1/6 de parte del costo de regeneración.

   • Costo Total de Propiedad (TCO): En cargas de trabajo realistas con alta densidad de consultas, el re-centrado incremental y las reconstrucciones completas son equivalentes en TCO. El re-centrado incremental gana estrictamente solo en cargas de trabajo con alta tasa de actualización.
   • Sin Punto de Crossover a Favor de la Reconstrucción: El artículo refuta una afirmación anterior de un punto de cruce ($u^* \approx 4.7$) donde las reconstrucciones completas se vuelven superiores, identificándolo como un artefacto de atribuir la latencia de construcción fresca a índices obsoletos y de un desfase temporal secuencial.

5. Validación Externa (Quake):
   La ejecución del sistema real Quake en el mismo trazo confirmó el límite del régimen: Quake mantiene el piso de recall con una fracción de escaneo acotada. Sin embargo, su política por defecto basada en el tamaño fragmentó el índice (aumentando $nlist$ 13 veces), incurriendo en altos costos de mantenimiento, mientras que un re-centrado controlado mantuvo un presupuesto pequeño de forma económica.

Contribuciones

1. Un Benchmark Controlado: Un workload de deriva parametrizado y un entorno con un protocolo de recall emparejado, que desacopla la deriva de datos/consultas y proporciona una verdad de terreno por región.
2. Un Mapa de Regímenes: Una caracterización que distingue entre regímenes de "suficiencia estática" (crecimiento/turnover moderado) y regímenes de "ayuda por re-centrado" (deriva rotacional).
3. Una Regla de Decisión: Una guía práctica para profesionales:
   • Crecimiento Moderado: Manténgase estático; use eliminaciones por tombstone y un presupuesto de sondeo ligeramente mayor.
   • Deriva Rotacional: Re-centre, pero use re-centrado incremental en lugar de reconstrucción completa.
   • Elección de Disparador: Los disparadores basados en deriva vs. cardinalidad no muestran diferencia en el recall; elija según la conveniencia de ingeniería.
4. Marco Explicativo: Un modelo de "margen de presupuesto de sondeo" ($\sigma < b$) que explica cuándo la obsolescencia es absorbible frente a cuándo fuerza la re-partición.
5. Resultados Negativos Honestos: Correcciones de sobre-afirmaciones en el campo, específicamente que el graph-in-leaf no es una victoria estática y que el split/merge sin re-centrado simplemente fragmenta el índice en lugar de reducir la obsolescencia.

Significancia y Reclamaciones
El artículo afirma que su principal contribución es un mapa de regímenes y una regla de decisión, no un nuevo algoritmo de mantenimiento. Argumenta que la premisa "la deriva requiere re-partición activa" es condicional.

• En el régimen de margen (deriva moderada), el mantenimiento no es una necesidad de corrección; es un compromiso de costo que a menudo es innecesario.
• En el régimen forzado (deriva rotacional), el mantenimiento es necesario, pero una reconstrucción completa periódica es evitable. El re-centrado incremental logra la misma calidad de recall que una reconstrucción completa a una fracción del costo de regeneración.
• El documento enfatiza que el protocolo de recall emparejado y control de contención es tan significativo como los resultados, ya que evita los errores de confusión (p. ej., comparaciones de presupuesto fijo) que llevaron anteriormente a conclusiones erróneas sobre la necesidad y el costo del mantenimiento.

Los autores declaran explícitamente que no pretenden haber resuelto todos los modos de deriva (p. ej., no se cubren la deriva de desaparición pura o trazas de deriva de consulta real) y que sus hallazgos están limitados a la familia específica de índices (router k-means con hojas HNSW/flat) y las magnitudes de deriva probadas.