Online query processing in Geographic Information Systems

Geographic Information Systems (GIS) have been widely used in many applications for exploring large georeferenced data. With the recent advances in Internet technologies, a large volume of GIS data is available on the Web. As a result, an increasing number of emerging applications began to provide tools for accessing these data. However, exploring georeferenced data can be very time-consuming due to the large size of the data. Current query processing techniques deal with spatial queries in a blocking manner and hence, may not be directly applicable for data analysis in GIS. This problem is more pronounced in decision support queries where query response time is a critical issue. Since these queries are mostly used to get a "big picture" of data sets and their relationships, a more useful and effective approach is to provide approximate query answers quickly and in an interactive manner. In this way, users can obtain an idea of how the query result would look like and can therefore stop/modify the query accordingly. Another issue related to online query processing is the limited access to Web data by certain types of queries due to restrictive Web interfaces. This problem hinders online data retrieval, which necessitates for methods that utilize certain query types to provide solutions to non-supported queries.;This dissertation studies technical, practical and theoretical issues raised in designing and implementing online query processing in GIS and provides techniques for interactive spatial joins and efficient Web data retrieval. We present a family of interactive spatial join algorithms that report incrementally refined running estimates for aggregate queries over vector data, while simultaneously displaying the actual query result tuples of the data sets sampled so far. We also present a new framework for raster data joins that allows users to get approximate answers in near instantaneous time for more interactive data exploration. Both solutions to online query processing for vector and raster data provide orders of magnitude improvement of response time over traditional GIS spatial joins. Finally, we conceptualize the online data retrieval problem as a more general problem of solving spatial range queries using only k-Nearest Neighbor (k-NN) queries. Consequently, based on the classification of k-NN interfaces on the Web, we propose a set of range query algorithms to completely cover the rectangular shape of a spatial range query while minimizing the number of k-NN queries.