2023 , Volume 28, № 5, p.114-131

Grid-based clustering algorithms allow processing large data arrays and distinguish clusters of complex, a priori unknown shape. However, grid-based algorithms remain computationally efficient only while the feature space dimensionality is small. This paper considers the problem of applying grid-based clustering to high-dimensional data, which arises due to the exponential growth for the size of grid structure with the feature space dimensionality. The common “greedy” approach, which stores information about each cell of the grid structure, requires unacceptably large memory costs in high dimensional cases.

In this paper a new data structure for storing multidimensional grid structure that considers only non-empty cells is proposed, which allows reducing the dependence of memory costs on the data dimension. The proposed data structure stores only a subspace of a grid structure in the expanded form. Besides, two multidimensional grid structures were implemented based on the use of hash tables. All developed structures were adjusted according to the HCA clustering algorithm and also may be used in other grid-based algorithms.

Experimental studies were carried out in terms of memory costs and computation time on WorldView-2 and Sentinel-2 multispectral satellite images. The obtained results have showed that all three implemented data structures allow grid-based algorithms for processing high-dimensional data with reasonable memory costs. At the same time, the proposed data structure have showed better results than other implemented approaches.

Thus, the conducted study allows expanding limits of the grid-based clustering algorithms in processing high-dimensional data (5–10 dimensions).