Efficient algorithms for spatial queries

Efficient query evaluation is an important issue in spatial databases, constraint databases, and geographical information systems. Spatial region search and spatial joins are two basic operations in these systems. In our study, we focus on evaluation of spatial queries using alternative approximations and efficient evaluation of spatial joins with different predicates.The traditional spatial query evaluation strategy is to perform spatial query on "minimum bounding rectangles" (MBRs) of the spatial objects (MBR-filter), and apply query on the actual spatial objects only when their MBRs satisfy the query condition (refinement). Unfortunately, MBRs are very coarse approximations and may only filter out a small number of "false results". To improve performance of spatial query evaluation, we propose to use finer approximations for the filter.We first introduce a general framework for efficient evaluation of spatial joins using finer approximations than MBRs. The core of the framework is the evaluation of join of two sets of trapezoids. Approximations that are bounded unions of trapezoids can first be decomposed into trapezoids, and then filters using these approximations can be constructed with the trapezoid join algorithm.We then focus on a new approximation method, "minimum bounding octagon" (MBO). We develop a new index structure, "Octagon Tree" (O-Tree) for MBOs and show by experiments that O-Trees outperform R*-trees for spatial point, line, and window searches and spatial joins. An important extension of MBOs and O-Trees is developed for evaluation of trajectory queries. A new index structure, Octagon-Prism tree (OP-Tree), is extended from O-Tree and experiments show that OP-Trees outperform MBR-based index structures.For spatial join evaluation, we study spatial queries with "region intersection" predicate and direction predicates ("direction join"). For the former, we use filters with finer approximations to improve the overall performance. For the latter, we develop efficient algorithms by combining the plane-sweeping technique with external priority search trees. In addition, we study direction joins with multiple relations and show that, although evaluating the general case is NP-hard, special cases such as "star joins" and bounded cases of "tree joins" can be in polynomial I/Os.