Application of Approximate Nearest Neighbour Search Algorithm- Locality Sensitive Hashing

Abstract

In computer science, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Exact nearest neighbour search algorithms return accurate results but with the dimensions the complexity, both time and space increase exponentially. Thus striking a tradeoff between complexity and accuracy, we shift to approximate nearest neighbour search algorithms wherein we cut down on the complexity and in turn compromise on the accuracy. In this year long project, various approximate nearest neighbour search algorithms were explored, the prominent ones being implemented as well. Thereafter, the algorithms so implemented were compared with each other on various grounds like time complexity and dependence on dimension by running the algorithms for various datasets.