A grid-based clustering is a space-driven approach method. The grid data structure is formed by quantizing the object space into a finite number of cells. The clustering are performed on the formed grid data structure. As this approach is independent of the number of data objects but only dependent on the number of cells in each dimension in the space, its processing time is faster.
There are two methods in grid based approach. They are STING (Statistical Information Grid) and CLIQUE (Clustering in Quest).
STING is a grid-based multiresolution clustering technique in which the embedding spatial area of the input objects is divided into rectangular cells. Each cell at a high level is partitioned to form a number of cells at the next lower level. The statistical parameters such as mean, maximum, and minimum values are computed and stored for query processing and for data analysis tasks.
STING approaches the clustering result of DBSCAN if the granularity approaches 0. STING offers the following advantages.
- the grid-based computation is query-independent.
- the grid structure facilitates parallel
- processing and incremental updating.
- It goes through the database once to compute the statistical parameters.
The time complexity of generating clusters is O(n), where n is the total number of objects. The query processing time is O(g) after generating the hierarchical structure, where g is the total number of grid cells at the lowest level.
The quality of STING clustering depends on the granularity of the lowest level of the grid structure. If the granularity is very fine, the cost of processing will increase substantially; however, if the bottom level of the grid structure is too coarse, it may reduce the quality of cluster analysis.
CLIQUE is a simple grid-based method for finding density based clusters in subspaces. It uses a density threshold to identify dense cells and sparse ones. A cell is dense if the number of objects mapped to it exceeds the density threshold.
CLIQUE performs clustering in two steps. In the first step, CLIQUE partitions the d-dimensional data space into nonoverlapping rectangular units. In the second step, CLIQUE uses the dense cells in each subspace to assemble clusters, which can be of arbitrary shape.
CLIQUE automatically finds subspaces of the highest dimensionality such that high-density clusters exist in those subspaces.