1
$\begingroup$

Lots of dating apps sort they results by distance. That's it, you're at position $(x, y)$ at the Earth map and the application shows you up to, let's say, $k$ potential partner. Those are not any people, but the $k$-nearest to you.

If I've got a vector $v$ with $n$ pairs $(x_i, y_i)$ indicating people's position, calculating the distance from my position $(x, y)$ to each position $(x_i, y_i)$ would be $\Theta(n)$, and selecting the $k$ smallest would probably be also $\Theta(n)$ (in mean in running time, probably using min heaps or something alike).

The problem is that $n$ may be huge (imagine how many users do use Tinder, Grindr and applications like that).

So, my question is, how do they do it so fast?

$\endgroup$
2
  • 1
    $\begingroup$ Cluster first, and then find distances only within the clusters. $\endgroup$
    – Paul
    Aug 24 '17 at 14:55
  • 1
    $\begingroup$ Thankfully, the Earth isn't high-dimensional, or else clustering wouldn't work very well. :-P $\endgroup$
    – Brian Tung
    Aug 28 '17 at 21:58
2
+50
$\begingroup$

As was hinted in the comment, clustering is the key. One possible scenario could be the following:

When you start your app, the app puts you into a bucket (or bin, or category, or whatever you want to call it). The bucket gives a hint to your location, e.g. your country, city, etc. This happens to all users, so everyone is already pre-sorted into a bucket (clustering) and this must not happen during the actual search. Now when there are $N$ buckets with on average $\bar n$ inhabitants, then you can first look for the $K<<N$ nearest buckets to your bucket, e.g. your own city and the nearest ones, and then you only look at those $\bar n K <<\bar nN=n$ nodes in your distance graph. If this number is still too large (e.g. a very big city) you might consider choosing smaller buckets or you cluster the buckets too, e.g. city districts.

Finding the $K$ nearest buckets might take $\Theta(N)$ time, but since the buckets represent cities or other immutable entities, you will calculate this only once. So it is not part of the interactive search. Now your search takes $\Theta(\bar nK)$ steps which is hopefully much smaller than $\Theta (n)= \Theta(\bar n N)$.

$\endgroup$
1
$\begingroup$

One data structure very applicable to this kind of problem is the k-d tree. (I think the wiki article explains it well enough, but comment if you have questions). If you store your positional data in a k-d tree, a nearest neighbor search becomes $O(\log(n))$.

I'm not sure if this is precisely what dating apps use (they probably just cluster by city where $n_{\text{city}}$ is "small enough" to brute search), but k-d trees are common in the field of motion-planning.

$\endgroup$
2
  • $\begingroup$ Clustering is a very wide term. I think k-d-trees can be considered a clever online clustering strategy. $\endgroup$
    – M. Winter
    Aug 29 '17 at 9:47
  • $\begingroup$ I think that formally a tree would not be considered table-based binning / clustering, although I see what you are getting at. I would call them both "data structures" in general. I'll edit my answer to avoid confusion where I juxtaposed the terms. $\endgroup$
    – jnez71
    Aug 29 '17 at 15:09

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.