Date: Fri 25 Sep
Time: 15.00
Place: room 214

Speaker: Dr. Gisli Runar Hjaltason (Maryland Univ.)
Title: Incremental Algorithms for Distance-Based Spatial Operations
Reference: Paola Magillo

Abstract. Many modern database applications demand the ability to handle spatial data. Examples of areas where this need arises include geographical information systems (GIS), multimedia databases, spatial data mining, and CAD/CAM. A common class of queries for such data involves spatial proximity, for example, "find the city closest to the Grand Canyon" and "find the store closest to a warehouse". The first example involves one object collection, cities, whereas the second query joins together two object collections, stores and warehouses. Queries often contain some other conditions, in addition to the proximity criterion. For example, the queries "find the city closest to the Grand Canyon with more than 1 million inhabitants" and "find the store closest to a warehouse that stocks hardware supplies" have secondary conditions involving non-spatial attributes. In my talk, I will discuss algorithms that enable us to efficiently answer these kinds of queries. The algorithms are incremental and aim to deliver their result as soon a possible, so they can be used by a query engine in a pipelined manner. Such "fast-first" pipelined algorithms are important for interactive query interfaces as they make it possible to quickly give the user some response to their query.