!!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!! !!!
-------------------------------------------------------------------------------
                                       
                                       
                   B O S T O N   U N I V E R S I T Y
                                       
                      Computer Science Department
                                       
                          C O L L O Q U I U M

              Access Methods For Spatiotemporal Databases

                           George Kollios
			     
			     
                        Polytechnic University


  		         Wednesday,  April 19
			       11:00 AM 
                       (Coffee served at 10:45AM)

                                       
                         Seminar Room / MCS 135
                                       


    Spatiotemporal databases  manage spatial objects that change
    positions and/or extents over time. Examples include traffic
    surveillance data, climate and land cover data, demographic data and
    multimedia applications (animated movies). Since these databases
    are large in size, it is important to design efficient indexing
    schemes that can access and explore this data. The queries of interest
    are range queries of the form: "find the objects that were in area
    $S$ between time instants $t_i$ and $t_j$", as well as nearest neighbor
    queries like: "find the $q$ nearest objects to a given position between
    time instants $t_i$ and $t_j$". We first reduce the problem to
    a partial-persistence problem, that is, we use a 2-dimensional access
    method that is made partially persistent. We show that this approach
    leads to fast query time while still using space proportional to the
    total number of changes in the spatiotemporal evolution. What
    differentiates this problem from traditional temporal indexing
    approaches is that objects are allowed to move and/or change their
    extent continuously over time. We present novel methods to approximate
    such objects. We formulate the problem as an optimization problem
    for which we provide an optimal solution for the case where objects
    move linearly. An extensive experimental study demonstrates the
    advantages of our approach over other straightforward solutions.
    While the above discussion concentrates on historical queries
    (past states) of spatiotemporal data, of interest are also queries
    about the future behavior of such data (assuming that the
    movement/change functions are known). If time permits, we will present 
    new results for such queries as well.


    Host:  Azer Bestavros (best@cs.bu.edu)

-------------------------------------------------------------------------------
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------------