Experimental Efficiency Study of Nearest Neighbors Search Algorithms in Metric Spaces for Clustering Objects

An acute problem of clustering appears with the technology progress and the exponential growth in data volumes. Several clustering algorithms use the nearest neighbor search to find the closest cluster to a given point. In this paper, we consider effective nearest neighbors search algorithms in a variety of metric spaces and their impact on the time and quality of clustering, also experimental results of the comparative analysis are provided. The study was conducted using a hierarchical agglomerative clustering algorithm and nearest neighbor search algorithms that are based on trees and hashing together Euclidean, Clark, Lorentzian and Penrose distances. Two kind of input was used for the experimental study: randomly generated (generalized characteristics of time series) and taken from real life (electromyography records). The paper contains 57 pages, 4 chapters, 33 illustrations, 4 tables, 49 bibliography items, 2 appendices. Keywords: clustering, hierarchical clustering, nearest neighbor search, kd tree, vp tree, locality-sensitive hashing, best bin first.