Nearest Neighbor Algorithm for Circular dimensions 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?
 A: 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:


*

*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.

*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.

*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)
A: 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.
