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.0562784e-05
Overall Rank: 3,743 | 74.85%
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,004	SQLEM: Fast Clustering in SQL using the EM Algorithm	2000	SIGMOD	9.205468e-05
2,786	DADA: A Data Cube for Dominant Relationship Analysis	2006	SIGMOD	8.0127919e-05
3,618	A Monte Carlo Algorithm for Fast Projective Clustering	2002	SIGMOD	7.1525532e-05
5,634	Combi-Operator – Database Support for Data Mining Applications	2003	VLDB	6.0552789e-05
7,165	C2P: Clustering based on Closest Pairs	2001	VLDB	5.5931268e-05
8,388	CURLER: Finding and Visualizing Nonlinear Correlation Clusters	2005	SIGMOD	5.3400228e-05
13,060	k-Means Projective Clustering	2004	PODS	4.9769913e-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.00049714561
94	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.0003456395
308	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD	0.00021463972
358	A Retrieval Technique for Similar Shapes	1991	SIGMOD	0.00020011298
488	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017451091
1,305	STING: A Statistical Information Grid Approach to Spatial Data Mining	1997	VLDB	0.00011094431
1,988	WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases	1998	VLDB	9.2470974e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,990	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,455	A Framework for Projected Clustering of High Dimensional Data Streams	2004	VLDB
4	308	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD
5	13,060	k-Means Projective Clustering	2004	PODS
6	12,868	Constrained Locally Weighted Clustering	2008	VLDB
7	1,679	Fast Algorithms for Projected Clustering	1999	SIGMOD
8	13,111	A Shrinking-Based Approach for Multi-Dimensional Data Analysis	2003	VLDB
9	1,882	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD
10	8,949	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB