Locality Sensitive Hashing (LSH)
Büyük veri kümelerinde benzer öğeleri hızlıca bulmak, geleneksel yöntemlerle oldukça zaman alabilir. Özellikle yüksek boyutlu verilerde "yakın komşu arama (nearest neighbor search)" işlemleri maliyetlidir. Locality Sensitive Hashing (LSH), bu problemi çözmek için kullanılan etkili ve pratik bir tekniktir.
Geleneksel hash fonksiyonları farklı girdiler için tamamen farklı çıktılar üretmeye çalışırken, LSH'de amaç tam tersidir: benzer öğelerin benzer hash çıktıları üretmesidir. Bu yaklaşım, veri uzayında "yakınlık" kavramını hash fonksiyonlarına entegre ederek, benzerlik aramayı hızlandırır.
Bir hash fonksiyonu ailesi $H = \{ h: \mathbb{R}^d \rightarrow U \}$, $(r, c \cdot r, p_1, p_2)$ parametreleriyle locality-sensitive (yerellik duyarlı) sayılabilmesi için şu iki matematiksel koşulu sağlamalıdır:
- Koşul 1 (Yakın Öğeler): Eğer iki öğe birbirine yakınsa, yani aralarındaki mesafe $d(x, y) \leq r$ ise, bu öğelerin aynı hash değerine sahip olma olasılığı en az $p_1$ olmalıdır:
$$ d(x, y) \leq r \implies P(h(x) = h(y)) \geq p_1 $$
- Koşul 2 (Uzak Öğeler): Eğer iki öğe birbirinden uzaksa, yani aralarındaki mesafe $d(x, y) > c \cdot r$ ise, bu öğelerin aynı hash değerine sahip olma olasılığı en fazla $p_2$ olmalıdır:
$$ d(x, y) > c \cdot r \implies P(h(x) = h(y)) \leq p_2 $$
Burada $c > 1$ bir sabittir ve $p_1 > p_2$ koşulu sağlanmalıdır.
Bu iki koşul sayesinde hash fonksiyonu ailesi, benzer (yakın) öğeleri aynı hash'e, farklı (uzak) öğeleri ise farklı hash'lere eşleme eğiliminde olur. Bu da benzerlik arama gibi uygulamalarda verimli sonuçlar alınmasını sağlar.
Bir sonraki yazıda görüşmek üzere.