Grid-Based Methods

1. Idea

Instead of clustering individual objects, quantise the data space into a finite number of cells (a grid) and perform all clustering operations on the grid structure. Benefits:

Fast — the number of grid cells is independent of the number of objects $n$ (only depends on the number of dimensions and the number of partitions per dimension), so complexity is typically $O(n)$ for the mapping plus something proportional to the number of cells.
Memory efficient — statistics are kept per cell rather than per object.
Data is summarised as cell statistics (count, sum, mean, min, max, variance, distribution types).

\#\text{cells} = k^{d}\ \ (k \text{ partitions per dimension},\ d \text{ dimensions}) \quad\Rightarrow\ \text{grows exponentially with } d

2. Grid Construction

Partition each dimension into $k$ equal-length intervals (e.g. $k = 10$ ).
Map every object to the cell containing it and accumulate statistics — the cell is occupied if its count > 0.
Identify dense cells whose density (count per unit volume, or count) exceeds a threshold $\xi$ .
Merge neighbouring dense cells into clusters.

        x2
        ^  +---+---+---+---+---+
        |  |   | ### | ### |   |        ### = dense cell (count >= xi)
        |  +---+---+---+---+---+        .   = sparse cell
        |  |   | ### | ### | . |        cluster = connected dense cells
        |  +---+---+---+---+---+
        |  |   |  .  | ### |   |
        |  +---+---+---+---+---+
        +-------------------------> x1

3. STING — STatistical INformation Grid

Structure: hierarchical — each cell at level $i$ is partitioned into 4 (2-D) child cells at level $i+1$ ; each cell stores independent statistical parameters (count, mean, standard deviation, min, max, and the distribution type) for each attribute.

Attribute independence assumption lets cell statistics be computed directly from a higher-level cell's statistics — so even an unpopulated lower-level cell can have statistics derived from its parent.

  Level 1  |                       root (whole space)                        |
  Level 2  |     cell      |     cell      |      cell     |     cell        |
  Level 3  |  c11 | c12    |  c21 | c22    |  c31 | c32   |  c41 | c42       |  ... (4^n children)

Query processing algorithm:

1. Determine a layer to begin with (usually a few layers from the top).
2. For each cell in that layer:
      compute the confidence interval (or estimated range) of the probability
      that this cell is relevant to the query.
3. Mark each cell as:
      RELEVANT    -> go down to its children
      NOT RELEVANT-> discard the cell and its subtree
      UNKNOWN/IRRELEVANT -> leave as is  (relevance not yet decided)
4. If this layer is the bottom layer, return the relevant cells (with all the
   information they contain); else go to the next lower layer and repeat.

Cell relevance test using the normal assumption for a region with $n$ objects:

\mu \pm \frac{z_{\alpha/2}\,\sigma}{\sqrt{n}}\quad\text{intersects the query region} \Rightarrow \text{relevant}

Advantages: grid hierarchy is query-independent so future queries are fast; incremental update is trivial (only affected cells change); parallelisable. Disadvantages: all cells at the same level have the same size (poorly adapted to skewed data); the distribution is assumed independent across dimensions (wrong for correlated attributes); the quality depends on the granularity of the lowest level.

4. CLIQUE — CLustering In QUEst

Designed for high-dimensional data; combines grid + density and finds subspaces in which clusters exist (a full-attribute cluster may not exist at all).

Algorithm (bottom-up over subspaces)

1. For each dimension, partition the space into intervals (grid), density threshold xi.
2. Pass over the data to identify the 1-D dense units (dense in 1 dimension).
3. k = 2  (number of dimensions)
4. repeat
      generate candidate dense units in k dimensions using the Apriori-style
        (k-1)-dimensional dense units (only units whose every (k-1)-dim projection
        is dense can be dense)
      count the density of candidate units with a data pass
      keep the dense ones
      k = k + 1
   until no more dense units can be generated
5. Find connected components (clusters) in the resulting dense units
   using a depth-first search, taking the maximal units (MDL pruning)
6. Determine the minimal description (DNF expression) of each cluster

Minimal description of a cluster (a DNF expression):

C = \big(d_1 \text{ in } I_{1}\big) \wedge \big(d_2 \text{ in } I_{2}\big) \ \vee\ \big(d_1 \text{ in } I_{3}\big) \wedge \big(d_3 \text{ in } I_{4}\big)\ \ \dots

Key points / properties:

Dense unit: a cell whose fraction of points $\ge \xi$ .
Uses the monotonicity/Apriori property: if a $k$ -dimensional unit is dense, then all its $(k-1)$ -dimensional projections are dense — this prunes the search drastically.
Automatically finds subspaces that contain clusters, so it resists the "curse of dimensionality"; the number of data passes = the highest dimensionality of a dense unit.
Scalability: exponential in the highest number of dimensions of a dense unit, not in the total number of dimensions — a big practical advantage. It is order-insensitive and insensitive to outliers.
Disadvantages: high accuracy requires many partitions → more dense units and higher complexity; interpretation can be hard (overlapping clusters in different subspaces).

Number of dimensions to consider (combinatorial explosion avoided by pruning):

\sum_{k=1}^{d}\binom{d}{k}=2^{d}-1 \quad\text{candidate subspaces}

5. Other Grid-Based Approaches

Method	Notes
STING	Hierarchical statistical grid, query-driven, independent of queries, fast but coarse
CLIQUE	Grid + density + Apriori-style subspace search for high dimensions
WaveCluster	Applies a wavelet transform on the grid; dense regions found as high-frequency coefficients; handles arbitrary shapes, noise and any input order; $O(n)$
MAFIA	Uses adaptive grids (different interval counts per dimension) plus a threshold per dimension; superior for very large data

6. Grid-Based vs Other Clustering Families

Criterion	Partitioning (k-means)	Hierarchical	Density (DBSCAN)	Grid (STING/CLIQUE)
Input parameter	$k$	linkage/distance	$\varepsilon$ , MinPts	#partitions, density threshold $\xi$
Shape of clusters	Spherical	Depends on linkage	Arbitrary	Arbitrary (cell shape limited)
Noise handling	Weak	Weak (single link)	Good	Good (sparse cells ignored)
Complexity	$O(nkt)$	$O(n^2)$	$O(n\log n)$	$O(n)$ for the mapping step
High dimensions	Poor	Poor	Poor	Good (CLIQUE finds subspaces)
Order dependence	Yes (initial seeds)	No (deterministic)	Practically minor	No

7. Exam Points

Explain STING with the cell structure, cell statistics and the query-processing algorithm — 10 marks (frequent).
Explain CLIQUE with its algorithm, monotonicity/density properties and subspaces — 10 marks.
Compare STING and CLIQUE (query-driven vs bottom-up, dimensions, output form) — 5-7 marks.
Advantages and disadvantages of grid-based clustering; why it is fast and scalable — 5 marks.
Short note on WaveCluster / MAFIA — 3 marks.

Grid-Based Methods