On Nearest Neighbors

This dissertation is devoted to various aspects of the nearest neighbors search. The nearest neighbor related techniques are applied in diverse areas including computational geometry, databases, robotic sensing, DNA sequencing, spell checking, statistical classification, cluster analysis, chemical similarity, computer vision, plagiarism detection, recommendation systems, viral marketing, social networks, data compression, coding theory and pattern recognition. The basic concept is the following. Knowledge on a given object may be considerably increased by examining objects which are similar or in some way connected to it. The nearest neighbors search provides means to identify such objects. Depending on the meaning of “similar” or “connected” in a particular case, an appropriate definition of a neighbor may be introduced. In this study, we show efficient methods of searching for neighbors in different cases. Among the numerous contexts in which the nearest neighbors search is applied, we are going to focus on similarity search in metric spaces and information dissemination in social networks.