Yüksek boyutlu vektörlerin dagıtık olarak yüksek performans ile aranması / Aykut Alparslan Koç ; thesis advisor Mehmet Burak Akgün.

Tez (Yüksek Lisans)--TOBB ETÜ Sosyal Bilimler Enstitüsü Şubat 2026.

Benzerlik araması ya da k-en yakın komşu araması veri tabanlarının çözmesi gereken önemli bir problem olarak karşımıza çıkmaktadır. Örüntü tanıma, semantik arama gibi çok çeşitli kullanım alanlarının olması problemi önemli kılan temel sebeptir. Bugün bu problemin çözümü için çok sayıda açık kaynaklı kütüphane ve vektör veri tabanı olarak tasarlanmış veri tabanı sistemi bulunmaktadır. Yaygın olarak kullanılan veri tabanı sistemlerine ise benzerlik araması yeteneğinin kazandırıldığı görülmeye başlanmıştır. Araştırmalar ilk başlarda problemi kesin bir doğrulukla çözmeye odaklanmış iken önerilen yöntemlerin 10-15 boyutlu vektörler söz konusu olduğunda dahi efektif olarak doğrusal bir aramaya eşdeğer olması sonraki araştırmaları problemi yaklaşık olarak çözmeye itmiştir. Nitekim bugün gösterim öğrenimi için kullanılan birçok yöntem 384 ya da 512 gibi çok yüksek boyutlu vektörler üretmektedir. Bu durum boyut sayısının laneti olarak da bilinen olgu sebebiyledir ve benzerlik araması yöntemleri bu olgudan etkilenirler. Önerilen yöntemler ağaç tabanlı, özet tabanlı, vektör nicelemesi tabanlı, ters dizin, ya da çizge tabanlıdır. Ağaç tabanlı yöntemler özellik uzayını ya da veriyi bölerler. Özet tabanlı yöntemler birden fazla özet fonksiyonu kullanarak birbirine yakın olan verilerin aynı kovalara düşmesini hedefler. Vektörler nicelendiğinde veri seti ana belleğe daha kolay sığmakta ve yapılacak işlem sayısı düştüğünden performans artışı sağlanmaktadır. Kümeleme yapıldığında sadece sorgulanacak vektörün yakınına düşen kümelerin aranması gerekir. Çizge tabanlı yöntemler ise Delaunay çizgesi ve görece komşuluk çizgesi gibi yapıların tahmin edilmesi ile oluşturulan çizgelerin üzerinde yapılan arama ile yaklaşık en yakın komşuların bulunmasını içerir. Veri setlerinin göreceli olarak büyük oluşu bugün bu yöntemlerin birlikte nasıl kullanılması ve veri ile sorguların hesaplama düğümlerine nasıl dağıtılması gerektiği sorularını ortaya çıkarmıştır. Problemin dağıtık olarak çözülmesi için çeşitli yöntemler ve sistemler önerilmiş olsa da veri kümelerinin ve sorguların hesap düğümlerine dağıtılmasının daha efektif yapılabileceği görülmüştür. Bu tez hangi yöntemlerin dağıtık çalışmaya daha uygun olduğunu ve hangi yöntemlerin birlikte kullanılabileceğini incelendikten sonra literatürde var olan yöntemlerden yola çıkarak yeni bir bölümleme ve sorgu yönlendirme stratejisi önerir ve bu yöntemin dağıtık sistemler için daha efektif çalışabileceğini gösterir.

Today, we are faced with similarity search or k-nearest neighbors search as an important problem that needs to be solved by databases. Having diverse applications such as pattern recognition and semantic search is what makes the problem important. There are many open-source libraries and database systems that are designed as a vector database today. Widely used database systems are observed to have added similarity search capabilities. Even though research had focused on solving the exact version of the problem at first, the fact that proposed methods effectively were equalivent to a linear search even with cases of 10-or-15-dimensional vectors directed later research at solving the approximate version of the problem. As a matter of fact many methods used for representation learning today produce vectors with dimensionality as high as 384 or 512. This is a result of a phenomenon known as the curse of dimensionality and similarity search methods are affected by this phenomenon. Proposed methods are tree-based, hash-based, quantization-based, inverted index or graph based. Tree-based algorithms divide the feature space or the data. Hash-based methods aim for the data points that are closer together to be in the same buckets makin use of multiple hash functions. When vectors are quantized, dataset fits more easily into the main memory and reduced calculations result in an increase in performance. When the vectors are clustered, only the clusters that are located closer to the query vector needs to be searched. Graph-based methods include finding nearest neighbors by searching graphs constructed by the approximation of structures such as Delaunay graph and relative neighborhood graph. The relatively large size of the datasets raises questions about how these methods should be used together and how the data and the queries should be spread across the nodes. Even though several methods and systems were proposed for solving the problem in a distributed manner it was observed that datasets and queries can be spread across the nodes more effectively. This thesis proposes a new partitioning and query routing strategy by building on existing methods, after analyzing which methods are more suitable for distributed execution and which can be used together and demonstrates that the proposed method can perform more effectively in distributed systems.