A study on a new order based approach for the closest pair and nearest neighbor problems

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.