Efficient polygon amalgamation methods for spatial OLAP and spatial data mining

Xiaofang Zhou, David Truffet, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The polygon amalgamation operation computes the boundary of the union of a set of polygons. This is an important operation for spatial on-line analytical processing and spatial data mining, where polygons representing different spatial objects often need to be amalgamated by varying criteria when the user wants to aggregate or reclassify these objects. The processing cost of this operation can be very high for a large number of polygons. Based on the observation that not all polygons to be amalgamated contribute to the boundary, we investigate in this paper efficient polygon amalgamation methods by excluding those internal polygons without retrieving them from the database. Two novel algorithms, adjacency-based and occupancy-based, are proposed. While both algorithms can reduce the amalgamation cost significantly, the occupancy-based algorithm is particularly attractive because: 1) it retrieves a smaller amount of data than the adjacency-based algorithm; 2) it is based on a simple extension to a commonly used spatial indexing mechanism; and 3) it can handle fuzzy amalgamation.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial Databases - 6th International Symposium, SSD 1999, Proceedings
EditorsRalf Hartmut Guting, Dimitris Papadias, Fred Lochovsky
Number of pages21
ISBN (Print)3540662472, 9783540662471
StatePublished - 1999
Externally publishedYes
Event6th International Symposium on Spatial Databases, SSD 1999 - Hong Kong, China
Duration: Jul 20 1999Jul 23 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other6th International Symposium on Spatial Databases, SSD 1999
CityHong Kong


  • On-line analytical processing (OLAP)
  • Polygon amalgamation
  • Spatial databases
  • Spatial indexing

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Efficient polygon amalgamation methods for spatial OLAP and spatial data mining'. Together they form a unique fingerprint.

Cite this