Spatial data structures and algorithms for large scale applications

In this thesis, we develop spatial data structures and algorithms for two broad classes of applications---forest growth models and range searching.; Forest growth model. We have developed an individual-based, spatially-explicit forest growth model. Our model is highly realistic and is quite complex compared to most forest models. Our forest model allows for many sources of variability and uncertainty that characterize processes and data. To perform efficient simulation, we balance accuracy against the stochasticity inherent in data and process. Based on this approach, we have developed efficient data structures and algorithms for calculating dispersal and light.; We have developed a quad-tree based data structure to represent the trees in the forest. Based on this data structure, we have developed a monopole-based approximation algorithm to compute dispersal. This yields an efficiency-accuracy tradeoff scheme. Experimental results show a speedup of about an order of magnitude for reasonable error. We have performed experiments to evaluate the stochasticity in the dispersal model. Results show that the stochasticity is at least an order of magnitude greater than computational error, thus justifying approximation. We also provide experimental results that provide guidelines for choosing the monopole constant. We have performed ecological experiments using model simulations to evaluate various mechanisms that affect biodiversity.; Range searching. We have developed data structures for answering two types of orthogonal range queries---range aggregate query and colored range query.; We have developed an efficient indexing scheme, Compressed Range Tree (CRB-tree) for answering range aggregate queries. For count queries in 2D, the CRB-tree is linear in size and can answer queries using logarithmic I/Os. Our index can be extended to handle SUM aggregate as well. We also show how to dynamize our index and extend it to higher dimensions. We demonstrate the efficacy of our data structure by comparing its performance with kdB-tree.; We develop efficient indices to answer colored range searching queries on a grid. (Abstract shortened by UMI.)...