|
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 |
Size | Format |
|---|
| 200003.pdf | | 551Kb | Adobe PDF | View/Open |
|
Find published version via |
All items in this Repository are protected by copyright, with all rights reserved.
|
