9216970 Samet Spatial Query Processing: A Sorting Approach This is the first year funding of a three-year continuing award. An investigation is being conducted into the efficient processing of spatial data as arising in problems involving scientific data. Instead of using standard database methods which represent spatial data as points in a higher dimensional space, and then storing the coordinate values in a relation (equivalent to mapping the data into points in a higher dimensional space), the data is organized by sorting it in such a way that the space it occupies is taken into account. Particular attention is focused on the spatial variant of the range query. Algorithms for such queries are being developed in the context of spatial data corresponding to road networks and topography both above ground and underwater (represented both as contour lines and surfaces). Their performance is being evaluated by examining factors such as buffer utilization, page sizes, page faults, data distribution, etc. in environments where the data is spatially sorted and where it is not. The evaluation is in terms of real data obtained by cooperating with the US Bureau of the Census and the US Geological Survey. This information is being used to pinpoint where the algorithms can be improved. Appropriate models for generating the queries rather than the underlying database (which consists of real data) are also being investigated. ***
