Spatio-temporal frequent patterns discovered from historical trajectories of moving objects can provide important knowledge for location-based services. To address the problem of finding sequential patterns from spatio-temporal datasets, continuous values of spatial and temporal attributes should be discretized with the minimum loss of information. Since data carries spatio-temporal correlation among attributes, it should be preserved during discretization to derive accurate patterns. In this paper, we define the problem of discretizing spatio-temporal data and propose a discretization method preserving spatio-temporal correlations in the data. Using line simplification, our method first abstracts trajectories into approximations considering the distributions of input data and then clusters them into logical cells. We experimentally analyze the effectiveness of the proposed approach in reducing the size of data and improving efficiency of the mining processes.