Büyük hacimli görüntü veri tabanlarında hızlı görüntü arama

Abstract

Bu tez çalışmasında, büyük hacimli görüntü veri tabanları üzerinde hızlı ve doğru bir şekildegörüntü arama yapılabilmesi için geliştirilen RDH (Randomized Distributed Hashing)yöntemi sunulmuştur. Büyük görüntü veri tabanlarında sorgulanan görüntülere yakınörneklerin bulunabilmesi için genellikle ANN (Approximate Nearest Neighbor) yöntemlerikullanılmaktadır. Bu yöntemlerde aranan örneklere benzer en yakın gerçek örneklerinbulunması yerine yakın olması muhtemel örnekler bulunmaktadır. Çoğu zaman özetlemeyöntemleriyle gerçeklenen bu yöntemlerin kullanılmasıyla arama zamanı ciddi orandaazaltıbilmektedir. ANN arama yöntemleri genellikle merkezi olarak uygulanmaktadır.Ancak gerçek dünya uygulamalarında veriler genellikle dağıtık bir şekilde saklanmaktadır.Bu durum ANN arama yöntemlerinin dağıtık bir şekilde uygulanabilmesinigerektirmektedir. Bu amaçla önerdiğimiz yaklaşımda LSH (Locality Sensitive Hashing)dağıtık bir şekilde uygulanmıştır. Veri bir küme içindeki farklı düğümlere dağıtılmışsonrasında her bir düğümde aynı özet fonksiyon kümesi kullanılarak veri özetlenmiştir.Sorgu aşamasında sorgu örneği her bir düğümde yerel olarak aranmaktadır. Paralelsorgulardan faydalanıldığında sorgu süresi önemli oranda düşmüştür. Deneysel çalışmalarda10 düğüm kullanıldığında sorgu hızı yaklaşık olarak 10 kat artırılmıştır. Sistemin başarısınıdeğerlendirmek için kullanılan MAP (Mean Average Precision) değeri literatürdekiçalışmalarla kıyaslanabilecek ölçüde yüksek çıkmıştır. Bu çalışmada aynı zamandadüğümlerde aynı özet fonksiyonların kullanılması yerine farklı özet fonksiyonların veseçilmiş özet fonksiyonların kullanımıyla LSH yönteminin dağıtık kullanımı detaylı birşekilde irdelenmiştir. Seçilmiş özet fonksiyonları indeksleme yapılmadan önce veriyi bölmeözelliğine göre oluşturulmuştur. LSH yöntemi veri bağımsız bir yöntem olduğundandüğümlerde aynı özet fonksiyonu kullanıldığında alınan sonuçlara benzer sonuçlar eldeedilmiştir. Alınan sonuçlar son zamanlarda yayınlanan ve dağıtık özetleme konusunda farklıyöntemlere ait sonuçlar içeren bir çalışma ile karşılaştırılmıştır. Önerilen yöntem dağıtıkolarak büyük boyutlu veri kümelerinde görüntü arama için umut vermektedir.

In this thesis, RDH (Randomized Distributed Hashing) method which is developed for fastand accurate image search on large scale image databases is presented. ANN (ApproximateNearest Neighbor) approaches are usually used to find the nearest samples to the queriedimages in large scale image databases. In these methods approximate nearest samples arefound instead of finding the real nearest samples. Using these methods, which are oftenimplemented by hashing methods, can significantly reduce the query time. ANN searchmethods are generally applied in centralized manner. However in real-world applications,data are often stored in a distributed manner. This situation requires to implement ANNsearch methods in a distributed manner. For this purpose in our proposed approach, LSH(Locality Sensitive Hashing) method is applied in a distributed way. Data are distributed todifferent nodes within a cluster, and then the data are hashed on each node using the samehash function set. In query phase, the query instance is searched locally on each node. Byexploiting from parallelism, the query time is significantly decreased. In the experimentalstudies, we have a speed up of 10 for the query performance in the distributed scheme with10 nodes. The level of MAP (Mean Average Precision) scores that are used to evaluatesystem performance are quite high which are comparable to other methods in literature. Wehave also investigated the usage of different and selected randomized hash functions indifferent nodes rather than using same indexing. By this way the distributed usages of LSHare scrutinized. We create selected hash functions according to their data division propertybefore indexing. Since LSH is data independent method, we have obtained similar resultswith using same hash functions. We compared our experimental results with state-of-the-artmethods given in a recent study. The proposed distributed scheme is promising for searchingimages in large datasets with multiple nodes.