9
$\begingroup$

Here is a nearest neighbor problem.

Given reals $a_1, \ldots, a_n$ (very large $n$!), plus target real $p$, find $a_i$ and $a_j$ whose SUM is closest to $p$. We allow reasonable pre-processing/indexing of $a_1, \ldots, a_n$ (up to $O(n \log n)$), but at query time (given $p$), the result should be returned very fast (e.g., $O(\log n)$ time).

(Simpler example: if we only wanted the SINGLE $a_i$ that is closest to $p$, we would sort $a_1, \ldots, a_n$ offline, $O(n \log n)$, then do binary search at query time, $O(\log n)$).

Solutions that don't work:

1) Sort $a_1, \ldots, a_n$ offline, then at query time, start from both ends & move two pointers inward (http://bit.ly/1eKHHDy). Not good, because of $O(n)$ query time.

2) Sort $a_1, \ldots, a_n$ offline, then at query time, take each $a_i$ and perform binary search for a "buddy" that helps it sum to something close to $p$. Not good, because of $O(n \log n)$ query time.

3) Sort all pairs $(a_{1}, \ldots, a_{n})$ offline, then do binary search. Not good, because of $O(n^2)$ pre-processing.

Thanks!

ps. Further generalizations needed for practice: (1) $a_1, \ldots, a_n$ and $p$ to be 50-dimensional vectors, (2) "close" to be vector cosine distance, and (3) $k$-best closest pairs-that-sum, not just 1-best.

$\endgroup$
3
  • $\begingroup$ Is there a limit on the pre-processing time or the amount of space we can use after pre-processing? If we're limited to $O(n)$ space, do you have any reason to believe it can be solved in, say, $O(\lg n)$ time? That seems awfully unlikely to me. $\endgroup$
    – D.W.
    Aug 17, 2013 at 20:13
  • $\begingroup$ Pre-processing is limited to O($n$ log $n$). I updated the problem statement. $\endgroup$
    – Kevin
    Aug 17, 2013 at 21:39
  • $\begingroup$ I don't have any reason to believe that querying can be fast, but many useful results for nearest-neighbors (kd-trees, locality-sensitive hashing, etc) seem counter-intuitively good to me. An approximate solution using locality-sensitive hashing would be fine for practical use. $\endgroup$
    – Kevin
    Aug 17, 2013 at 22:00

2 Answers 2

17
$\begingroup$

This is almost certainly impossible.

Suppose you could solve your problem with preprocessing time $P(n)$ and query time $Q(n)$. Then there is a simple algorithm to solve the 3SUM problem—Given a set of $n$ real numbers, do any three elements sum to zero?—in $P(n)+n\cdot Q(n)$ time. We pre-process all the numbers, then for each number $a_k$, we find the value of $a_i+a_j$ that is closest to $-a_k$; if it matches $-a_k$ exactly, we have found a solution to the 3SUM problem.

However, the fastest algorithm known for 3SUM runs in $O(n^2)$ time, and this algorithm is widely conjectured to be optimal. Moreover, there is a matching $\Omega(n^2)$ lower bound in a restricted but natural decision tree model of computation. For sets of integers, there are slightly subquadratic-time algorithms that "play games with bits", but even in the integer RAM model, 3SUM is conjectured to require $\Omega(n^2/\text{polylog}\,n)$ time.

So assuming that conjecture is correct, your problem either requires (near-)quadratic preprocessing time or (near-)linear query time.

$\endgroup$
2
$\begingroup$

If you can use unlimited space and unlimited time during pre-processing, then the following solution meets your requirements:

  • During pre-processing, compute the set $\{a_i+a_j:1\le i\le j\le n\}$, and store this set in sorted order. This set can be generated and sorted in $O(n^2)$ time, and it takes $O(n^2)$ space to store it.

  • Now to answer a query (to find $a_i,a_j$ where $a_i+a_j$ is as close to $p$ as possible), simply do a binary search in this sorted list. That will take $O(\lg n)$ time.

If this solution is not acceptable, you need to think through your requirements more carefully and edit the question accordingly.

$\endgroup$
1
  • $\begingroup$ Hi, and thank you! But your solution is the same as my solution #3, which is problematic due to O(n^2) pre-processing time. In my case, n is very large (e.g., 1m) and I must avoid O(n^2) operations. $\endgroup$
    – Kevin
    Aug 17, 2013 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.