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

Sintesi Tecnica: Quando un indice ANN partizionato necessita di una ri-partizione attiva sotto drift?

Problematica
Gli indici per la ricerca dei vicini più prossimi approssimati (ANN) servono sempre più spesso corpora non stazionari dove le distribuzioni dei dati cambiano a causa di inserimenti continui, cancellazioni e aggiornamenti dei modelli. Un presupposto prevalente nella ricerca sui sistemi (es. Quake, Ada-IVF, GTI, CrackIVF, SPFresh, DeDrift) postula che le partizioni statiche diventino obsolete sotto l'effetto del drift dei dati, causando un crollo del recall a meno che l'indice non venga attivamente ri-partizionato (tramite splitting, merging, riclustering o cracking). Questo articolo mette in discussione l'universalità di tale presupposto, chiedendosi: sotto quali specifiche condizioni di drift la ri-partizione attiva è effettivamente necessaria, rispetto a quando il drift può essere assorbito da un indice statico con un budget di probing leggermente aggiustato?

Metodologia
Gli autori non eseguono un benchmark testa a testa di sistemi esistenti. Al contrario, costruiscono un harness a recall accoppiato (matched-recall) per caratterizzare il trade-off tra costi di manutenzione e di ricostruzione. I componenti metodologici chiave includono:

• Protocollo Matched-Recall: Diversamente dai benchmark che fissano un controllo di costo (es. budget di probe $b$) e misurano il recall, questo protocollo fissa un pavimento di recall (0.90) e misura il budget di probe minimo ($b_{needed}$) e la latenza necessari per raggiungerlo. Ciò isola il costo della manutenzione dall'effetto confondente del cambiamento di copertura (es. lo splitting delle partizioni riduce la massa coperta da un $b$ fisso).
• Generatori di Carichi di Lavoro: Lo studio utilizza assi di drift parametrizzati:
  • Turnover ($\tau$): Frazione del set live sostituita.
  • Tasso di Aggiornamento ($u$): Rapporto tra aggiornamenti e query.
  • Correlazione ($\rho$): Disaccoppiamento del drift dei dati dal drift delle query.
  • Finestra Limitata (Bounded Window): Una modalità in cui la cardinalità rimane costante mentre la distribuzione ruota, isolando il drift dagli effetti di scala.
• Ground Truth Condiviso: Un ground truth esatto basato su chiavi di contenuto viene calcolato una sola volta per checkpoint e condiviso tra tutti i bracci sperimentali (statico, split/merge, recluster, rebuild) per garantire un confronto equo.
• Kill-Gates Pre-Registrati: Lo studio impiega una sequenza di criteri falsificabili per evitare di "salvare" un'ipotesi. Se un'ipotesi (es. "graph-in-leaf è un vantaggio statico") fallisce un gate, il lavoro devia invece di regolare i parametri per forzare un risultato positivo.
• Bracci Testati:
  • Statico (C0): Nessuna manutenzione, cancellazioni tramite tombstone.
  • Varianti di Manutenzione: Split/merge innescati dal drift, split innescati dalla cardinalità e re-centramento incrementale.
  • Riferimento (R): Un recluster completo nell'architettura (ricostruzione da zero) che funge da baseline di qualità.
  • Controllo Esterno: L'artefatto reale di Quake (OSDI'25) è stato eseguito sullo stesso trace per la validazione esterna.

Risultati Chiave

1. Sufficienza Statica in Drift Moderato:
   Su dataset con crescita/turnover moderati (SIFT1M, GIST1M), una partizione statica con cancellazioni tramite tombstone mantiene il pavimento di recall 0.90 con lo stesso budget di probe delle varianti mantenute. La manutenzione attiva è inutile in questo regime; lo "slack" nel budget di probe assorbe il drift.

2. Graph-in-Leaf non è un vantaggio statico:
   L'indice ibrido graph-in-leaf (che motiva il lavoro originale) è Pareto-dominato da un HNSW piatto sulla frontiera statica recall–QPS. Non offre alcun vantaggio di ricerca statica, solo un tempo di build più veloce.

3. Il Confine del Regime (Rotating Drift):
   Su un vero scenario di finestra rotante a scala controllata (MS-Turing-10M), una partizione statica degrada materialmente. Il suo budget di probe richiesto ($b_{needed}$) sale da 64 a 112+ man mano che la distribuzione ruota. In questo regime, il re-centramento è realmente necessario.

4. Re-centramento Incrementale vs. Full Rebuild:
   Nel regime di rotating drift, un re-centramento incrementale economico eguaglia la qualità del recall di un recluster completo (identico $b_{needed}$) a circa 1/6 del costo di rigenerazione.

   • Total Cost of Ownership (TCO): In carichi di lavoro realistici e intensivi di query, il re-centramento incrementale e il full rebuild sono TCO-equivalenti. Il re-centramento incrementale vince rigorosamente solo in carichi di lavoro intensivi di update.
   • Nessun Crossover a favore del Rebuild: Il paper smentisce una precedente affermazione di un punto di crossover ($u^* \approx 4.7$) in cui i full rebuild diventano superiori, identificandolo come un artefatto dell'attribuzione della latenza di build fresca a indici obsoleti e del drift temporale sequenziale.

5. Validazione Esterna (Quake):
   L'esecuzione del sistema reale Quake sullo stesso trace ha confermato il confine del regime: Quake mantiene il pavimento di recall con una frazione di scansione limitata. Tuttavia, la sua politica predefinita basata sulla dimensione ha frammentato l'indice (aumentando $nlist$ di 13 volte), incorrendo in alti costi di manutenzione, mentre un re-centramento controllato manteneva un budget ridotto a basso costo.

Contributi

1. Un Benchmark Controllato: Un workload di drift parametrizzato e un harness con un protocollo a recall accoppiato, che disaccoppia il drift di dati/query e fornisce un ground truth per regione.
2. Una Mappa dei Regimi: Una caratterizzazione che distingue tra regimi "staticamente sufficienti" (crescita/turnover moderati) e regimi "dove il re-centramento aiuta" (rotating drift).
3. Una Regola Decisionale: Una guida pratica per i professionisti:
   • Crescita Moderata: Resta statico; usa cancellazioni tramite tombstone e un budget di probe leggermente più ampio.
   • Rotating Drift: Re-centra, ma usa il re-centramento incrementale invece del full rebuild.
   • Scelta del Trigger: I trigger basati sul drift vs quelli basati sulla cardinalità non mostrano differenze di recall; scegli in base alla convenienza ingegneristica.
4. Framework Esplicativo: Un modello di "slack del budget di probe" ($\sigma < b$) che spiega quando il drift è assorbibile rispetto a quando forza la ri-partizione.
5. Risultati Negativi Onesti: Correzioni di affermazioni eccessive nel campo, specificamente che il graph-in-leaf non è un vantaggio statico e che lo splitting/merging senza re-centramento frammenta semplicemente l'indice invece di ridurre il drift.

Significatività e Rivendicazioni
Il paper rivendica come contributo primario una mappa dei regimi e una regola decisionale, non un nuovo algoritmo di manutenzione. Argomenta che la premessa "il drift necessita di ri-partizione attiva" è condizionale.

• Nel regime di slack (drift moderato), la manutenzione non è una necessità di correttezza; è un trade-off di costo che è spesso non necessario.
• Nel regime forzato (rotating drift), la manutenzione è necessaria, ma un full rebuild periodico è evitabile. Il re-centramento incrementale raggiunge la stessa qualità di recall di un full rebuild a una frazione del costo di rigenerazione.
• Il paper sottolinea che il protocollo a matched-recall e a contenzione controllata è significativo quanto i risultati stessi, poiché evita gli errori confondenti (es. confronti a budget fisso) che hanno portato in precedenza a conclusioni errate sulla necessità e sul costo della manutenzione.

Gli autori dichiarano esplicitamente di non pretendere di aver risolto tutti i modi di drift (ad esempio, il drift di pura scomparsa o i trace di puro query drift non sono coperti) e che le loro scoperte sono limitate alla specifica famiglia di indici (router k-means con foglie HNSW/flat) e ai livelli di drift testati.