Gaussian process regression (GPR), a potent non-parametric data modeling tool, has gained attention but is hindered by its high com- putational load. State-of-the-art low-rank approximations like struc- tured kernel interpolation (SKI)-based methods offer efficiency, yet lack a strategy for determining the number of grid points, a pivotal factor impacting accuracy and efficiency. In this thesis, we tackle this challenge. We explore existing low-rank approximations that facilitates the computation, dissecting their strengths and limitations, particularly SKI-based methods. Subsequently, we introduce a novel approxima- tion framework, MKISSGP, which dynamically adjusts grid points us- ing a new hyperparameter of the model: density, according to changes in the kernel hyperparameters in each training iteration. MKISSGP exhibited consistent error levels in the reconstruction of the kernel matrix, irrespective of changes in hyperparameters. This robust performance forms the bedrock for achieving accurate approx- imations of kernel matrix-related terms. When employing our rec- ommended density value (i.e., 2.7), MKISSGP achieved a comparable level of precision to that of precise GPR, while requiring only 52% of the time compared to the current state-of-the-art method.