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

Technisches Resümee: Wann benötigt ein partitionierter ANN-Index unter Drift eine aktive Repartitionierung?

Problemstellung
Approximative Nearest-Neighbor-Indizes (ANN) dienen zunehmend nicht-stationären Korpora, bei denen die Datenverteilungen durch kontinuierliche Einfügungen, Löschungen und Modell-Updates variieren. Eine vorherrschende Prämisse in der Systemforschung (z. B. Quake, Ada-IVF, GTI, CrackIVF, SPFresh, DeDrift) besagt, dass statische Partitionen unter Daten-Drift veralten, was zu einem Recall-Kollaps führt, sofern der Index nicht aktiv repartitioniert wird (mittels Splitting, Merging, Reklustern oder Cracking). Dieses Paper stellt die Universalität dieser Prämisse in Frage und fragt: Unter welchen spezifischen Drift-Bedingungen ist eine aktive Repartitionierung tatsächlich notwendig, und wann kann der Drift durch einen statischen Index mit einem leicht angepassten Probe-Budget absorbiert werden?

Methodik
Die Autoren führen keinen Head-to-Head-Benchmark bestehender Systeme durch. Stattdessen konstruieren sie eine kontrollierte, Match-Recall-Harness, um den Trade-off zwischen Wartungs- und Rebuild-Kosten zu charakterisieren. Die wesentlichen methodischen Komponenten umfassen:

• Matched-Recall-Protokoll: Im Gegensatz zu Benchmarks, die einen Kostenknopf (z. B. Probe-Budget $b$) fixieren und den Recall messen, fixiert dieses Protokoll eine Recall-Untergrenze (0.90) und misst das erforderliche minimale Probe-Budget ($b_{needed}$) sowie die benötigte Latenz, um diese zu erreichen. Dies isoliert die Wartungskosten vom konfundierenden Effekt sich ändernder Abdeckung (z. B. reduziert das Splitten von Partitionen die durch ein festes $b$ abgedeckte Masse).
• Workload-Generatoren: Die Studie verwendet parametrisierte Drift-Achsen:
  • Turnover ($\tau$): Anteil des Live-Sets, der ersetzt wird.
  • Update-Rate ($u$): Verhältnis von Updates zu Queries.
  • Korrelation ($\rho$): Entkopplung von Daten-Drift und Query-Drift.
  • Bounded Window: Ein Modus, bei dem die Kardinalität konstant bleibt, während die Verteilung rotiert, wodurch Drift von Skalierungseffekten isoliert wird.
• Gemeinsame Ground Truth: Eine inhalts-gekeyte exakte Ground Truth wird einmal pro Checkpoint berechnet und über alle experimentellen Arme (statisch, split/merge, recluster, rebuild) geteilt, um einen fairen Vergleich zu gewährleisten.
• Pre-Registered Kill-Gates: Die Studie verwendet eine Sequenz falsifizierbarer Kriterien, um das „Retten“ einer Hypothese zu verhindern. Wenn eine Hypothese (z. B. „Graph-in-Leaf ist ein statischer Gewinn“) eine Gate durchläuft, wechselt die Arbeit die Richtung, anstatt Parameter anzupassen, um ein positives Ergebnis zu erzwingen.
• Getestete Arme:
  • Statisch (C0): Keine Wartung, Tombstone-Löschungen.
  • Wartungsvarianten: Drift-getriggertes Split/Merge, Kardinalitäts-getriggertes Split und inkrementelles Re-Centering.
  • Referenz (R): Ein in-Architektur Full-Recluster (Rebuild von Grund auf), der als Qualitäts-Baseline dient.
  • Externer Check: Das reale Quake-Artefakt (OSDI'25) wurde auf demselben Trace zur externen Validierung ausgeführt.

Wesentliche Ergebnisse

1. Statische Suffizienz bei moderatem Drift:
   Bei Datensätzen mit moderatem Wachstum/Turnover (SIFT1M, GIST1M) hält eine statische Partition mit Tombstone-Löschungen die 0.90 Recall-Untergrenze mit demselben Probe-Budget wie die gewarteten Varianten aufrecht. Aktive Wartung ist in diesem Regime unnötig; der „Slack“ im Probe-Budget absorbiert den Drift.

2. Graph-in-Leaf ist kein statischer Gewinn:
   Der Graph-in-Leaf Hybrid-Index (der die ursprüngliche Arbeit motiviert) wird auf der statischen Recall–QPS-Front Pareto-dominiert von flachem HNSW. Er bietet keinen Vorteil bei der statischen Suche, sondern lediglich eine schnellere Build-Zeit.

3. Die Regime-Grenze (Rotierender Drift):
   Auf einem realen, skalen-kontrollierten rotierenden Fenster (MS-Turing-10M) verschlechtert sich eine statische Partition materiell. Ihr erforderliches Probe-Budget ($b_{needed}$) steigt von 64 auf 112+ an, während die Verteilung rotiert. In diesem Regime ist Re-Centering tatsächlich erforderlich.

4. Inkrementelles Re-Centering vs. Full Rebuild:
   Im rotierenden Drift-Regime erreicht günstiges inkrementelles Re-Centering die gleiche Recall-Qualität wie ein Full Recluster (identisches $b_{needed}$) bei etwa einem Sechstel der Regenerationskosten.

   • Total Cost of Ownership (TCO): In realistischen, query-intensiven Workloads sind inkrementelles Re-Centering und Full Rebuilds TCO-äquivalent. In update-intensiven Workloads gewinnt inkrementelles Re-Centering strikt.
   • Kein Rebuild-bevorzugender Crossover: Das Paper widerlegt eine frühere Behauptung eines Crossover-Punktes ($u^* \approx 4.7$), an dem Full Rebuilds überlegen werden, und identifiziert diesen als Artefakt der Zuschreibung von Fresh-Build-Latenz zu stale Indizes und sequenzieller Timing-Drift.

5. Externe Validierung (Quake):
   Die Ausführung des realen Quake-Systems auf demselben Trace bestätigte die Regime-Grenze: Quake hält die Recall-Untergrenze bei einem begrenzten Scan-Anteil. Jedoch fragmentierte seine standardmäßige größengetriggerte Policy den Index (erhöhte $nlist$ um das 13-fache), was hohe Wartungskosten verursachte, während kontrolliertes Re-Centering ein kleines Budget günstig hielt.

Beiträge

1. Ein kontrollierter Benchmark: Ein parametrisierter Drift-Workload und eine Harness mit einem Matched-Recall-Protokoll, das Daten-/Query-Drift entkoppelt und pro Region eine Ground Truth bereitstellt.
2. Eine Regime-Map: Eine Charakterisierung, die zwischen „statisch-ausreichenden“ Regimen (moderates Wachstum/Turnover) und „Re-Centering-hilft“-Regimen (rotierender Drift) unterscheidet.
3. Eine Entscheidungsregel: Ein praktischer Leitfaden für Praktiker:
   • Moderates Wachstum: Bleiben Sie statisch; nutzen Sie Tombstone-Löschungen und ein etwas größeres Probe-Budget.
   • Rotierender Drift: Re-Centern Sie, aber nutzen Sie inkrementelles Re-Centering statt Full Rebuild.
   • Trigger-Wahl: Drift-basierte vs. Kardinalitäts-basierte Trigger zeigen keinen Recall-Unterschied; wählen Sie basierend auf der technischen Handhabung.
4. Ein erklärendes Modell: Ein „Probe-Budget-Slack“-Modell ($\sigma < b$), das erklärt, wann Staleness absorbierbar ist versus wann sie eine Repartitionierung erzwingt.
5. Ehrliche negative Ergebnisse: Korrekturen von Übertreibungen im Feld, spezifisch dass Graph-in-Leaf kein statischer Gewinn ist und dass Split/Merge ohne Re-Centering den Index lediglich fragmentiert, anstatt die Staleness zu reduzieren.

Bedeutung und Ansprüche
Das Paper beansprucht als primären Beitrag eine Regime-Map und Entscheidungsregel, nicht einen neuen Wartungsalgorithmus. Es argumentiert, dass die Prämisse „Drift erfordert aktive Repartitionierung“ konditional ist.

• Im Slack-Regime (moderater Drift) ist Wartung keine Korrektheitsnotwendigkeit, sondern ein Kosten-Trade-off, der oft unnötig ist.
• Im Forced-Regime (rotierender Drift) ist Wartung notwendig, aber ein vollständiger periodischer Rebuild ist vermeidbar. Inkrementelles Re-Centering erreicht die gleiche Recall-Qualität wie ein Full Rebuild zu einem Bruchteil der Regenerationskosten.
  Das Paper betont, dass das Matched-Recall-, Contention-kontrollierte Protokoll ebenso signifikant ist wie die Ergebnisse selbst, da es die konfundierenden Fehler (z. B. Fixed-Budget-Vergleiche) verhindert, die zuvor zu falschen Schlussfolgerungen über die Notwendigkeit und Kosten der Wartung führten.

Die Autoren erklären explizit, dass sie nicht behaupten, alle Drift-Modi (z. B. reiner Verschwindens-Drift oder echte Query-Drift-Traces) gelöst zu haben, und dass ihre Ergebnisse auf die spezifische Indizien-Familie (k-means Router mit HNSW/Flat Leaves) und die getesteten Drift-Magnituden beschränkt sind.