MPdist is a distance measure which considers two time series to be similar if they share many similar subsequences. However, computing MPdist can be slow, especially for large time series. We propose a technique for the approximate computation of MPdist that uses the SAX representation of the time series to quickly estimate the Nearest Neighbor (NN) distance of each subsequence, and then applies a Machine Learning model to correct the accuracy loss incurred. Our method is orders of magnitude faster than the exact computation of MPdist; at the same time, our best approximation computes the NN of a time series with high accuracy. A thorough evaluation of our technique is provided.