Early Separation of Filter and Refinement Steps in Spatial Query Optimization.

@inproceedings{DBLP:conf/dasfaa/ParkLLC99,
  author    = {Ho-Hyun Park and
               Chan-Gun Lee and
               Yong-Ju Lee and
               Chin-Wan Chung},
  editor    = {Arbee L. P. Chen and
               Frederick H. Lochovsky},
  title     = {Early Separation of Filter and Refinement Steps in Spatial Query
               Optimization},
  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     = {161-168},
  ee        = {db/conf/dasfaa/ParkLLC99.html},
  crossref  = {DBLP:conf/dasfaa/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The spatial query has been processed in two steps, the filter step and the refinement step, due to a large volume and high complexity of the spatial data. However, this approach has been considered only in the query execution phase after completing the query optimization phase. This paper presents query optimization strategies which take the characteristics of spatial databases into account. The first strategy is the separation of filter and refinement steps not in the query execution phase but in the query optimization phase.

As the second strategy, several refinement operations can be combined in processing a complex query, and as the third strategy several filter operations can also be combined. We call the optimization technique utilizing these strategies the Early Separated Filter And Refinement (ESFAR). This paper also presents a rule-based optimization technique for ESFAR.

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]

Walid G. Aref, Hanan Samet: Optimization for Spatial Query Processing. VLDB 1991: 81-90 BibTeX

[2]

Ludger Becker, Ralf Hartmut Güting: Rule-Based Optimization and Query Processing in an Extensible Geometric Database System. ACM Trans. Database Syst. 17(2): 247-303(1992) BibTeX

[3]

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

[4]

Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX

[5]

Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 BibTeX

[6]

Wan-Sup Cho, Seung-Sun Lee, Kyu-Young Whang, Yong-Ik Yoon: Query Optimization Techniques Utilizing Path Indexes in Object-Oriented Database Systems. DASFAA 1997: 21-29 BibTeX

[7]

Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218 BibTeX

[8]

Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner: Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations. VLDB 1997: 396-405 BibTeX

[9]

C. Mohan, Donald J. Haderle, Yun Wang, Josephine M. Cheng: Single Table Access Using Multiple Indexes: Optimization, Execution, and Concurrency Control Techniques. EDBT 1990: 29-43 BibTeX

[10]

Beng Chin Ooi, Ron Sacks-Davis, Ken J. McDonell: Extending a DBMS for Geographic Applications. ICDE 1989: 590-597 BibTeX

[11]

Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX

[12]

...

[13]

...

[14]

Hanan Samet, Walid G. Aref: Spatial Data Models and Query Processing. Modern Database Systems 1995: 338-360 BibTeX

[15]

Abraham Silberschatz, Henry F. Korth, S. Sudarshan: Data Models. The Computer Science and Engineering Handbook 1997: 979-994 BibTeX

[16]

Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX