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

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.