Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering
KOPS (University of Konstanz)Published 7 September 1999Open access
Alexander Hinneburg, Daniel A. Keim
Citations336
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 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.
Abstract
Many applications require the clustering of large amounts of high-dimensional data. Most clustering algorithms, however, do not work effectively and efficiently in high-dimensional space, which is due to the so-called "curse of dimensionality". In addition, the high-dimensional data often contains a significant amount of noise which causes additional effectiveness problems. In this paper, we review and compare the existing algorithms for clustering high-dimensional data and show the impact of the curse of dimensionality on their effectiveness and efficiency. The comparison reveals that condensation-based approaches (such as BIRCH or STING) are the most promising candidates for achieving the necessary efficiency, but it also shows that basically all condensation-based approaches have severe weaknesses with respect to their effectiveness in high-dimensional space. To overcome these problems, we develop a new clustering technique called OptiGrid which is based on constructing an optimal grid-...
Keywords
Computer SciencePhysics and Astronomy
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.
IEEE Transactions on Information TheoryThe estimation of the gradient of a density function, with applications in pattern recognition
3,021 Citations1975Keinosuke Fukunaga, L.D. Hostetler
Applications of gradient estimation to pattern recognition are presented using clustering and intrinsic dimensionality problems, with the ultimate goal of providing further understanding of these problems in terms of density gradients.
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.
Lecture notes in computer scienceWhen Is “Nearest Neighbor” Meaningful?
2,297 Citations1999Kevin Beyer, Jonathan Goldstein +2 more
The effect of dimensionality on the "nearest neighbor" problem is explored, and it is shown that under a broad set of conditions, as dimensionality increases, the Distance to the nearest data point approaches the distance to the farthest data point.
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.
ACM Computing SurveysTechniques for automatically correcting words in text
1,256 Citations1992Karen Kukich
Research aimed at correcting words in text has focused on three progressively more difficult problems: nonword error detection; (2) isolated-word error correction; and (3) context-dependent work correction, which surveys documented findings on spelling error patterns.
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.
Knowledge Discovery and Data MiningA density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise
1,134 Citations1996Martin Ester, Hans‐Peter Kriegel +2 more
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.
Journal of Molecular BiologyReversible peptide folding in solution by molecular dynamics simulation 1 1Edited by R. Huber
371 Citations1998Xavier Daura, Bernhard Jaun +3 more
Long-standing questions on how peptides fold are addressed by the simulation at different temperatures of the reversible folding of a peptide in solution in atomic detail, implying that the search problem in peptide (or even protein) folding is surmountable using dynamics simulations.
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.
Computer Graphics and Image ProcessingAn efficient three-dimensional aircraft recognition algorithm using normalized fourier descriptors
337 Citations1980Timothy P. Wallace, P. A. Wintz
This paper presents a technique for normalizing Fourier descriptors which retains all shape information, and is computationally efficient, and combined with certain others relating to accurate contour representation in a complete three-dimensional aircraft recognition algorithm.
A retrieval technique for similar shapes
251 Citations1991H. V. Jagadish
An organization for a database of objects that permits the efficient retrieval of all objects in the database with a shape similar to a search template is proposed, which can have the computer reproduce, on a huge database of images, the process performed by a human in ‘ ‘riffling’ through a book, using an index structure to retrieve likely candidates quickly.
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.
Grid-clustering: an efficient hierarchical clustering method for very large data sets
156 Citations1996Erich Schikuta
A new approach to hierarchical clustering of very large data sets is presented with the GRIDCLUS algorithm, which uses a multidimensional grid data structure to organize the value space surrounding the pattern values, rather than to organized the patterns themselves.
Informatik-FachberichteLEDA A Library of Efficient Data Types and Algorithms
94 Citations1990Kurt Mehlhorn, Stefan Näher
Efficient color histogram indexing
73 Citations2002Harpreet Sawhney, James Lee Hafner
Results on color histogram matching in large image databases show that pre-filtering with the simpler distance measures leads to significantly less time complexity because the quadratic histogram distance is now computed on a smaller set of images.
Density-connected sets and their application for trend detection in spatial databases
46 Citations1997Martin Ester, Hans‐Peter Kriegel +2 more
The concept of density-connected sets is introduced and a significantly generalized version of DBSCAN, which can be used as a basis to discover trends in a spatial database, is presented.
Feature-index-based similar shape retrieval
26 Citations1995R. Mehrotra, James E. Gary
A new feature-index-based shape similarity-based image retrieval technique, which is capable of handling images of rigid as well as articulated objects, is proposed and can also retrieve images of overlapping and touching objects that satisfy the query constraints.