Object decomposition for spatial query processing

Abstract

Efficient query processing for complex spatial objects is one of the most challenging requirements in non-traditional applications such as geographic information systems, computer-aided design, and multimedia databases. The performance of spatial query processing can be improved by decomposing a complex object into a small number of simple components. This paper investigates the natural trade-off between the number and the complexity of decomposed components. In particular, we propose a new object decomposition method that can control the number of components using a parameter. This method enables the user to select the optimal trade-off by controlling the parameter. The proposed method is compared with traditional decomposition methods by an analytical study and experimental measurements. These comparisons show that our decomposition method outperforms traditional decomposition methods. A spatial query processor based on object decomposition is implemented as a SHORE Value Added Server (VAS) directly on top of the SHORE Storage Manager (SSM). The goal in developing the query processor is to implement a sub- system that efficiently supports a well-chosen set of spatial queries. These spatial queries serve as a basis for implementing other more sophisticated operations required in special applications. Spatial queries that we implemented are the point query, region query, spatial join query, nearest neighbor query, and insert query. An efficient implementation of these basic spatial queries is the most important for good overall performance of the spatial query processor. We provide analytical formulas that predict the performance of the spatial query processor. The major contribution of our analysis is the refinement step analysis. In contrast to several earlier investigations on this subject, we take into account the analytical formulas that predict the performance of the refinement step, since the refinement step exerts critical influence on the performance...