Re: [boost] Congratulations to the Successful Summer of CodeStudents!

From: Hartmut Kaiser (hartmut.kaiser_at_[hidden])
Date: 2008-04-24 08:53:14

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

Spatial indices are just another ordering criteria for data. I think that it
should be possible to use Boost.Bimap or Boost.MultiIndex for this task,
having one index ordering the data in time, and the other index is the
spatial one. This is just a hunch, though, I didn't think about or
investigate this in more detail.

Regards Hartmut