Geri Dön

Efficient k-nearest neighbor query processing in metric spaces based on precise radius estimation

Metrik uzaylarda iyi bir alan tahmini ile en yakın k komşu sorgusu işleme

  1. Tez No: 246237
  2. Yazar: CAN ŞARDAN
  3. Danışmanlar: DR. CENGİZ ÇELİK, YRD. DOÇ. DR. ALİ AYDIN SELÇUK
  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: 2009
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Bölümü
  12. Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  13. Sayfa Sayısı: 58

Özet

Resim, görüntü, metin dökümanları gibi karmaşık ve düzensiz yapılarda, benzerlik taraması önemli bir işlemdir. Sıkça kullanılan bir yöntem, bu karmaşık verileri öznitelik vektörleriyle temsil etmektir. Bir başka çözüm ise, sadece bir mesafe fonksiyonuna dayanan metrik uzaylar yaklaşımını kullanmaktır. Objelerin iç yapıları hakkında herhangi bir bilgiye bağlı olunmadığından, daha genel bir iskelet oluşturulmaktadır. Metrik uzay yapısını kullanan yöntemlerin, özellikle yüksek boyutlarda daha iyi performans sergiledikleri gösterilmiştir.Benzerlik taramasında kullanılan yaygın bir sorgu şekli, sorgu objesinin, verilen belirli bir alan içindeki komşularının bulunduğu, alan sorgusudur. Bir başka önemli sorgu ise, en yakın k komşu sorgusudur. İstenilen en uzak komşunun mesafesi değişkenlik gösterdiği için, bu sorguları işlemesi daha zordur. Bu nedenle, tam olarak k tane objeyi kapsayacak bir alan tahmini ile işlem bir alan sorgusuna indirgenebilir. Bu tekniği kullanan yöntemlerle ilgili genel bir sorun, alan tahminin düşük çıktığı durumlarda, algoritma az sayıda obje döndürür ve kalan komşuları bulmak için dizin verisi üzerinde birden çok tarama gerekir.Bu tezde, en yakın k komşu taraması için, alan tahminine dayalı yeni bir sistem sunulmaktadır. Bu sistemde, sadece bir sıralı dizin taraması uygulanmaktadır. Bu, eksik komşu bulunduğu durumlar için, uygun aday olabilecek objelerin kısa bir listede tutulması ile sağlanmaktadır. Ayrıca, daha önce savunulmuş yöntemlerden daha iyi bir alan tahmini içeren yeni algoritmalar önerilmiştir. Bu tahminlerin, bahsedilen aday listesinin boyutunu düşük seviyede tutabilecek kadar gerçeğe yakın olduğu gösterilmektedir.

Özet (Çeviri)

Similarity searching is an important problem for complex and unstructured data such as images, video, and text documents. One common solution is approximating complex objects into feature vectors. Metric spaces approach, on the other hand, relies solely on a distance function between objects. No informationis assumed about the internal structure of the objects, therefore a more general framework is provided. Methods that use the metric spaces have also been shown to perform better especially on high dimensional data.A common query type used in similarity searching is the range query, where all the neighbors in a certain area dened by a query object and a radius are retrieved. Another important type, k-nearest neighbor queries return k closest objects to a given query center. They are more dicult to process since the distance of the kth nearest neighbor varies highly. For that reason, some techniques are proposed to estimate a radius that will return exactly k objects, reducing the computation into a range query. A major problem with these methods is that multiple passes over the index data is required if the estimation is low.In this thesis we propose a new framework for k-nearest neighbor search based on radius estimation where only one sequential pass over the index data is required. We accomplish this by caching a short-list of promising candidates. We also propose several algorithms to estimate the query radius which outperform previously proposed methods. We show that our estimations are accurate enough to keep the size of the promising objects at acceptable levels.

Benzer Tezler

  1. İçerik tabanlı sorgu ve tarama için yapısal ve anlamsal ses içerik analizi

    Structural and semantic analysis of audio content for content-based querying and browsing

    MUSTAFA SERT

    Doktora

    Türkçe

    Türkçe

    2006

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

    Elektronik-Bilgisayar Eğitimi Ana Bilim Dalı

    PROF.DR. BUYURMAN BAYKAL

  2. Assignment query and its implementation in moving object databases

    Hareketli nesne veritabanı sistemleri için atama operatörü ve uygulaması

    ALİ RIZA KONAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2006

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

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. TAFLAN İMRE GÜNDEM

  3. Kümeleme ve yerel aykırı faktör tabanlı aktif öğrenme yaklaşımları: Otomotiv sektöründe bir uygulama

    Clustering and local outlier factor-based active learning approaches: An application to the automotive industry

    FATMA SANİYE KOYUNCU

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    Endüstri ve Endüstri MühendisliğiBursa Uludağ Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. TÜLİN İNKAYA

  4. The efficiency of classification techniques in predicting thyroid disease

    Tiroid hastalığını öngörmede sınıflandırma tekniklerinin etkinliği

    KHALID ABDALSTAR SALMAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKarabük Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ EMRULLAH SONUÇ

  5. Türkiye'deki teknoloji geliştirme bölgelerinin etkinlik ve yenilikçilik yönünden analizi

    Analysis of science and technology parks in Türkiye in terms of efficiency and innovativeness

    ONUR BİLGİN

    Doktora

    Türkçe

    Türkçe

    2023

    EkonomiKırıkkale Üniversitesi

    İktisat Ana Bilim Dalı

    PROF. DR. HACI BAYRAM IŞIK