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

Resumo Técnico: Quando um Índice ANN Particionado Precisa de Reparticionamento Ativo sob Drift?

Definição do Problema
Índices de vizinhos mais próximos aproximados (ANN) servem cada vez mais corpora não estacionários, onde as distribuições de dados sofrem mudanças devido a inserções contínuas, deleções e atualizações de modelos. Uma premissa prevalente na pesquisa de sistemas (ex: Quake, Ada-IVF, GTI, CrackIVF, SPFresh, DeDrift) é que partições estáticas tornam-se obsoletas sob drift de dados, causando o colapso do recall (revocação), a menos que o índice seja ativamente reparticionado (via divisão, fusão, re-clusterização ou cracking). Este artigo desafia a universalidade dessa premissa, perguntando: sob quais condições específicas de drift o reparticionamento ativo é realmente necessário, versus quando o drift pode ser absorvido por um índice estático com um orçamento de sondagem (probe budget) ligeiramente ajustado?

Metodologia
Os autores não realizam um benchmark direto contra sistemas existentes. Em vez disso, constroem um harness de recall correspondente para caracterizar o equilíbrio entre custos de manutenção e de reconstrução. Os principais componentes metodológicos incluem:

• Protocolo de Recall Correspondente (Matched-Recall Protocol): Ao contrário de benchmarks que fixam um controle de custo (ex: orçamento de sondagem $b$) e medem o recall, este protocolo fixa um piso de recall (0.90) e mede o orçamento de sondagem mínimo ($b_{needed}$) e a latência necessária para alcançá-lo. Isso isola o custo da manutenção do efeito de confusão da mudança de cobertura (ex: dividir partições reduz a massa coberta por um $b$ fixo).
• Geradores de Carga de Trabalho: O estudo utiliza eixos de drift parametrizados:
  • Turnover ($\tau$): Fração do conjunto vivo substituído.
  • Taxa de Atualização ($u$): Razão entre atualizações e consultas.
  • Correlação ($\rho$): Desacoplamento do drift de dados do drift de consulta.
  • Janela Limitada (Bounded Window): Um modo onde a cardinalidade permanece constante enquanto a distribuição rotaciona, isolando o drift de efeitos de escala.
• Verdade Fundamental Compartilhada (Shared Ground Truth): Uma verdade fundamental exata baseada em chave de conteúdo é computada uma única vez por checkpoint e compartilhada entre todos os braços experimentais (estático, divisão/fusão, re-clusterização, reconstrução) para garantir uma comparação justa.
• Kill-Gates Pré-Registrados: O estudo emprega uma sequência de critérios falsificáveis para evitar o "resgate" de uma hipótese. Se uma hipótese (ex: "graph-in-leaf é uma vitória estática") falha em um gate, o trabalho pivota em vez de ajustar parâmetros para forçar um resultado positivo.
• Braços Testados:
  • Estático (C0): Sem manutenção, deleções via tombstone.
  • Variantes de Manutenção: Divisão/fusão disparada por drift, divisão disparada por cardinalidade e re-centralização incremental.
  • Referência (R): Um re-cluster completo dentro da arquitetura (reconstrução do zero) servindo como linha de base de qualidade.
  • Verificação Externa: O artefato real do Quake (OSDI'25) foi executado no mesmo traço para validação externa.

Resultados Principais

1. Suficiência Estática em Drift Moderado:
   Em conjuntos de dados com crescimento/turnover moderados (SIFT1M, GIST1M), uma partição estática com deleções tombstone mantém o piso de recall de 0.90 com o mesmo orçamento de sondagem das variantes mantidas. A manutenção ativa é desnecessária neste regime; a "folga" no orçamento de sondagem absorve o drift.

2. Graph-in-Leaf Não é uma Vitória Estática:
   O índice híbrido graph-in-leaf (que motiva o trabalho original) é Pareto-dominado pelo HNSW plano na fronteira de recall-QPS estática. Ele não oferece vantagem de busca estática, apenas um tempo de construção mais rápido.

3. A Fronteira do Regime (Drift Rotacional):
   Em um cenário de janela rotativa real e controlada por escala (MS-Turing-10M), uma partição estática degrada materialmente. Seu orçamento de sondagem necessário ($b_{needed}$) sobe de 64 para 112+ conforme a distribuição rotaciona. Neste regime, a re-centralização é genuinamente necessária para manter a eficiência.

4. Re-centralização Incremental vs. Reconstrução Completa:
   No regime de drift rotacional, a re-centralização incremental barata iguala a qualidade de recall de um re-cluster completo (idêntico $b_{needed}$) a aproximadamente 1/6 do custo de regeneração.

   • Custo Total de Propriedade (TCO): Em cargas de trabalho realistas e intensivas em consultas, a re-centralização incremental e as reconstruções completas são equivalentes em TCO. A re-centralização incremental vence estritamente apenas em cargas de trabalho intensivas em atualizações.
   • Não há Cruzamento Favorável à Reconstrução: O artigo refuta uma afirmação anterior de um ponto de cruzamento ($u^* \approx 4.7$) onde reconstruções completas se tornariam superiores, identificando-o como um artefato de creditar a latência de construção fresca a índices obsoletos e ao drift temporal sequencial.

5. Validação Externa (Quake):
   A execução do sistema real Quake no mesmo traço confirmou a fronteira do regime: o Quake mantém o piso de recall em uma fração de varredura limitada. No entanto, sua política padrão disparada por tamanho fragmentou o índice (aumentando o $nlist$ em 13x), incorrendo em altos custos de manutenção, enquanto a re-centralização controlada manteve um orçamento pequeno e barato.

Contribuições

1. Um Benchmark Controlado: Um harness de carga de trabalho de drift parametrizado e um protocolo de recall correspondente, desacoplando drift de dados/consulta e fornecendo ground truth por região.
2. Um Mapa de Regimes: Uma caracterização distinguindo entre regimes "estáticos-suficientes" (crescimento/turnover moderado) e regimes "onde-re-centralização-ajuda" (drift rotacional).
3. Uma Regra de Decisão: Um guia prático para profissionais:
   • Crescimento Moderado: Permaneça estático; use deleções tombstone e um orçamento de sondagem ligeiramente maior.
   • Drift Rotacional: Re-centralize, mas use re-centralização incremental em vez de reconstrução completa.
   • Escolha de Gatilho: Gatilhos baseados em drift vs. cardinalidade não mostram diferença de recall; escolha com base na conveniência de engenharia.
4. Modelo de "Folga de Orçamento de Sondagem" ($\sigma < b$): Explica quando a obsolescência é absorvível versus quando força o reparticionamento.
5. Resultados Negativos Honestos: Correções de alegações excessivas no campo, especificamente que o graph-in-leaf não é uma vitória estática e que a divisão/fusão sem re-centralização apenas fragmenta o índice em vez de reduzir a obsolescência.

Significância e Alegações
O artigo afirma que sua principal contribuição é um mapa de regime e uma regra de decisão, não um novo algoritmo de manutenção. Argumenta-se que a premissa "o drift exige reparticionamento ativo" é condicional.

• No regime de folga (drift moderado), a manutenção não é uma necessidade de correção; é um equilíbrio de custo que é frequentemente desnecessário.
• No regime forçado (drift rotacional), a manutenção é necessária, mas uma reconstrução periódica completa é evitável. A re-centralização incremental atinge a mesma qualidade de recall que uma reconstrução completa a uma fração do custo de regeneração.
• O artigo enfatiza que o protocolo de recall correspondente e de contenção de disputa é tão significativo quanto os resultados, pois evita os erros de confusão (ex: comparações de orçamento fixo) que levaram anteriormente a conclusões incorretas sobre a necessidade e o custo da manutenção.

Os autores declaram explicitamente que não pretendem resolver todos os modos de drift (ex: drift de desaparecimento puro ou traços de drift de consulta real não foram cobertos) e que suas descobertas são limitadas à família específica de índices (roteador k-means com folhas HNSW/flat) e às magnitudes de drift testadas.