Please use this identifier to cite or link to this item:

Expected-Case complexity of approximate nearest neighbor searching

Authors Arya, Sunil
Fu, Ho-Yam Addy
Issue Date 2003
Source SIAM journal on computing, v. 32, (3), 2003, p. 793-815
Summary 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. 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 a hypercube that encloses all the data points; however, we make no assumption on the distribution of data points. We investigate three simple variants of partition tree: sliding-midpoint, balance-split, and hybrid-split trees. We show that with these simple tree-based 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 complex, and algorithms on them run more slowly in practice. Moreover, for the sliding-midpoint tree, we prove that it achieves optimal expected query time under reasonable assumptions.
Language English
Format Technical report
Access Find@HKUST
Files in this item:
File Description Size Format
200003.pdf 551.17 kB Adobe PDF