IAli
Tüm Yazılar
HNSW Graf Mimarisi ile Yüksek Boyutlu Vektör Uzayında Hızlı Arama

HNSW Graf Mimarisi ile Yüksek Boyutlu Vektör Uzayında Hızlı Arama

Vektör veritabanlarında HNSW hiyerarşik küçük dünya graf mimarisi, yaklaşık en yakın komşu (ANN) araması, efConstruction parametresi ve analizi.

Büyük Dil Modelleri (LLM), anlamsal arama ve öneri sistemleri metinleri, görselleri ve kullanıcı profillerini yüzlerce veya binlerce boyuttan oluşan yoğun gömme vektörlerine (dense embedding vectors) dönüştürür. 1536 boyutlu bir vektör uzayında kullanıcı sorgusuna en yakın vektörü bulmak için kaba kuvvet (exact k-NN) yaklaşımı milyonlarca vektör arasında mesafe hesaplamayı gerektirir ve saniyeler sürer. Vektör veritabanlarının (pgvector, Pinecone, Milvus, Qdrant) kalbinde yer alan Hiyerarşik Gezilebilir Küçük Dünya (Hierarchical Navigable Small World - HNSW) graf mimarisi, yaklaşık en yakın komşu (ANN) aramasını logaritmik karmaşıklığa indirerek milisaniyelik yanıtlar üretir.

Kapsam Notu: Bu teknik analiz Malkov ve Yashunin'in 2016 HNSW algoritması, pgvector uygulaması ve vektör graf indeksleme parametreleri dikkate alınarak hazırlanmıştır.

Küçük Dünya (Small World) Grafları ve Skip-List Analojisi

HNSW mimarisini kavramak için tek boyutlu bağlı listeleri hızlandıran Skip-List veri yapısını hatırlamak gerekir. Skip-List'te üst katmanlar seyrek elemanlar içerir ve arama sırasında büyük adımlarla hedefe yaklaşmayı sağlar.

Yura Malkov ve Dmitry Yashunin bu fikri çok boyutlu metrik uzaylara uyarlayarak çok katmanlı bir graf hiyerarşisi inşa etmiştir:

TEXT
Katman 2 (Seyrek Graf):    [Düğüm A] ---------------------------> [Düğüm B]
                               |                                      |
Katman 1 (Orta Graf)  :    [Düğüm A] ------------> [Düğüm C] ---> [Düğüm B]
                               |                       |              |
Katman 0 (Taban Graf) :    [Düğüm A] <-> [Düğüm D] <-> [Düğüm C] <-> [Düğüm B]
                            (Tüm veri noktaları burada yoğun bağlıdır)
  1. Katman 2 (Üst Katmanlar): Çok az sayıda düğüm ve uzun mesafeli bağlantılar içerir. Uzayda otoyol görevi görür.
  2. Katman 0 (Zemin Katman): Kümedeki tüm vektörleri barındırır ve yalnızca yakın komşuluk bağlantılarına sahiptir. Yerel sokak haritası gibidir.

Arama Algoritması: Açgözlü Arama (Greedy Routing)

Bir sorgu vektörü ($q$) geldiğinde arama işlemi en üst katmandaki giriş noktasından (entry point) başlar:

  1. Açgözlü Gezinme: Algoritma mevcut düğümün komşularını inceler. Sorgu vektörüne mevcut düğümden daha yakın bir komşu bulduğu sürece o yöne doğru sıçrar.
  2. Yerel Minimuma Ulaşma: Mevcut katmanda sorguya daha yakın bir komşu kalmadığında bir alt katmana inilir.
  3. Taban Katmanda İnce Arama: En alt katmanda (Katman 0) belirlenen aday havuzu (efSearch) genişliğinde taranarak en yakın K adet komşu tespit edilir.

Bu çok katmanlı sıçrama mekanizması arama karmaşıklığını $O(N)$ seviyesinden $O(\log N)$ seviyesine düşürür.

HNSW İnşa Parametreleri: M, efConstruction ve efSearch

HNSW grafının bellek tüketimini ve arama doğruluğunu (recall) belirleyen üç kritik parametre vardır:

1. M (Maksimum Komşu Sayısı)

Her bir düğümün bağlanabileceği maksimum kenar sayısıdır (Katman 0 için genellikle $2M$ kullanılır).

  • Tipik Değerler: 16, 32 veya 64.
  • M arttıkça graf bağlantıları güçlenir, yüksek boyutlu uzaylarda doğruluk artar. Ancak bellek tüketimi ve indeks inşa süresi katlanır.

2. efConstruction (İnşa Sırasındaki Aday Havuzu Boyutu)

Yeni bir vektör grafa eklenirken en uygun komşuları bulmak için taranan dinamik listenin boyutudur.

  • Tipik Değerler: 64, 128, 200.
  • Yüksek değerler daha kusursuz bir graf örgüsü kurar ve arama başarısını artırır. İndeksleme süresini uzatır.

3. efSearch (Sorgu Sırasındaki Dinamik Liste Boyutu)

Sorgu anında bellekte tutulan en yakın adayların sayısıdır.

  • Tipik Değerler: 40, 100.
  • efSearch arttıkça sorgunun doğru komşuları bulma oranı (%99 recall) yükselir ancak sorgu gecikmesi (latency) birkaç milisaniye artar.
SQL
-- pgvector üzerinde HNSW indeksi oluşturma
CREATE INDEX idx_belgeler_vektor ON belgeler
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 128)

Bellek Duvarı (RAM Tüketimi)

HNSW graf mimarisinin en büyük bedeli bellek açlığıdır. Standart B-Tree veya ters dizinlerin aksine HNSW grafının yüksek verimle çalışması için tüm graf düğümlerinin ve kenar işaretçilerinin RAM üzerinde yaşaması gerekir.

1 milyon adet 1536 boyutlu float32 vektör yaklaşık 6 GB ham veri tutarken, HNSW graf bağlantıları ile birlikte indeks boyutu 10 ila 15 GB RAM gerektirebilir. Bellek yetersiz kaldığında ve graf sayfaları disk takasına (swap) düştüğünde arama süresi mikrosaniyelerden saniyelere fırlar.

Yazıyı Değerlendir

0 tepki

Fikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.

Bu teknik notu çevrenizle paylaşın

Ali Purtaş

@alipurtas • Hey, This is Ali!

İletişime Geç

Kendi halinde yazılım geliştiren bir öğrenci. Sistemler kuruyor, deniyor, bozuyor ve öğrendiği gerçek çözümleri burada belgeliyor.

Konu Kümesi & Önerilen Yazılar

İç Bağlantılı Mimari
Yorumlar yükleniyor...