In this paper, we consider the problem of evaluating the continuous query of finding the k nearest objects with respect to a given point object Oq among a set of n moving point-objects. The query returns a sequence of answer-pairs, namely pairs of the form (I,S) such that I is a time interval and S is the set of objects that are closest to Oq during I . When there is uncertainty associated with the locations of the moving objects, S is the set of all the objects that are possibly the k nearest neighbors. We analyze the lower bound and the upper bound on the maximum number of answer-pairs, for the certain case and the uncertain case, respectively. Then, we consider two different types of algorithms. The first is off-line algorithms that compute a priori all the answer-pairs. The second type is on-line algorithms that at any time return the current answer-pair. We present algorithms for the certain case and the uncertain case, respectively, and analyze their complexity. We experimentally compare different algorithms using a database of 1 million objects derived from real-world GPS traces.