Geri Dön

Yüksek boyutlu vektörlerin dagıtık olarak yüksek performans ile aranması

High-performance distributed search of high dimensional vectors

PDF İndir

  1. Tez No: 998995
  2. Yazar: AYKUT ALPARSLAN KOÇ
  3. Danışmanlar: DR. MEHMET BURAK AKGÜN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2026
  8. Dil: Türkçe
  9. Üniversite: Tobb Ekonomi ve Teknoloji Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

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.

Özet (Çeviri)

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.

Benzer Tezler

  1. Tez No

    847173

    Fake news classification using machine learning and deep learning approaches

    Makine öğrenimi ve derin öğrenme yaklaşımlarını kullanarak sahte haber sınıflandırması

    SAJA ABDULHALEEM MAHMOOD AL-OBAIDI

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGazi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ TUBA ÇAĞLIKANTAR

  2. Tez No

    1002346

    Neutrino particle direction estimation using transformer-based deep learning

    Transformer tabanlı derin öğrenme kullanılarak nötrino parçacık yönü kestirimi

    ŞEVVAL COŞKUN

    Yüksek Lisans

    İngilizce

    İngilizce

    2026

    Fizik ve Fizik Mühendisliğiİstanbul Teknik Üniversitesi

    Fizik Mühendisliği Ana Bilim Dalı

    PROF. DR. EMRE ONUR KAHYA

    ÖĞR. GÖR. DOĞU SIRT

  3. Tez No

    806195

    Convolutional ensemble learning for edge intelligence

    Kenar zeka için evrişimsel topluluk öğrenmesi

    İLKAY SIKDOKUR

    Yüksek Lisans

    İngilizce

    İngilizce

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi Üniversitesi

    Hesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı

    PROF. DR. ARDA YURDAKUL

    DR. ÖĞR. ÜYESİ İNCİ MELİHA BAYTAŞ

  4. Tez No

    451155

    Design and performance analysis of enhanced network coded cooperative communication systems

    Gelişmiş ağ kodlamalı işbirlikli haberleşme sistemlerinin tasarımı ve performans analizi

    RIDA KHAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. İBRAHİM ALTUNBAŞ

  5. Tez No

    655117

    Kabin tipi ofislerin iklimlendirilmesinde hız ve sıcaklık dağılımlarının sayısal olarak incelenmesi

    Numerical analysis of velocity and temperature distributions for air conditioning of cabin type offices

    MUHAMMED YASİN YAVUZ

    Yüksek Lisans

    Türkçe

    Türkçe

    2021

    Makine MühendisliğiFırat Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. CENGİZ YILDIZ

Geri Dön