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: hc9247356c8882ba6
Venue: VLDB
Year: 1999
Pagerank: 7.0336098e-05
Overall Rank: 3,750 | 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,006	SQLEM: Fast Clustering in SQL using the EM Algorithm	2000	SIGMOD	9.1840961e-05
2,795	DADA: A Data Cube for Dominant Relationship Analysis	2006	SIGMOD	7.9865595e-05
3,627	A Monte Carlo Algorithm for Fast Projective Clustering	2002	SIGMOD	7.1290231e-05
5,647	Combi-Operator – Database Support for Data Mining Applications	2003	VLDB	6.0352838e-05
7,185	C2P: Clustering based on Closest Pairs	2001	VLDB	5.5746325e-05
8,406	CURLER: Finding and Visualizing Nonlinear Correlation Clusters	2005	SIGMOD	5.3223662e-05
13,101	k-Means Projective Clustering	2004	PODS	4.9605343e-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
32	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00049559562
94	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.00034470298
310	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD	0.00021410542
361	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00019948113
490	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017397036
1,313	STING: A Statistical Information Grid Approach to Spatial Data Mining	1997	VLDB	0.00011058121
1,996	WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases	1998	VLDB	9.2175908e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,001	Fast Euclidean OPTICS with Bounded Precision in Low Dimensional Space	2018	SIGMOD
2	32	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD
3	9,485	A Framework for Projected Clustering of High Dimensional Data Streams	2004	VLDB
4	310	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD
5	13,101	k-Means Projective Clustering	2004	PODS
6	12,911	Constrained Locally Weighted Clustering	2008	VLDB
7	1,685	Fast Algorithms for Projected Clustering	1999	SIGMOD
8	13,152	A Shrinking-Based Approach for Multi-Dimensional Data Analysis	2003	VLDB
9	1,893	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD
10	8,970	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB