From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2008-04-23 15:24:49
On Wed, Apr 23, 2008 at 12:15 PM, Phil Endecott
> Federico J. Fern?ndez wrote:
> > In my case, I'll be working in Spatial Indexes with Hartmut Kaiser.
> Congratulations Federico. I'll be really interested to hear how you
> get on.
> Here's my spatial index problem of the day: I have a time-ordered
> series of GPS fixes which I'm inserting into a spatial container.
> Their locations are highly correlated with time, so I'd like to be able
> to use a hint to say that each point I insert is adjacent to the
> previous one (like we can do when inserting into a std::map). If I can
> find a good way to do this I could improve this code from O(n log n) to
> O(n), which would be very worthwhile.
I had a very similar problem. I had many thousands of GPS coordinates
coming in, with position and time stamp that needed to be spatially
indexed so that you could later query for all points within M distance
and N hours/minutes/seconds of another spatio-temporal point.
I ended up using a Bounding Interval Hierarchy that had a bucket of
points at each leaf, rather than a single point at each leaf, and that
bucket was sorted temporally (hashed by timestamp). This was because
the order I received the points was not necessarily in temporal order.
In your case, Phil, it might make sense to reverse the ordering (i.e.
hash by time, then use a spatially indexed bucket).
A Spatio-Temporal data structure would be a great addition to boost.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk