Approximate Nearest Neighbour Searching
Prof. Amit Chakrabarti
Nearest neighbour searching is one of those basic and fascinating theoretical problems in computer science that has a host of applications in problems from very diverse fields. The problem is widely believed to be intractable in high dimensions, but good approximation algorithms were discovered in the late 1990s.
Our research considers the approximate nearest neighbour search (ANNS) problem on the d-dimensional Hamming cube. Building on techniques of information complexity and communication complexity from an earlier research project of ours, we prove the first unrestricted lower bound for this problem. We also improve previous algorithms for this problem, ending up with matching upper and lower bounds on the number of randomised queries required to solve ANNS.
Shown in the figure is a schematic of the reduction bridging communication complexity and ANNS, a key step in our proof.