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

<ul>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ul>

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

CC BY-SA 3.0
2013-08-17T20:30:10.257Z
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.
Kevin
CC BY-SA 3.0
2013-08-17T20:15:36.970Z
2013-08-17T20:15:36.970Z
D.W.
<p><strong>This is almost certainly impossible.</strong></p>

<p>Suppose you could solve your problem with preprocessing time $P(n)$ and query time $Q(n)$.  Then there is a simple algorithm to solve <a href="http://en.wikipedia.org/wiki/3SUM">the 3SUM problem</a>—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.</p>

<p>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 <em>integers</em>, 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.</p>

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

CC BY-SA 3.0
2013-08-18T03:13:18.103Z
2013-08-18T13:41:41.363Z
2013-08-18T13:41:41.363Z
Jeffε
<p>Here is a nearest neighbor problem.</p>

<p>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).</p>

<p>(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)$).</p>

<p>Solutions that don't work:</p>

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

<p>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.</p>

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

<p>Thanks!</p>

<p>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.</p>

CC BY-SA 3.0
2013-08-17T20:13:23.650Z
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.
D.W.
CC BY-SA 3.0
2013-08-17T21:39:02.940Z
Pre-processing is limited to O($n$ log $n$).  I updated the problem statement.
Kevin
CC BY-SA 3.0
2013-08-17T22:00:29.390Z
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.
Kevin
<ds.algorithms><cg.comp-geom><ds.data-structures>
Select two numbers that sum to $p$, using sub-linear query time
Kevin
# Select two numbers that sum to $p$, using sub-linear query time

(Asked by: username_0 on 2013-08-17)

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.

**Tags:** ds.algorithms, cg.comp-geom, ds.data-structures
> **Comments:**
> **username_1**: 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.  
> **username_0**: Pre-processing is limited to O($n$ log $n$).  I updated the problem statement.  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_2 on 2013-08-18. Score: 17 | Accepted answer

**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](http://en.wikipedia.org/wiki/3SUM)—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 by username_1 on 2013-08-17. Score: 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.

> **Comments:**
> **username_0**: 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.  

---

