ST-DBSCAN: An algorithm for clustering spatial–temporal data
Data & Knowledge EngineeringPublished 15 March 2006
Derya Birant, Alp Kut
Citations1,407
SJR quartileQ2
SJR score0.68
SNIP1.41
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.
TL;DR
A new density-based clustering algorithm based on DBSCAN, which has the ability of discovering clusters according to non-spatial, spatial and temporal values of the objects, is presented and an implementation of the algorithm is shown by using this data warehouse and the data mining results are presented.
Abstract
This paper presents a new density-based clustering algorithm, ST-DBSCAN, which is based on DBSCAN. We propose three marginal extensions to DBSCAN related with the identification of (i) core objects, (ii) noise objects, and (iii) adjacent clusters. In contrast to the existing density-based clustering algorithms, our algorithm has the ability of discovering clusters according to non-spatial, spatial and temporal values of the objects. In this paper, we also present a spatial–temporal data warehouse system designed for storing and clustering a wide range of spatial–temporal data. We show an implementation of our algorithm by using this data warehouse and present the data mining results.
Keywords
Computer Science
Choice Reviews OnlineData mining: concepts and techniques
28,877 Citations2012Jiawei Han, Micheline Kamber +1 more
Data mining is the search for new, valuable, and nontrivial information in large volumes of data, a cooperative effort of humans and computers that is possible to put data-mining activities into one of two categories: Predictive data mining, which produces the model of the system described by the given data set, or Descriptive data mining which produces new, nontrivials information based on the available data set.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Some methods for classification and analysis of multivariate observations
22,787 Citations1967James B. MacQueen
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.
Introduction to Data Mining
7,026 Citations2008
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
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.
Journal of Intelligent Information SystemsOn Clustering Validation Techniques
2,655 Citations2001Maria Halkidi, Yannis Batistakis +1 more
The fundamental concepts of clustering are introduced while it surveys the widely known clustering algorithms in a comparative way and the issues that are under-addressed by the recent algorithms are illustrated.
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.
Machine LearningKnowledge Acquisition Via Incremental Conceptual Clustering
1,754 Citations1987Douglas Fisher
COBWEB is a conceptual clustering system that organizes data so as to maximize inference ability, and is incremental and computationally economical, and thus can be flexibly applied in a variety of domains.
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.
Machine LearningKnowledge acquisition via incremental conceptual clustering
1,081 Citations1987Douglas Fisher
COBWEB is a conceptual clustering system that organizes data so as to maximize inference ability, and is incremental and computationally economical, and thus can be flexibly applied in a variety of domains.
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.
The VLDB JournalAn introduction to spatial database systems
717 Citations1994Ralf Hartmut G�ting
This work surveys data modeling, querying, data structures and algorithms, and system architecture for spatial database systems, with the emphasis on describing known technology in a coherent manner, rather than listing open problems.
Incremental Clustering for Mining in a Data Warehousing Environment
464 Citations1998Martin Ester, Hans‐Peter Kriegel +3 more
It can be proven that the incremental algorithm yields the same result as DBSCAN, which is applicable to any database containing data from a metric space, e.g., to a spatial database or to a WWW-log database.
Journal of Geophysical Research AtmospheresThe development and operational application of nonlinear algorithms for the measurement of sea surface temperatures with the NOAA polar‐orbiting environmental satellites
451 Citations1998Charles C. Walton, William G. Pichel +2 more
ACM Transactions on Information SystemsQuery clustering using user logs
370 Citations2002
A new query clustering method that makes use of user logs which allow us to identify the documents the users have selected for a query and shows that a combination of both keywords and user logs is better than using either method alone.
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.
Journal of the American Statistical AssociationInteger Programming and the Theory of Grouping
245 Citations1969Hrishikesh D. Vinod
GeoInformaticaSurvey of Spatio-Temporal Databases
212 Citations1999Tamas Abraham, John F. Roddick
An overview of previous achievements within the spatio-temporal data field is provided and areas currently receiving or requiring further investigation are highlighted.
Geographic Data Mining and Knowledge Discovery
147 Citations2001John F. Roddick, Brian G. Lees
This book is a kind of precious book written by an experienced author and it will show one of recommendation of the book that you need to read.
Lecture notes in computer scienceScalable Density-Based Distributed Clustering
114 Citations2004Eshref Januzaj, Hans‐Peter Kriegel +1 more
A scalable density-based distributed clustering algorithm which allows a user-defined trade-off between clustering quality and the number of transmitted objects from the different local sites to a global server site.
Journal of Computer Science and TechnologyApproaches for scaling DBSCAN algorithm to large spatial databases
106 Citations2000Aoying Zhou, Shuigeng Zhou +3 more
Several approaches are proposed to scale DBSCAN algorithm to large spatial databases and some experimental results are given to demonstrate the effectiveness and efficiency of these algorithms.
Clustering Algorithms for Spatial Databases: A Survey
87 Citations2001Erica Kolatch
Journal of the American Statistical AssociationInteger Programming and the Theory of Grouping
68 Citations1969Hrishikesh D. Vinod
Analyzing Popular Clustering Algorithms from Different Viewpoints
64 Citations2002Weining Qian
This work analyzes several popular clustering algorithms from three different viewpoints: (1) clustering criteria, (2) cluster representation, and (3) algorithm framework.
Lecture notes in computer scienceA New Fast Clustering Algorithm Based on Reference and Density
49 Citations2003Shuai Ma, Tengjiao Wang +3 more
A method of RGUBR is presented to improve the accuracy of grid clustering method, so it can be used to discover information in very large databases.
Journal of Intelligent Information SystemsMultidimensional Index Structures in Relational Databases
42 Citations2000Christian Böhm, Stefan Berchtold +2 more
This work proposes a new approach to implement an index structure on top of a commercial relational database system, which maps the index structure to a relational database design and simulates the behavior of theindex structure using triggers and stored procedures.
Clustering-based Approach to Identify Solutions for the Inference of Regulatory Networks
14 Citations2005Christian Spieth, Felix Streichert +2 more
This paper proposes to use a clustering based niching evolutionary algorithm to maintain diversity in the optimization population to prevent premature convergence and to raise the probability of finding the global optimum by identifying multiple alternative networks.
Identifying valid solutions for the inference of regulatory networks
3 Citations2005Christian Spieth, Felix Streichert +2 more
A clustering based niching evolutionary algorithm is proposed to use to maintain diversity in the optimization population to prevent premature convergence and to raise the probability of finding the global optimum by identifying multiple alternative networks than standard algorithms.