Expected-case analysis of approximate nearest neighbor algorithms

Most research in algorithms for geometric query problems has focused on their worst-case performance. But when information on the query distribution is available, the alternative paradigm of designing and analyzing algorithms from the perspective of expected-case performance appears more attractive. In this thesis, we study the approximate nearest neighbor problem from this point of view. As a first step in this direction, we assume that the query points are chosen uniformly from inside a hypercube that encloses all the data points. However, we make no assumption on the distribution of data points. We show that with very simple data structures, it is possible to achieve linear space and logarithmic (or polylogarithmic) query time in the expected case. In contrast, the data structures known to achieve linear space and logarithmic query time in the worst case are complicated, and algorithms on them run more slowly in practice