Clustering Algorithms for Spatial Databases: A Survey
Published 1 January 2001
Erica Kolatch
Citations87
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Introduction Spatial Database Systems (SDBS) are database systems designed to handle spatial data and the non-spatial information used to identify the data. SDBS are used for everything from geo-spatial data to bio-medical knowledge and the number of such databases and their uses are increasing rapidly. The amount of spatial data being collected is also increasing exponentially. The complexity of the data contained in these databases means that it is not possible for humans to completely analyze the data being collected. Data mining techniques have been used with relational databases to discover unknown information, searching for unexpected results and correlations. Extremely large databases require new techniques to analyze the data and discover these patterns. Traditional search algorithms can still answer questions about specific pieces of information, but traditional techniques are no longer capable of performing searches for previously unknown patterns in the data. The re
Keywords
Computer Science
A density-based algorithm for discovering clusters in large spatial Databases with Noise
19,114 Citations1996Martin Ester, Hans‐Peter Kriegel +2 more
DBSCAN, a new clustering algorithm relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape, is presented which requires only one input parameter and supports the user in determining an appropriate value for it.
Choice Reviews OnlineFinding groups in data: an introduction to cluster analysis
10,614 Citations1991
BIRCH
3,906 Citations1996Tian Zhang, Raghu Ramakrishnan +1 more
A data clustering method named BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) is presented, and it is demonstrated that it is especially suitable for very large databases.
Automatic subspace clustering of high dimensional data for data mining applications
2,386 Citations1998Rakesh Agrawal, Johannes Gehrke +2 more
CLIQUE is presented, a clustering algorithm that satisfies each of these requirements of data mining applications including the ability to find clusters embedded in subspaces of high dimensional data, scalability, end-user comprehensibility of the results, non-presumption of any canonical data distribution, and insensitivity to the order of input records.
ComputerChameleon: hierarchical clustering using dynamic modeling
2,102 Citations1999George Karypis, Eui-Hong Han +1 more
Chameleon's key feature is that it accounts for both interconnectivity and closeness in identifying the most similar pair of clusters, which is important for dealing with highly variable clusters.
CURE
1,909 Citations1998Sudipto Guha, Rajeev Rastogi +1 more
This work proposes a new clustering algorithm called CURE that is more robust to outliers, and identifies clusters having non-spherical shapes and wide variances in size, and demonstrates that random sampling and partitioning enable CURE to not only outperform existing algorithms but also to scale well for large databases without sacrificing clustering quality.
Efficient and Effective Clustering Methods for Spatial Data Mining
1,788 Citations1994Raymond T. Ng, Jiawei Han
The analysis and experiments show that with the assistance of CLAHANS, these two algorithms are very effective and can lead to discoveries that are difficult to find with current spatial data mining algorithms.
STING: A Statistical Information Grid Approach to Spatial Data Mining
1,224 Citations1997Wei Wang, Jiong Yang +1 more
The idea is to capture statistical information associated with spatial cells in such a manner that whole classes of queries and clustering problems can be answered without recourse to the individual objects.
KOPS (University of Konstanz)An efficient approach to clustering in large multimedia databases with noise
1,168 Citations1998Alexander Hinneburg, Daniel A. Keim
A new algorithm to clustering in large multimedia databases called DENCLUE (DENsity-based CLUstEring) is introduced, which has a firm mathematical basis, has good clustering properties in data sets with large amounts of noise, allows a compact mathematical description of arbitrarily shaped clusters in high-dimensional data sets and is significantly faster than existing algorithms.
WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases
753 Citations1998Gholamhosein Sheikholeslami, Surojit Chatterjee +1 more
WaveCluster is proposed, a novel clustering approach based on wavelet transforms which can effectively identify arbitrary shape clusters at different degrees of accuracy and is highly efficient in terms of time complexity.
Lecture notes in computer science3D Shape Histograms for Similarity Search and Classification in Spatial Databases
518 Citations1999Mihael Ankerst, Gabi Kastenmüller +2 more
3D shape histograms are introduced as an intuitive and powerful similarity model for 3D objects that efficiently supports similarity search based on quadratic forms and has high classification accuracy and good performance.
A distribution-based clustering algorithm for mining in large spatial databases
346 Citations2002Xiaowei Xu, Martin Ester +2 more
The new clustering algorithm DBCLASD (Distribution-Based Clustering of LArge Spatial Databases) is introduced to discover clusters of this type and is very attractive when considering its nonparametric nature and its good quality for clusters of arbitrary shape.
KOPS (University of Konstanz)Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering
336 Citations1999Alexander Hinneburg, Daniel A. Keim
A new clustering technique called OptiGrid is developed which is based on constructing an optimal grid-partitioning of the data and has a mathematical basis which is by far more e ectiveness andiency than existing clustering algorithms for highdimensional data.
Lecture notes in computer scienceSpatial data mining: A database approach
245 Citations1997Martin Ester, Hans‐Peter Kriegel +1 more
A set of basic operations which should be supported by a spatial database system (SDBS) to express algorithms for KDD in SDBS are introduced and it is argued that these operations are sufficient for K DD algorithms considering spatial neighborhood relations.
Lecture notes in computer scienceKnowledge discovery in large spatial databases: Focusing techniques for efficient class identification
160 Citations1995Martin Ester, Hans‐Peter Kriegel +1 more
This paper addresses the task of class identification in spatial databases using clustering techniques using a well-known spatial access method, the R*-tree, and presents several strategies for focusing: selecting representatives from a spatial database, focusing on the relevant clusters and retrieving all objects of a given cluster.
Discovery of General Knowledge in Large Spatial Databases.
125 Citations1993Wei Lu, Jungang Han +1 more
The study shows that knowledge discovery has wide applications in spatial databases, and relatively efficient algorithms can be developed for discovery of general knowledge in large spatial databases.
Algorithms for characterization and trend detection in spatial databases
120 Citations1998Martin Ester, Alexander Frommelt +2 more
This paper presents new algorithms for spatial characterization and spatial trend analysis, implemented within a general framework for spatial data mining providing a small set of database primitives on top of a commercial spatial database management system.
A spatial data mining method by Delaunay triangulation
71 Citations1997In-Soo Kang, Tae‐Wan Kim +1 more
This paper presents a spatial data mining method named SMiYN (Spatial data Mining by Triangulated Irregular Network), which is based on Delaunay Triangulation, and demonstrates important advantages over the previous works.
STING+: an approach to active spatial data mining
62 Citations1999Wei Wang, Jiong Yang +1 more
This paper introduces an active spatial datamining approach which extends the current spatial data mining algorithms to efficiently support user-defined triggers on dynamically evolving spatial data and employs a hierarchical structure with associated statistical information at the various levels of the hierarchy to exploit the locality of the effect of an update and the nature of spatial data.
Lecture notes in computer scienceKnowledge Discovery in Spatial Databases
55 Citations1999Martin Ester, Hans‐Peter Kriegel +1 more
A small set of database primitives are defined, and it is demonstrated that typical spatial KDD algorithms are well supported by the proposeddatabase primitives, and the effectiveness and efficiency of the approach are shown.
Lecture notes in computer scienceEfficient Polygon Amalgamation Methods for Spatial OLAP and Spatial Data Mining
42 Citations1999Xiaofang Zhou, David Truffet +1 more
Efficient polygon amalgamation methods by excluding those internal polygons without retrieving them from the database are investigated, and two novel algorithms, adjacency-based and occupancy-based, are proposed.
Modelling spatial dependencies for mining geospatial data
30 Citations2010Sanjay Chawla, Shashi Shekhar +2 more
Lecture notes in computer scienceThe Pruning Power: Theory and Heuristics for Mining Databases with Multiple k-Nearest-Neighbor Queries
6 Citations2000Christian Böhm, Bernhard Braunmüller +1 more
This paper derives the theoretic foundation of this scheduling problem and proposes several scheduling algorithms based on the theoretical results, and shows that considering the maximum priority of pages clearly outperforms other scheduling approaches.
Lecture notes in computer scienceDynamic Spatial Clustering for Intelligent Mobile Information Sharing and Dissemination
4 Citations1999Eddie C. Shek, Giovanni Giuffrida +2 more
Intelligent Mobile Information Systems dynamically cluster similar user profiles into aggregate user classifications that are served by independent multicast channels of custom information packets to maximize the value of multicast dissemination.