skip to main content
10.1145/1183471.1183503acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
Article

Filtering with raster signatures

Published: 10 November 2006 Publication History

Abstract

Efficient evaluation of spatial queries is an important issue in spatial database. Among spatial operations, spatial join is very useful, intersection being the most common predicate. However, the exact intersection test of two spatial objects is the most time-consuming and I/O-consuming step in processing spatial joins. On the other hand, the use of approximations can reduce the need for examining the exact geometry of spatial objects in order to find the intersecting ones. This work proposes a new raster approximation (Three-Color Raster Signature - 3CRS) for representing different data types (polygons, polylines and points), and to be used as filter in the second step of the Multi-Step Query Processor. We have also executed experimental tests over real datasets, the results having demonstrated the effectiveness of our approach.

References

[1]
Aronoff, S. Geographic Information Systems, 1 ed., WDL Publications, Ottawa, Canada, 1989.
[2]
Beckmann, N., Kriegel, H. P., Schneider, R., and Seeger, B. The R*tree: An Efficient and Robust Access Method for Points and Rectangles. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data (Atlantic City, NJ, USA, May 23-25, 1990), ACM Press, New York, NY, 1990, 322--331.
[3]
Boissonnat, J. D., and Preparata, F. P. Robust Plane Sweep for Intersecting Segments, SIAM Journal on Computing, 1997, v. 29, issue 5, 1401--1421.
[4]
Brazilian Institute of Geography and Statistics Fundação Instituto Brasileiro de Geografia e Estatística -- IBGE: "Malha Municipal Digital do Brasil - 1994", Rio de Janeiro, 1996.
[5]
Brinkhoff, T., Kriegel, H. P., and Schneider, R. Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems. In Proceedings of Ninth International Conference on Data Engineering (ICDE'93) (Vienna, Austria, April 19-23, 1993), IEEE Computer Society, Washington, DC, USA, 1993, 40--49
[6]
Brinkhoff, T., Kriegel, H. P., Schneider, R., and Seeger, B. Multi-step Processing of Spatial Joins. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data (Minneapolis, Minneapolis, Minnesota, USA, May 24-27, 1994) ACM Press New York, NY, USA, 1994, 197--208.
[7]
Freiseisen W., and Pau, P. A generic plane-sweep for intersecting line segments, Technical Report RISC-Linz TR-98-18, University of Linz, Linz, Austria, 1998.
[8]
Gordon, S. R.,Goodwin, C.W.H., and Xiong, D. Final Report on Status of Spatial/Map Databases. Technical Report of Oak Ridge National Laboratory, June, 1994.
[9]
Güting, R.H., Almeida, V., Ansorge, D., Behr, T., Ding, Z., Höse, T., Hoffmann, F., Spiekermann, M., and Telle, U. Secondo: An Extensible DBMS Platform for Research Prototyping and Teaching, In Proceedings of 21st International Conference. on Data Engineering (ICDE'05) (Tokyo, Japan, April 5-8, 2005), IEEE Computer Society Washington, DC, USA, 1115--1116.
[10]
Kothuri, R. K., and Ravada, S. Efficient Processing of Large Spatial Queries Using Interior Approximations. In Proceedings of the 7th International Symposium on Spatial and Temporal Databases (SSTD'01), (Redondo Beach, CA, USA, July 12-15, 2001) Springer-Verlag London, UK, 2001, 404--424.
[11]
Newman, W. M., and Sproull, R. F. Principles of Interactive Computer Graphics, 2 ed., McGraw-Hill Book Company, New York, 1979.
[12]
Orenstein, J. A. Spatial query processing in an object-oriented database system. In Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, (Washington, DC, USA, May 28-30, 1986) ACM Press, New York, NY, USA, 1986, 326--336.
[13]
Samet, H.The Design and Analysis of Spatial Data Structure, 1 ed., Addison-Wesley Publishing Company, Boston, Massachusetts, 1990.
[14]
Tao, Y., Sun, J., and Papadias, D. Selectivity estimation for predictive spatio-temporal queries. In Proceedings of the 19th International Conference on Data Engineering (ICDE'03) (Bangalore, India, March 5-8, 2003) IEEE Computer Society, 2003, 417--428.
[15]
Zimbrao, G., and Souza, J. M. A Raster Approximation For Processing of Spatial Joins. In Proceedings of the 24th International Conference on Very Large Databases (VLDB'98) (New York City, NY, USA, August 24-27, 1998) Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 558--569.
[16]
Zhu, H., Su, J., and Ibarra, O. H. Toward Spatial Joins for Polygons. In Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00) (Berlin, Germany, July 26-28, 2000) IEEE Computer Society Washington, DC, USA, 2000, 231--244.

Cited By

View all
  • (2023)SGPAC: generalized scalable spatial GroupBy aggregations over complex polygonsGeoInformatica10.1007/s10707-023-00491-827:4(789-816)Online publication date: 21-Mar-2023
  • (2020)Scalable Spatial GroupBy Aggregations Over Complex PolygonsProceedings of the 28th International Conference on Advances in Geographic Information Systems10.1145/3397536.3422222(449-452)Online publication date: 3-Nov-2020
  • (2012)An interactive framework for spatial joinsGeoinformatica10.1007/s10707-011-0134-716:2(329-355)Online publication date: 1-Apr-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GIS '06: Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems
November 2006
264 pages
ISBN:1595935290
DOI:10.1145/1183471
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 November 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. GIS
  2. four-colors raster signature
  3. multi-step query processor
  4. raster approximation
  5. spatial databases
  6. spatial join
  7. three-colors raster signature

Qualifiers

  • Article

Conference

CIKM06
Sponsor:
CIKM06: Conference on Information and Knowledge Management
November 10 - 11, 2006
Virginia, Arlington, USA

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)SGPAC: generalized scalable spatial GroupBy aggregations over complex polygonsGeoInformatica10.1007/s10707-023-00491-827:4(789-816)Online publication date: 21-Mar-2023
  • (2020)Scalable Spatial GroupBy Aggregations Over Complex PolygonsProceedings of the 28th International Conference on Advances in Geographic Information Systems10.1145/3397536.3422222(449-452)Online publication date: 3-Nov-2020
  • (2012)An interactive framework for spatial joinsGeoinformatica10.1007/s10707-011-0134-716:2(329-355)Online publication date: 1-Apr-2012
  • (2007)An interactive framework for raster data spatial joinsProceedings of the 15th annual ACM international symposium on Advances in geographic information systems10.1145/1341012.1341018(1-8)Online publication date: 7-Nov-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media