Spatial clustering in the presence of obstacles

A. K H Tung, J. Hou, Jiawei Han

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


Clustering in spatial data mining is to group similar objects based on their distance, connectivity, or their relative density in space. In the real world, there exist many physical obstacles such as rivers, lakes and high-ways, and their presence may affect the result of clustering substantially. In this paper, we study the problem of clustering in the presence of obstacles and define it as a COD (Clustering with Obstructed Distance) problem. As a solution to this problem, we propose a scalable clustering algorithm, called COD-CLARANS. We discuss various forms of pre-processed information that could enhance the efficiency of COD-CLARANS. In the strictest sense, the COD problem can be treated as a change in distance function and thus could be handled by current clustering algorithms by changing the distance function. However, we show that by pushing the task of handling obstacles into COD-CLARANS instead of abstracting it at the distance function level, more optimization can be done in the form of a pruning function E′. We conduct various performance studies to show that COD-CLARANS is both efficient and effective.

Original languageEnglish (US)
Title of host publicationProceedings - International Conference on Data Engineering
Number of pages9
StatePublished - 2001
Externally publishedYes
Event17th International Conference on Data Engineering - Heidelberg, Germany
Duration: Apr 2 2001Apr 6 2001


Other17th International Conference on Data Engineering

ASJC Scopus subject areas

  • Software
  • Engineering(all)
  • Engineering (miscellaneous)


Dive into the research topics of 'Spatial clustering in the presence of obstacles'. Together they form a unique fingerprint.

Cite this