In this paper, we attempt to approximate and index a $d$-dimensional
($d \geq 1$) spatio-temporal trajectory with a low order continuous
polynomial.  There are many possible ways to choose the polynomial,
including (continuous) Fourier transforms, splines, non-linear
regression, etc.  Some of these possibilities have indeed been studied
before.  We hypothesize that one of the best possibilities is the
polynomial that minimizes the maximum deviation from the true value,
which is called the minimax polynomial. Minimax approximation is
particularly meaningful for indexing because in a branch-and-bound
search (i.e., for finding nearest neighbours), the smaller the maximum
deviation, the more pruning opportunities there exist. However, in
general, among all the polynomials of the same degree, the optimal
minimax polynomial is very hard to compute.  However, it has been shown
that the Chebyshev approximation is almost identical to the optimal
minimax polynomial, and is easy to compute~\cite{MH03}.  Thus, in this
paper, we explore how to use the Chebyshev polynomials as a basis for
approximating and indexing $d$-dimensional trajectories.

The key analytic result of this paper is the Lower Bounding Lemma.
That is, we show that the Euclidean distance between two
$d$-dimensional trajectories is lower bounded by the weighted Euclidean
distance between the two vectors of Chebyshev coefficients. This lemma
is not trivial to show, and it ensures that indexing with Chebyshev
coefficients admits no false negatives. To complement the analytic
result, we conducted comprehensive experimental evaluation with real
and generated 1-dimensional to 4-dimensional data sets. We compared the
proposed scheme with the Adaptive Piecewise Constant Approximation
(APCA) scheme.  Our preliminary results indicate that in all situations
we tested, Chebyshev indexing dominates APCA in pruning power, I/O and
CPU costs.