CLARANS: A method for clustering objects for spatial data mining

Raymond T. Ng, Jiawei Han

Research output: Contribution to journalArticlepeer-review


Spatial data mining is the discovery of interesting relationships and characteristics that may exist implicitly in spatial databases. To this end, this paper has three main contributions. First, we propose a new clustering method called CLARANS, whose aim is to identify spatial structures that may be present in the data. Experimental results indicate that, when compared with existing clustering methods, CLARANS is very efficient and effective. Second, we investigate how CLARANS can handle not only points objects, but also polygon objects efficiently. One of the methods considered, called the IR-approximation, is very efficient in clustering convex and nonconvex polygon objects. Third, building on top of CLARANS, we develop two spatial data mining algorithms that aim to discover relationships between spatial and nonspatial attributes. Both algorithms can discover knowledge that is difficult to find with existing spatial data mining algorithms.

Original languageEnglish (US)
Pages (from-to)1003-1016
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number5
StatePublished - Sep 2002
Externally publishedYes


  • Clustering algorithms
  • Computational geometry
  • Randomized search
  • Spatial data mining

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'CLARANS: A method for clustering objects for spatial data mining'. Together they form a unique fingerprint.

Cite this