| Separability of Polyhedra and a New Approach to Spatial Storage (Extended Abstract) | |||||||||||||||
Abstract | |||||||||||||||
| ) Alexander Brodsky Catherine Lassez I.B.M. Thomas J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598 Efficient storage and access methods for large amounts of spatial objects are key issues in Geographic Information Systems (GIS), Computer Aided Design (CAD), VLSI design and also Linear Constraint Databases (LCDBs) [BJM92], a new application domain in which objects are convex multidimensional polyhedra represented as conjunctions of linear constraints over real variables. Typically, the first step of query processing is the filtering out of irrelevant information. We propose a new filtering method which is based on pre-evaluation of projections of objects (polyhedra) on a number of selected axes. We are concerned with how to achieve any desired quality of filtering by selecting (a minimum number of) optimal axes, while keeping storage overhead low. Filtering in Spatial Queries Typical spatial queries deal with intersection and containment of objects. For example, given... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||