HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/692
Title: Expected-Case complexity of approximate nearest neighbor searching
Authors: Arya, Sunil
Fu, Ho-Yam Addy
Keywords: Geometric query
Expected-case performance
Approximate nearest neighbor
Optimal expected query time
Issue Date: 2003
Citation: SIAM journal on computing, v. 32, no. 3, 2003, p. 793-815
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2000-03
Abstract: 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.
URI: http://hdl.handle.net/1783.1/692
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
200003.pdf551KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.