| This thesis presents a number of techniques to manage spatial and temporal data for range search and related problems. The main contributions cover three areas: geometric retrieval, temporal range queries, and range queries for large-scale raster data. Algorithms with provably good performance for important problems in each of these areas are described.; Our fast geometric retrieval algorithms are based on an improved version of the standard fractional cascading structure for a special class of catalog trees. We apply this new technique to obtain O(n )-space and O(log n/log log n + f)-query time algorithms for the orthogonal segment intersection problem and the rectangular point, enclosure problem, where n is the size of the data set and f is the output size. These algorithms are faster than the best previously known algorithms while maintaining linear-space. We also present the fastest algorithms for the dominance reporting and counting problems.; We introduce in this thesis a new framework for handling temporal range queries. Given a set of n objects, each characterized by d attributes whose values are observed at different time instances, a temporal range query looks for the sub set of objects whose values fall within a specified value ranges during each of the time instances in a given time interval. We develop probably good algorithms for both synchronous data (time-series data, which are collected at fixed sequences of time instances for all the objects, and asynchronous data, which may arrive at different rates and need to be dynamically incorporated as they are made available.; The last part of the thesis deals with the problem of organizing raster data to efficiently handle queries for identifying regions, rather than individual cells, whose parameters fall within certain value ranges. We focus on data structures and algorithms that minimize the I/O complexity, and obtain a linear-space data structure, which involves a combination of an R-tree and efficient representation of regions and enables the identification of connected regions that satisfy the query ranges very quickly. |
