DiskANN
Jak działa
Indeksowanie: (1) budowana jest graf Vamana — każdy węzeł to wektor, krawędzie łączą go z R wybranymi sąsiadami; budowa jest iteracyjna, z parametrem alpha (>1.0) decydującym o tym, jak agresywnie dodawane są długie „skróty" między odległymi klastrami. (2) Pełne wektory i listy sąsiedztwa zapisywane są na SSD w układzie zoptymalizowanym pod 4 KB strony, tak by jedna strona zawierała zarówno wektor węzła, jak i jego sąsiadów. (3) W RAM trzyma się skompresowane (Product Quantization) wersje wszystkich wektorów oraz mały „cache" węzłów wokół punktów wejścia. Zapytanie: (a) startuje z medoida grafu, (b) na każdym kroku odczytuje ze SSD listę sąsiadów aktualnego węzła i ich pełne wektory, ale kandydatów do rozszerzenia frontu wybiera się za pomocą tanich obliczeń PQ z RAM, (c) frontier jest utrzymywany w priority queue rozmiaru L (search list size), (d) wyszukiwanie kończy się gdy żaden z R najbliższych kandydatów nie poprawia odległości. Wariant FreshDiskANN dodaje warstwę „delta" w RAM dla świeżych wstawień i okresowo scala ją z indeksem na SSD, umożliwiając aktualizacje bez przebudowy całości.
Rozwiązany problem
Dokładne k-NN w przestrzeniach o setkach lub tysiącach wymiarów jest niewykonalne na zbiorach rzędu miliardów rekordów, a klasyczne ANN-grafy (HNSW) wymagają, by cały indeks zmieścił się w RAM, co dla 10⁹ wektorów oznacza setki GB do TB pamięci na pojedynczym węźle. DiskANN rozwiązuje ten problem ekonomiczny: pozwala uzyskać porównywalne recall i latency, trzymając indeks na dużo tańszym SSD i tylko niewielką część w RAM, dzięki czemu jeden serwer obsłuży miliardy wektorów zamiast całego klastra.
Komponenty
Skierowany graf sąsiedztwa o ustalonym maksymalnym stopniu R, budowany iteracyjnie z parametrem alpha sterującym długością skrótów między klastrami; przechowywany na SSD razem z wektorami.
Wszystkie wektory są kompresowane przez Product Quantization do kilkudziesięciu bajtów na wektor i trzymane w RAM, by szybko szacować odległości przy wyborze kandydatów do rozszerzenia frontu.
Oficjalna
Strony 4 KB pakują wektor węzła i jego listę sąsiadów razem, tak że jedno żądanie I/O zwraca wszystko, czego potrzebuje krok wyszukiwania.
Wyszukiwanie utrzymuje priority queue rozmiaru L (search list size) — większe L = wyższy recall, kosztem latency i większej liczby odczytów SSD.
Opcjonalna warstwa w RAM dla świeżych wstawień/usunięć, okresowo scalana z indeksem na SSD, umożliwia mutowalne kolekcje bez pełnej przebudowy.
Oficjalna
Implementacja
DiskANN jest zaprojektowany pod losowe odczyty 4 KB z bardzo niskim opóźnieniem. Na HDD lub wolnym SATA SSD latency wzrasta o 1–2 rzędy wielkości i algorytm przestaje być konkurencyjny.
L kontroluje rozmiar frontiera. Wartości <50 dramatycznie obniżają recall na trudnych zbiorach (>1M wektorów, wysoki D).
Klasyczny DiskANN jest semi-statyczny. Częste wstawienia/usunięcia bez warstwy delta (FreshDiskANN) prowadzą do degradacji jakości grafu i konieczności pełnej przebudowy.
Mimo że indeks jest „na dysku", PQ codebooks i wycinek frontiera muszą zmieścić się w RAM. Dla 1B wektorów × 64 B PQ to ~64 GB — nieoczywiste przy planowaniu sprzętu.
Pierwsze zapytania po starcie odczytują wszystko z SSD — p99 może być 5–10× wyższe niż w stanie ustalonym, dopóki cache stron systemu plików się nie nagrzeje.
Ewolucja
Microsoft Research prezentuje DiskANN i graf Vamana — pierwsze ANN dla miliarda wektorów na pojedynczym węźle z indeksem na SSD.
Rozszerzenie pozwala dodawać i usuwać wektory bez pełnej przebudowy indeksu, dzięki dwuwarstwowej architekturze RAM + SSD.
Implementacje DiskANN pojawiają się w Milvus oraz w usługach Microsoft Azure (Cosmos DB, Bing).
Microsoft ogłasza DiskANN jako domyślny silnik wektorowy dla Cosmos DB for MongoDB vCore — produkcyjne użycie na ogromnych zbiorach.
Hiperparametry (konfigurowalne osie)
Maksymalny stopień wyjściowy węzła w grafie Vamana. Większy R = wyższy recall, ale więcej miejsca na SSD i wolniejsza budowa.
Rozmiar priority queue podczas zapytania. Bezpośrednio kontroluje trade-off recall vs latency.
Parametr (>1.0) w pruningu krawędzi podczas budowy grafu — większe alpha = więcej długich „skrótów", krótsze ścieżki wyszukiwania.
Ile bajtów po Product Quantization przeznaczyć na jeden wektor w RAM. Kontroluje recall (większe = lepsze szacowanie odległości) vs zużycie RAM.
Złożoność obliczeniowa
Złożoność czasowa: O(log N) per query (empirical). Złożoność przestrzenna: RAM: O(N · b_PQ); SSD: O(N · (D · 4B + R · 4B)).
Wąskie gardło obliczeniowe
Każdy krok wyszukiwania to nowy losowy odczyt 4 KB ze SSD. Wydajność jest zdominowana przez IOPS dysku, nie przez CPU/RAM — stąd preferencja dla NVMe SSD.
Paradygmat wykonania
Tylko niewielki podzbiór węzłów grafu jest odwiedzany w trakcie pojedynczego zapytania — paradygmat „sparse exploration".
Równoległość
Każde zapytanie jest niezależne; throughput skaluje się liniowo z liczbą rdzeni CPU i liczbą równoczesnych operacji I/O obsługiwanych przez SSD.
Wymagania sprzętowe
Wyszukiwanie zdominowane przez kalkulacje dystansu PQ (small dot-products) i logikę grafu — idealne dla wektorowych instrukcji CPU (AVX2/AVX-512). GPU jest nieopłacalne ze względu na małe rozmiary batchów per zapytanie.
Implementacje DiskANN działają na ARM (Graviton, Apple Silicon) i x86. Krytyczny jest NVMe SSD i przepustowość pamięci, nie konkretna ISA.
Tensor Cores zaprojektowane pod gęste GEMM-y nie mają przewagi dla losowych odczytów i sparse traversal grafu. GPU może przyspieszyć fazę budowy indeksu, ale nie samo zapytanie.