Development of Multi-step Filtering Processor.

@inproceedings{DBLP:conf/dasfaa/KimLK99,
  author    = {Miyeon Kim and
               Sumi Lim and
               Jangsu Kim},
  editor    = {Arbee L. P. Chen and
               Frederick H. Lochovsky},
  title     = {Development of Multi-step Filtering Processor},
  booktitle = {Database Systems for Advanced Applications, Proceedings of the
               Sixth International Conference on Database Systems for Advanced
               Applications (DASFAA), April 19-21, Hsinchu, Taiwan},
  publisher = {IEEE Computer Society},
  year      = {1999},
  isbn      = {0-7695-0084-6},
  pages     = {169-176},
  ee        = {db/conf/dasfaa/KimLK99.html},
  crossref  = {DBLP:conf/dasfaa/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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 © 1999 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD DiSC

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Online Edition: IEEE Computer Society Digital Library

References

[1]

Andrew U. Frank: Properties of Geographic Data: Requirements for Spatial Access Methods. SSD 1991: 225-234 BibTeX

[2]

Won Kim (Ed.): Modern Database Systems: The Object Model, Interoperability, and Beyond. ACM Press and Addison-Wesley 1995, ISBN 0-201-59098-0
Contents BibTeX

[3]

Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider: Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems. ICDE 1993: 40-49 BibTeX

[4]

Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
BibTeX

[5]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX

[6]

Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 BibTeX

[7]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[8]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

[9]

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX

[10]

Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305 BibTeX

[11]

...

[12]

Oliver Günther: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989: 598-605 BibTeX

[13]

H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319 BibTeX

[14]

Thomas Brinkhoff, Hans-Peter Kriegel: Approximations for a Multi-Step Processing of Spatial Joins. IGIS 1994: 25-34 BibTeX

[15]

Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208 BibTeX