Select two numbers that sum to $p$, using sub-linear query time

Question

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.

Answer 1

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.

Answer 2

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.