Several GIS applications are characterized by the vast amount of information that needs to be stored, retrieved and analyzed. In addition to just being able to handle these large data sets, a GIS should also be able to perform queries on this data efficiently to meet certain real-time constraints. As a result, there are three main requirements for a GIS to be successful in handling the demands of current and emerging applications:
1. The GIS must be able to store large data sets.
2. The GIS must be able to store, retrieve and process these large data sets efficiently.
3. The GIS must provide low response times and high throughput for complex queries on the data sets.
Focussing specifically on the R-Tree, a common data structure used to store spatial information, we have proposed different techniques for distributing this data structure across the workstations of a NOW platform. We have implemented a client-server architecture to evaluate these distribution strategies experimentally on a cluster of UltraSPARC model 170 workstations connected by Ethernet and Myrinet. Using this framework, we have experimentally studied the performance of two distribution schemes and shown that there can be significant performance improvements with the use of parallelism for inserts and spatial search operations.