Digital Symposium Collection 2000

Development of Multi-step Filtering Processor Miyeon Kim, Sumi Lim, and Jangsu Kim   View Paper (PDF)   Return to Session 3B: Spatial Databases Abstract Spatial query processing using a Spatial Access Method (SAM) faces the problem of having to examine a large number of candidate objects during the CPU-time intensive refinement step. This is due to the Minimum Bounding Rectangle (MBR) filter in the first step of query processing which is rough by nature. In order to overcome these problem, the multi-step filtering method that takes a series of spatial filters with higher filtering ratios than that of the MBR in a cascade fashion for the object set already filtered by an MBR has been introduced. Most of the spatial filters were only able to manage areal objects. In this paper, we propose the Minimum Maximum Points (MMP) filter, a spatial filter that can manage not only areal objects but also linear objects. In addition, we propose a multi-step filtering processor using the MMP filter, which is designed for well-known spatial operator respectively. We also show the superiority of our multi-step filtering by extensive experiments. Copyright(C) 2000 ACM