-------------------------------------------------------------------------------
                                       
                                       
		   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
                                       
                     Fast Algorithms for Spatial and
                         Multidimensional Joins

                              Nick Koudas
                     Department of Computer Science
                          University of Toronto

	                 Wednesday, February 18th
                                       
			        11:00pm 
		       (Coffee served at 10:30pm)

                                       
			 Seminar Room / MCS 135
                                       

-------------------------------------------------------------------------------

       Since the introduction of the relational model of data,  the
       join  operation   has   received  much  attention due to its
       unique  feature  of   combining    data    from    different
       relations.     As    Database  Management   Systems   become
       richer  in  data  types,   there  is increasing interest  to
       extend  the   join   operation   to   new  data types,  like
       geographical or spatial and multimedia data.
       
       In this talk, we first present an overview of  work  in  the
       area  of  spatial and multimedia queries.  We then introduce
       a new algorithm to compute the  spatial  join   of   two  or
       more   spatial   data  sets,  when indexes are not available
       on  them.    Size   Separation   Spatial    Join    (S^{3}J)
       imposes   a hierarchical  decomposition  of  the  data space
       and, in contrast  with  previous  approaches,  requires   no
       replication   of   entities from  the  input data sets. Thus
       its performance is a function of the original  size  of  the
       joined data sets.
       
       We  describe  S^{3}J   and   present   an   analytical   and
       experimental   evaluation   of    its  I/O   and   processor
       requirements  comparing   them   with  those  of  previously
       proposed  algorithms for the  same  problem. In addition, we
       introduce Dynamic Spatial Bitmaps  (DSB),  a  new  technique
       that  enables  S^{3}J  to  dynamically or statically exploit
       bitmap query processing techniques.
       
       We conclude by discussing generalizations of S^{3}J in order
       to apply to other data types.


Host: Wayne Snyder (snyder@cs.bu.edu)

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