4
$\begingroup$

Problem: Given a set of points $S = \{x_1, x_2, x_3, ..., x_n\}$ from $\mathbb{R}^m$ and an offset vector $v \in \mathbb{R}^m$, find a set $Z \subseteq S \times S$ containing $k$ pairs of points $(x_i, x_j)$ such that the quantity $|x_i-x_j-v|$ (Euclidean norm) is smaller for any pair $(x_i,x_j) \in Z$ than that of any pair not in $Z$.

One obvious approach would be to maintain a max-heap of size $k$ and run through all pairs of points $(x_i, x_j) \in S^2$, inserting pairs into the heap if $|x_i-x_j-v|$ is smaller than the current maximum. This algorithm has $O(mn^2 \log k)$ running time.

Is there a faster algorithm? Is there a lower bound on the complexity of this problem?

This problem is motivated by an application where $50 \leq m \leq 1000$, $10^5 \leq n \leq 10^6$, and $5 \leq k \leq 100$, and the running time should be in seconds, not minutes or hours (which is I the naive approach above is not applicable).

$\endgroup$
  • $\begingroup$ 3. Your problem is basically a variant of the nearest neighbor problem. I suggest you look at algorithms for the nearest neighbor problem. I expect that many/most such algorithms can be adjusted to handle your setting. I suggest that you go read about all such algorithms, think about how they can be adjusted to your setting, and then edit your question to show what you've come up with (or answer your own question, if you found a satisfactory answer). $\endgroup$ – D.W. Apr 22 '16 at 19:26
  • $\begingroup$ @D.W. 1. and 2. Added cost for vector operations and specified some bounds on the problem. 3. Thank you for the suggestion. I am doing that, but I thought it would be nice to parallelize the search for a solution by posting the problem here. Perhaps someone has seen this problem before and could guide the search. $\endgroup$ – Alexandre Apr 23 '16 at 13:40
4
+25
$\begingroup$

One optimization I would propose is over the brute force search:

$$ \begin{align*} d(\mathbf{x}_i, \mathbf{x}_j) &= \lVert (\mathbf{x}_i-\mathbf{x}_j) - \mathbf{v} \rVert^2\\ &= \sum\limits_{k=1}^N (x_i^k - x_j^k-v^k)^2\\ &= \sum\limits_{k=1}^N ((x_i^k-x_j^k)^2+(v^k)^2-2v^k(x_i^k-x_j^k))\\ &= \sum\limits_{k=1}^N ((x_i^k)^2+(x_j^k)^2-2x_i^kx_j^k+(v^k)^2-2v^k(x_i^k-x_j^k))\\ \end{align*} $$ as $(v^k)^2$ is the same for all pairs, we could simply drop it - doesn't effect minimization.

\begin{align*} d(\mathbf{x}_i, \mathbf{x}_j) &= \sum\limits_{k=1}^N ((x_i^k)^2+(x_j^k)^2-2x_i^kx_j^k-2v^kx_i^k+2v^kx_j^k)\\ &= \sum\limits_{k=1}^N (x_i^k)^2 + \sum\limits_{k=1}^N(x_j^k)^2 - 2\sum\limits_{k=1}^N x_i^kx_j^k - 2\sum\limits_{k=1}^N v^kx_i^k + 2\sum\limits_{k=1}^N v^kx_j^k\\ \end{align*}

Let's go back to matrix notation:

\begin{align*} d(\mathbf{x}_i, \mathbf{x}_j) &= \lVert \mathbf{x}_i \rVert+\lVert \mathbf{x}_j \rVert - 2(\mathbf{x}_i \cdot \mathbf{x}_j)- 2(\mathbf{x}_i \cdot \mathbf{v}) + 2(\mathbf{x}_j \cdot \mathbf{v})\\ \end{align*}

Note that all the terms, except the middle one is free of the pairwise computations and can be computed in $O(N)$ time and stored. To compute $(\mathbf{x}_i \cdot \mathbf{x}_j)$, one can assemble matrix $X$, which contains $\mathbf{x}_i^T$ at each row and compute $D=XX^T$. Each element in this huge symmetric matrix, would then give you the dot product per pair: $D(i,j)=(\mathbf{x}_i \cdot \mathbf{x}_j)$. If memory is of concern, you can simply revert to iterative computation and not store the intermediate dot products. All in all, this would save a lot of time in pairwise comptutations, speeding up the entire search. I assume that you could couple this easy to implement approach with any other optimization to further boost the performance. In all the calculations I omitted $sqrt$ because it doesn't influence the relative comparison of distances.

If the assumption is that $\mathbf{v}=\mathbf{0}$ ($\mathbf{v}$ is null), the entire procedure boils down to a fast computation of distance matrix - this view might benefit certain applications.

$\endgroup$
  • $\begingroup$ Thanks for the contribution. $D$ matrix preparation will be $O(mn^2)$, but after this setup solutions for different $v$ will be $O(n^2 \log k)$, a moderate improvement over the original $O(mn^2 \log k)$ solution proposed in the question. Though I can't select this as the answer to the original question, I think the insight might be valuable for other answers and so I upvoted. $\endgroup$ – Alexandre Apr 25 '16 at 23:34
  • $\begingroup$ Well, matrix multiplication nowadays have $O(N^{2.373})$ complexity. Given that $D$ is symmetric, you'll have a less complex operation. If you have pre-computed $D$, then for varying values of $\mathbf{v}$, you only have some linear complexity, as you don't need to pair anything now. You could also sum the first three terms in the final equation and further reduce runtime and storage. $\endgroup$ – Tolga Birdal Apr 28 '16 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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