Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering

Summary: OptiGrid introduces optimal grid-partitioning for high-dimensional clustering, selecting dimension-wise hyperplane splits via projections to beat the curse of dimensionality. It outperforms condensation-based methods like BIRCH, offering a solid mathematical basis, improved effectiveness in high dimensions, and scalable efficiency on large real datasets (CAD, molecular biology). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8785
Venue: VLDB
Year: 1999
Pagerank: 7.2151113e-05
Overall Rank: 3,663 | 74.87%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Alexander Hinneburg (University of Halle)
2. Daniel A. Keim (University of Halle)

BibTeX Citation

@article{hinneburg_vldb99,
        title = {{Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering}},
        author = {Hinneburg, Alexander and Keim, Daniel A.},
        journal = {PVLDB},
        series = {{VLDB} '99},
        pages = {506--517},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,002	SQLEM: Fast Clustering in SQL using the EM Algorithm	2000	SIGMOD	9.3312236e-05
2,730	DADA: A Data Cube for Dominant Relationship Analysis	2006	SIGMOD	8.1977425e-05
3,550	A Monte Carlo Algorithm for Fast Projective Clustering	2002	SIGMOD	7.3200789e-05
5,500	Combi-Operator – Database Support for Data Mining Applications	2003	VLDB	6.1968585e-05
7,023	C2P: Clustering based on Closest Pairs	2001	VLDB	5.7242118e-05
8,215	CURLER: Finding and Visualizing Nonlinear Correlation Clusters	2005	SIGMOD	5.4651579e-05
12,764	k-Means Projective Clustering	2004	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00050347119
88	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.00035240327
304	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD	0.00021917388
350	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00020425134
483	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017756569
1,285	STING: A Statistical Information Grid Approach to Spatial Data Mining	1997	VLDB	0.00011321748
1,941	WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases	1998	VLDB	9.4453261e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,867	Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space	2018	SIGMOD
2	31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD
3	9,272	A Framework for Projected Clustering of High Dimensional Data Streams	2004	VLDB
4	304	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD
5	12,764	k-Means Projective Clustering	2004	PODS
6	12,572	Constrained Locally Weighted Clustering	2008	VLDB
7	1,646	Fast Algorithms for Projected Clustering	1999	SIGMOD
8	12,815	A Shrinking-Based Approach for Multi-Dimensional Data Analysis	2003	VLDB
9	1,833	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD
10	8,778	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB