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

Technische Samenvatting: Wanneer heeft een gepartitioneerde ANN-index actieve herpartitionering nodig onder drift?

Probleemstelling
Benaderende nearest neighbor (ANN) indexen dienen steeds vaker voor niet-stationaire corpora waarbij datadistributies verschuiven door continue invoegingen, verwijderingen en modelupdates. Een heersend uitgangspunt in systeemonderzoek (bijv. Quake, Ada-IVF, GTI, CrackIVF, SPfresh, DeDrift) stelt dat statische partities verouderen onder datadrift, wat leidt tot een instorting van de recall tenzij de index actief wordt herpartitioneerd (via splitsen, samenvoegen, herclusteren of 'cracking'). Dit artikel daagt de universaliteit van dit uitgangspunt uit door de vraag te stellen: onder welke specifieke omstandigheden van drift is actieve herpartitionering daadwerkelijk noodzakelijk, versus wanneer kan de drift worden geabsorbeerd door een statische index met een licht aangepast probe-budget?

Methodologie
De auteurs voeren geen head-to-head benchmark uit van bestaande systemen. In plaats daarvan construeren zij een gecontroleerde, gematchte-recall harness om de afweging tussen onderhouds- en herbouwkosten te karakteriseren. Belangrijke methodologische componenten zijn:

• Matched-Recall Protocol: In tegenstelling tot benchmarks die een kostenknop vastleggen (bijv. probe-budget $b$) en de recall meten, legt dit protocol een recall-vloer vast (0.90) en meet het het minimale probe-budget ($b_{needed}$) en de benodigde latentie om dit te bereiken. Dit isoleert de kosten van onderhoud van het verwarrende effect van veranderende dekking (bijv. het splitsen van partities vermindert de massa die door een vaste $b$ wordt gedekt).
• Workload Generatoren: De studie gebruikt geparametriseerde drift-assen:
  • Turnover ($\tau$): Fractie van de actieve set die wordt vervangen.
  • Update Rate ($u$): Ratio van updates ten opzichte van queries.
  • Correlatie ($\rho$): Ontkoppeling van datadrift van query-drift.
  • Bounded Window: Een modus waarbij de cardinaliteit constant blijft terwijl de distributie roteert, waardoor drift wordt geïsoleerd van schaal-effecten.
• Gedeelde Grondwaarheid: Een op content gebaseerde exacte grondwaarheid wordt één keer per checkpoint berekend en gedeeld over alle experimentele armen (statisch, split/merge, recluster, rebuild) om een eerlijke vergelijking te garanderen.
• Pre-Registered Kill-Gates: De studie hanteert een sequentie van falsifieerbare criteria om het "redden" van een hypothese te voorkomen. Als een hypothese (bijv. "graph-in-leaf is een statische winst") een gate faalt, verschuift het werk naar een nieuw pad in plaats van parameters aan te passen om een positief resultaat te forceren.
• Geteste Armen:
  • Statisch (C0): Geen onderhoud, tombstone-verwijderingen.
  • Onderhoudsvarianten: Drift-getriggerde split/merge, cardinaliteit-getriggerde split, en incrementele her-centrering.
  • Referentie (R): Een in-architectuur volledige recluster (herbouw vanaf nul) die dient als kwaliteitsbaseline.
  • Externe Controle: Het echte Quake-artefact (OSDI'25) werd op dezelfde trace gedraaid voor externe validatie.

Belangrijkste Resultaten

1. Statische Voldoenheid bij Matige Drift:
   Op datasets met matige groei/turnover (SIFT1M, GIST1M) behoudt een statische partitie met tombstone-verwijderingen de 0.90 recall-vloer bij hetzelfde probe-budget als de onderhouden varianten. Actief onderhoud is onnodig in dit regime; de "slack" in het probe-budget absorbeert de drift.

2. Graph-in-Leaf is Geen Statische Winst:
   De graph-in-leaf hybride index (die het oorspronkelijke werk motiveert) wordt Pareto-gedomineerd door flat HNSW op de statische recall–QPS-frontier. Het biedt geen voordeel voor statisch zoeken, alleen een snellere bouwtijd.

3. De Regime-grens (Roterende Drift):
   Op een echte, schaal-gecontroleerde roterende window (MS-Turing-10M), degradeert een statische partitie materieel. Het vereiste probe-budget ($b_{needed}$) stijgt van 64 naar 112+ naarmate de distributie roteert. In dit regime is her-centrering daadwerkelijk vereist.

4. Incrementele Her-centrering vs. Volledige Herbouw:
   In het roterende drift-regime evenaart goedkope incrementele her-centrering de recall-kwaliteit van een volledige recluster (identieke $b_{needed}$) tegen ongeveer 1/6e van de regeneratiekosten.

   • Total Cost of Ownership (TCO): In realistische, query-zware workloads zijn incrementele her-centrering en volledige herbouw TCO-equivalent. Incrementele her-centrering wint strikt alleen in update-zware workloads.
   • Geen Crossover die Herbouw Bevoordeelt: Het artikel weerlegt een eerdere claim van een crossoverpunt ($u^* \approx 4.7$) waar volledige herbouw superieur wordt, door te wijzen op een artefact veroorzaakt door het toeschrijven van de latency van een verse build aan verouderde indexen en sequentiële timing-drift.

5. Externe Validatie (Quake):
   Het draaien van het echte Quake-systeem op dezelfde trace bevestigde de regime-grens: Quake behoudt de recall-vloer bij een begrensde scan-fractie. Echter, het standaard grootte-getriggerde beleid fragmenteerde de index (verhoogde $nlist$ met 13x), wat hoge onderhoudskosten met zich meebracht, terwijl gecontroleerde her-centrering een klein budget goedkoop in stand hield.

Bijdragen

1. Een Gecontroleerde Benchmark: Een geparametriseerde drift-workload en harness met een gematchte-recall protocol, dat data/query-drift ontkoppelt en per regio grondwaarheid biedt.
2. Een Regime-kaart: Een karakterisering die "statisch-voldoende" regimes (matige groei/turnover) onderscheidt van "her-centrering-helpt" regimes (roterende drift).
3. Een Beslisregel: Een praktische gids voor practitioners:
   • Matige Groei: Blijf statisch; gebruik tombstone-verwijderingen en een iets groter probe-budget.
   • Roterende Drift: Her-centreer, maar gebruik incrementele her-centrering in plaats van een volledige herbouw.
   • Trigger Keuze: Drift-gebaseerde versus cardinaliteit-gebaseerde triggers vertonen geen verschil in recall; kies op basis van engineering-gemak.
4. Een Verklarend Kader: Een "probe-budget slack" model ($\sigma < b$) dat verklaart wanneer veroudering absorbeerbaar is versus wanneer het herpartitionering dwingt.
5. Eerlijke Negatieve Resultaten: Correcties van overclaims in het veld, specifiek dat graph-in-leaf geen statische winst is en dat split/merge zonder her-centrering de index slechts fragmenteert in plaats van de veroudering te verminderen.

Betekenis en Claims
Het artikel claimt dat de primaire bijdrage een regime-kaart en beslisregel is, en geen nieuw onderhoudsalgoritme. Het betoogt dat de premisse "drift vereist actieve herpartitionering" conditioneel is.

• In het slack-regime (matige drift) is onderhoud geen correctheidsnoodzaak; het is een kostenafweging die vaak onnodig is.
• In het forced regime (roterende drift) is onderhoud noodzakelijk, maar is een volledige periodieke herbouw te vermijden. Incrementele her-centrering bereikt dezelfde recall-kwaliteit als een volledige herbouw tegen een fractie van de regeneratiekosten.
• Het artikel benadrukt dat het gematchte-recall, contention-gecontroleerde protocol net zo significant is als de resultaten, omdat het de verwarrende fouten (zoals fixed-budget vergelijkingen) voorkomt die eerder leidden tot onjuiste conclusies over de noodzaak en kosten van onderhoud.

De auteurs verklaren expliciet dat zij niet beweren alle drift-modi te hebben opgelost (bijv. zuivere verdwijnings-drift of echte query-drift traces zijn niet gedekt) en dat hun bevindingen beperkt zijn tot de specifieke indexfamilie (k-means router met HNSW/flat leaves) en de geteste magnitudes van drift.