On the Optimality of the Dimensionality Reduction Method

We investigate the optimality of (1+\in )-approximation algorithms obtained via the dimensionality reduction method. We show that: --Any data structure for the (1+\in )-approximate nearest neighbor problem in Hamming space, which uses constant number of probes to answer each query, must use n^{\Omega \left( {1/ \in ^2 } \right)} space. --Any algorithm for the (1+\in )-approximate closest substring problem must run in time exponential in 1/ \in ^{2 - \gamma } for any \gamma > 0 (unless 3SAT can be solved in subexponential time) Both lower bounds are (essentially) tight.

Authors

• Alexandr Andoni
• Piotr Indyk
• Mihai Patrascu

Keywords

• Polynomials
• Data structures
• Nearest neighbor searches
• Frequency
• Clustering algorithms
• Probes
• Pattern analysis
• Concrete
• Design methodology
• Algorithm design and analysis
• Dimensionality Reduction
• Dimensionality Reduction Methods
• Data Structure
• Lower Bound
• Estimation Algorithm
• Estimation Problem
• Substring
• Exponent
• Running Time
• Time Constant
• Hardness
• Algorithm For Problem
• Codeword
• Forward Error Correction
• Query Time
• Bernoulli Process
• Answer Yes