HNSW: Yaklaşık En Yakın Komşu Araması
HNSW, vektörleri çok katmanlı bir grafa yerleştirip arama sırasında yalnızca en yakın komşulara ilerleyerek tüm veri taramasından kaçınır; bu, milyonlarca vektörde bile milisaniyelere düşen arama süreleri sağlar.
Arama problemi
Gömme vektörleri, anlamsal benzerliği uzaysal yakınlığa dönüştürüyor. Bu, anlamsal arama sorununu bir yakınlık araması problemine çeviriyor.
En doğru sonuç, tüm vektörleri karşılaştıran tarama ile bulunur. Ancak bu, veri hacmi arttıkça pratik olarak uygulanamaz hâle geliyor.
Graf yaklaşımı
HNSW, vektörleri bir grafa yerleştiriyor. Her düğüm, birkaç yakın komşusuyla bağlantılı ve birden çok katmana dağıtılıyor.
Üst katmanlar seyrek ve geniş bağlantılara, alt katmanlar ise daha yoğun ve yerel bağlantılara sahip. Bu, arama sırasında farklı ölçeklerde gezinmeyi mümkün kılıyor.
Arama süreci
Arama, en üst katmanda başlıyor ve bir komşuya ilerleyip mesafe iyileştiğinde duruyor. Bu, yaklaşık bir sonuç veriyor ancak çok hızlı.
Ardından bir alt katmana iniliyor ve burada daha kapsamlı bir arama yapılıyor. Katmanlar tek tek inildikçe arama hassasiyeti artıyor.
Hız ve bellek dengesi
İndeksin kalitesi, kullanılan bağlantı sayısı ve katman yapısıyla belirleniyor. Daha fazla bağlantı daha iyi sonuç verir ancak bellek ve derleme maliyetini artırır.
Kullanıcı, arama kalitesi ile hız arasında bir denge seçmek zorunda. Farklı kullanım senaryoları farklı ayarlar gerektiriyor.
Alternatifler
İndeksle birlükte kuantizasyon uygulamak, bellek kullanımını belirgin biçimde azaltabiliyor. Bu, maliyet duyarlı kurulumlar için önemli bir seçenek.
Bazı sistemler, indeks ile tarama yöntemlerini birlikte kullanarak karma bir strateji kuruyor. Bu, sorgu tipine göre en uygun yöntemi seçmeyi hedefliyor.
- Tüm vektörleri taramak veri hacmiyle birlikte pratik olmaktan çıkıyor
- HNSW vektörleri hiyerarşik bir komşuluk grafına yerleştiriyor
- Arama üst katmandan başlayıp katman katman hassasiyet kazanıyor
- Bağlantı sayısı arama kalitesi ile bellek maliyeti arasında denge kuruyor
Sık sorulan sorular
HNSW tam olarak nedir?
Vektörleri çok katmanlı bir komşuluk grafına yerleştiren ve arama sırasında yalnızca en yakın komşulara ilerleyen yaklaşık en yakın komşu arama indeksidir. Bu sayede tüm veri taramasından kaçınılır.
Neden katmanlar kullanılıyor?
Üst katmanlar geniş ve seyrek bağlantılara, alt katmanlar daha yoğun ve yerel bağlantılara sahiptir. Bu, arama sırasında farklı ölçeklerde gezinmeyi ve doğru bölgeye hızlıca ulaşmayı mümkün kılıyor.
Arama kalitesi nasıl ayarlanıyor?
Graf bağlantı sayısı ve katman yapısıyla belirleniyor. Daha fazla bağlantı daha iyi sonuç verir ancak bellek ve derleme maliyetini artırır. Kullanıcı bu dengeyi seçmek zorunda.
Tüm vektörleri taramak neden sorun?
Bu, kesin sonucu verir ancak veri hacmi arttıkça pratik olmaktan çıkar. Milyonlarca vektörde tam tarama, arama süresini pratik olmayan seviyelere çıkarır.
Kaynakça
- HNSW: Hierarchical Navigable Small World GraphsarXiv
- Yaklaşık en yakın komşu aramasıWikipedia
- Vektör veritabanıWikipedia
- Gömme (makine öğrenmesi)Wikipedia
- Benzerlik aramasıWikipedia
