In order to process CKNN queries on the basis of TPR-tree efficiently, a new spatio-temporal distance metrics minmaxdist(t) was presented as a pruning upper bound. Also a CKNN queries algorithm STM-CNN which can search in best-first manner was developed by means of mindist(t) and minmaxdist(t) metrics, in which STM-CNN algorithm visits TPR-tree nodes according to mindist(t)order, and pruning the nodes with minmaxdist(t).