Space-time tradeoffs for approximate nearest neighbor searching
Abstract
Nearest neighbor searching is the problem of preprocessing a set of n point points in d -dimensional space so that, given any query point q , it is possible to report the closest point to q rapidly. In approximate nearest neighbor searching, a parameter ε > 0 is given, and a multiplicative error of (1 + ε) is allowed. We assume that the dimension d is a constant and treat n and ε as asymptotic quantities. Numerous solutions have been proposed, ranging from low-space solutions having space O ( n ) and query time O (log n + 1/ε d −1 ) to high-space solutions having space roughly O (( n log n )/ε d ) and query time O (log ( n /ε)).
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 01, 2009
- Source ID
- 10.1145/1613676.1613677
Entities
People
- David M. Mount
- Sunil Arya
- Theocharis Malamatos
Organizations
- Hong Kong University of Science and Technology
- National Science Foundation
- Office of Naval Research
- Research Grants Council, University Grants Committee
- University of Maryland
- University of Peloponnese