| Due to the interactive nature of the applications and the complexity of the data, spatial databases face some unique challenges compared to more traditional DBMS. As part of the Alexandria Digital Library Project, our work addresses some of these challenges with a focus on efficient access of large spatial datasets. At the collection level, we develop three approximation algorithms based on the Euler Histogram, and for the first time enable users to quickly browse a spatial dataset with a variety of spatial relations. In addition to browsing, we also generalize the Euler Histogram to provide accurate selectivity estimation for spatial joins. At the object level, we propose a novel approach to accelerate spatial operations using the highly optimized rendering and searching capabilities of modern graphics hardware. Experiments with real world datasets show that by combining hardware and software methods, the overall computational cost can be reduced substantially for both spatial selections and joins. |
