En yakın çift ve en yakın komşu problemlerine sıralama bazlı yeni bir yaklaşım üzerine bir çalışma
A study on a new order based approach for the closest pair and nearest neighbor problems
Yazar: GÖRKEM TOKATLI
Danışman: PROF. DR. MEHMET EMİN DALKILIÇ
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Uluslararası Bilgisayar Ana Bilim Dalı
Derece: Doktora, 2018
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Veriler arasında benzerlik, bağlantı ve ilişkiler kurmak, birçok alanda veri ile yapılabilecek en etkili işlemlerden biri olmuştur. Dünya çapında saklanan dijital veri miktarının hızla artması, bu verinin hızlı ve efektif olarak işlenmesi ihtiyacını da beraberinde getirmiştir. Bu çalışmada, veri sınıflandırma ve benzerlik bulma yöntemlerinin temelinde yer alan en yakın çift ve en yakın komşu problemleri ele alınmıştır. 
Bu tez çalışmasında, vektör uzayındaki en yakın çift ve en yakın komşu problemlerine karşı genel bir sıralama bazlı yaklaşım uygulanmıştır. Bu yaklaşımda, vektör uzayında sahip olunan geometrik bilgi kullanılarak daha hafif veri yapısına sahip daha hızlı algoritmalar tasarlanması amaçlanmıştır.
2 boyutlu ve çok boyutlu en yakın çift problemlerine karşı geliştirilmiş QuickCP algoritması analiz edilerek rastgeleleştirme metodu uygulanmış ve algoritmanın paralelleştirilmesi sağlanmıştır. Noktaların bağımsız olarak hesaplanmasını sağlayan QuickCP+  algoritması geliştirilmiştir. Böl ve Fethet yaklaşımını içeren hibrit yapıya sahip farklı bir algoritma daha tasarlanmıştır. Dinamik en yakın çift problemleri için, DQCP isimli yeni bir algoritma tasarlanmıştır. Anahtarlı Tablo veri yapısı kullanan DQCP+ isimli yeni bir algoritma geliştirilmiştir. En yakın komşu problemleri için aynı yaklaşım kullanılarak QNN ve QANN isimli algoritmalar geliştirilmiştir.
Analizler ve çalışma zamanı testleri sonucunda, sıralama bazlı yaklaşım kullanarak en yakın çift problemleri için geliştirilen algoritmaların beklenen hız performansının literatürdeki çalışmalarla karşılaştırılabilir veya daha iyi olduğu gösterilmiştir.

Abstract:
Finding similarity, relations and classifications has been one of the most effective usage of owned data. Size of stored electronic data has rapidly increased globally, which yielded the demand of effectively processing big data. The scope of this work consists of closest pair and nearest neighbor problems, which are fundamental in data classification and similarity search techniques.
In this thesis, an order based approach is applied to the variety of closest pair and nearest neighbor problems in vector space. This approach uses the geometric information in order to develop faster algorithms while using lighter data structures.
In this work, detailed analysis of QuickCP, the order-based closest pair algorithm is carried out. Randomization and parallelization methods are applied to this algorithm. A novel algorithm (QuickCP+) that processes points independently is developed. Another hybrid algorithm that uses the divide and conquer approach is proposed. For the dynamic closest pair problems, a novel algorithm named DQCP is proposed. Another algorithm (DQCP+), which uses hash table structure is also proposed. The same order-based approach is applied to the nearest neighbor problems, and algorithms named QNN and QANN are developed.
Analyses and run-time tests revealed that, proposed algorithms for the closest pair problems have comparable or better performance than that of algorithms in literature.