Is there an algorithm for fast nearest neighbor search of circular dimensions? e.g., For a dimension based on "hour of day", a KD-tree would place 00:01 and 23:59 far apart. But the proper distance metric would yield the shortest distance (2min). Angle is another such dimension, or seasons, or months, or ...

I was wondering whether a ball tree might fit the bill? Does such a problem still fit within the triangle inequality required there?

  • 2
    $\begingroup$ Can't you run kNN on any distance matrix? Just compute what you find adequate. A ball tree is just a data-structure and doesn't give you a metric, no? $\endgroup$
    – ziggystar
    Mar 11 '13 at 12:56
  • 2
    $\begingroup$ You can use polar coordinates: an angle $\theta$ becomes a point $(\cos\theta, \sin\theta)$. The distance is different, but the nearest neighbours are the same. $\endgroup$ Mar 11 '13 at 14:09
  • $\begingroup$ Are there any side effects (aside the obvious of increasing the set with one more variate ) in going over to polar coordinates? $\endgroup$
    – Ove
    Mar 11 '13 at 14:26
  • $\begingroup$ None whatsoever, Ove, because the two metrics are equivalent: two points that are nearest neighbors along the circle are also nearest neighbors in $\mathbb{R}^2$, and conversely. $\endgroup$
    – whuber
    Mar 11 '13 at 19:15
  • $\begingroup$ whuber, Vincent: Is it that obvious if you're using multiple dimensions? The distances interact non-linearly (and since you're no longer in the flat torus, the gaussian curvature makes a difference, right?) It might be true, but it's not directly obvious to me. $\endgroup$ Mar 11 '13 at 22:05

How many circular dimensions are there? Two of the tricks described below trade off resources for representational convenience, unfortunately exponentially on the number of circular dimensions.

There are at least three tricks you can use:

  1. Use coordinate patches: create many small kd-trees, overlapping so that they are locally continuous. This will not work if your range queries are wide enough to go past the boundaries of the patch.

  2. You can manually glue the pieces of the space by making extra queries across the boundaries and adding a post-processing pass. This will be exponential in the dimension of the corner the point is closest to, but will use no extra memory.

  3. Use multiple covering. In other words, unwrap the space along every border, and make each point have many representations so the boundaries "are invisible". With one circular dimension, :01 would be stored as three points:

    :-59, :01, :61

    With two circular dimensions, you'd have 00:01 stored as

    -24:-59, 00:-59, 24:-59

    -24:01, 00:01, 24:01

    -24:61, 00:61: 24:61

    You can see that the space blowup increases exponentially with the number of circular dimensions. The advantage is that with this representation, the querying is exactly the same as before. (Of course, this is just a materialization of trick 2). If you know how far back your range queries work, then you might be able to prevent multiplication of some of the points (if they're sufficiently deep in the interior of the space)

  • $\begingroup$ I will try this solution, and compare its efficiency and space requirements to that of the polar coordinates. $\endgroup$
    – Ove
    Mar 12 '13 at 9:25

Try a clustering algorithm like DBScan. R and Weka both have this algo. It's density based. So if the clusters are continuous in nature for the day, it should do a good job of making a cluster for a day.

  • $\begingroup$ Both R and Weka have incredibly slow implementations of this algorithm. It's correctly written DBSCAN, btw. the "N" for example is for "noise". $\endgroup$ May 31 '13 at 0:11

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.