Organizing and Indexing Non-Convex Regions

The authors demonstrate data indexing and query processing techniques that improve the efficiency of comparing, correlating, and joining data contained in non-convex regions. They use computational geometry techniques to automatically characterize the region of space from which data are drawn, partition the region based on that characterization, and create an index from the partitions. Their motivating application performs distributed data analysis queries among federated database sites that store scientific data sets from the Chesapeake Bay. Their preliminary findings indicate that these techniques often reduce the number of I/Os needed to serve a query by a factor of five-depending on the geometry of the query region.