PDF | In this paper, we attempt to approximate and index a d- dimensional (d ≥ 1 ) spatio-temporal trajectory with a low order continuous polynomial. There are. Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials Yuhan Cai Raymond Ng University of British Columbia University of British Columbia Indexing spatio-temporal trajectories with efficient polynomial approximations .. cosрiarccosрt0ЮЮ is the Chebyshev polynomial of degree i.
|Country:||Bosnia & Herzegovina|
|Published (Last):||19 December 2006|
|PDF File Size:||9.67 Mb|
|ePub File Size:||7.31 Mb|
|Price:||Free* [*Free Regsitration Required]|
Skip to main content. Log In Sign Up. Indexing spatio-temporal trajectories with Chebyshev polynomials.
Some of these the values of a vector of scalars at time ti. For example, possibilities have indeed been studied before. We hypoth- if the vector is of arity 1, the trajectory is a time series. Minimax approx- Time series are ubiquitous in temporal databases, which imation is particularly meaningful for indexing because in is a well-established area in database studies. Stock prices, a branch-and-bound search i. Exam- max polynomial is very hard to compute. However, it has ples include spatio-temporal trajectories of cars, airplanes, been shown that the Chebyshev approximation is almost and moving objects generated by motion tracking devices in identical to the optimal minimax polynomial, and is easy to surveillance applications and electronic games applications.
That is, we show that the Euclidean distance tal operation. This lemma is not trivial to show, on the ice rink. Finally, a 4-dimensional example is the four mits no false negatives. To complement the analytic result, angles of body joints of a spatio-tempora, playing kung-fu or danc- we conducted comprehensive experimental evaluation with ing.
This type of data sets is useful for games developers real and generated 1-dimensional to 4-dimensional data sets. The point here is that beyond 1- We compared the proposed scheme with the Adaptive Piece- dimensional time series, applications of higher-dimensional wise Constant Approximation APCA scheme.
Our prelim- spatio-temporal trajectories are ubiquitous. While indexung will discuss imdexing 1. That is to say, a smooth and continuous trajectory is Permission to make digital or hard copies of all or part of this work for approximated with a piecewise discontinuous function.
This personal or classroom use is granted without fee provided that copies are mismatch may cause unnecessary error or deviation, and not made or distributed for profit or commercial advantage, and that copies may lead to a loss in pruning power in a branch-and-bound bear this notice and the full citation on the first page.
To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific search. Below we discuss re- minimizes the maximum deviation from the true value is lated work.
In the next section, we review Chebyshev poly- very desirable. This is called the minimax approximation. In Section 3, we show how to approximate a dexing because in a branch-and-bound search i. We also propose a metric distance function between tion, the more pruning opportunities there exist. Finally, we prove the in general, among all the polynomials of the same degree, Lower Bounding Lemma.
In Section 4, we generalize the the optimal minimax polynomial is very hard to compute. In Section 5, we present our experimental setup most identical to the optimal minimax polynomial, and is and results. Examples include earlier works by Faloutsos et al. Thus, it is discrete in nature.
Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials
We also mation with a discontinuous piecewise function. DWT fur- give algorithms for building an index of Chebyshev ther requires the length of a time series be a power polynomialw two. We used with a continuous function. But while Fourier transforma- 1- to 4-dimensional real data sets, as well as generated tion is connected to Chebyshev approximation, the former data sets. For time series, the Adaptive Piecewise does not have the chebysyev property that the latter enjoys.
It is a global technique, and requires the computation et al. Our empirical results indicate that Cheby- experimental comparison.
For instance, not as many as the ones for time series. Their framework answers cients. This is a very important advantage. As the di- queries of the form: Fur- interval [a, b]. See  for more details. Without loss of thermore, it is based on the assumption that all the objects generality, hereafter we simply focus on the interval [-1,1]. The indexing scheme approx- Concerning Chebyshev polynomials, a key property is that imates each trajectory by straight line segments.
Two polynomials are orthogonal if their inner indexing in high dimensional spaces. In , Perng et al. The following is true for the Cheby- ilarity model for time series called the Landmark model.
A weaker version of the Triangle Inequality is used to answer k-nearest-neighbors kNN queries . The purpose of the weight exact schemes for similarity searching of the whole trajecto- function is to make the result of the integration exact e.
That is to say, the schemes guarantee no false negatives. In the literature, there are studies which consider provid- Given the orthogonality of the Chebyshev polynomials, ing faster approximate similarity search, at the expense of they can be used as a base for approximating any function. Examples in- That is, given a function f tit can be approximated as: The approximation is exact if f t is a polynomial and its degree is less than or equal to m.
Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials – Semantic Scholar
The following theo- In this section, we review Chebyshev polynomials and rem is called the Gauss-Chebyshev formula. This is a direct nomials are: Recall that time t is normalized into of degree m, with m N. To facilitate fast searching, the the cebyshev [-1,1]. We propose in Section 3. We then establish the important An obvious choice for an interval function would be the Lower Bounding Lemma in Section 3.
Sptio-temporal the tighter the lower bound, To create an interval function based on the original time the smaller is the number of false positives. Special attention is paid to the boundary conditions: Polynomiaps every time series has the same end-point of the interval, and tN with respect to the right length, i.
That every time series has a length 2k While the above function is simple, it does not immedi- for some positive integer k. Thus, this assump- Section 2 and the length insexing each subinterval: This extends the same- of subinterval Ii. Furthermore, for better approximation quality, we can use all the Cheebyshev data points and values of the time series.
Unlike some other frame- works, like wavelet decompositions [4, 27, 9, 18], we do not 1 X 1 X N N require the power-of-2 assumption. If this assumption is not met, interpolation techniques 2 X N may be applied. In any event, trajectodies ci is O N. Because n is intended to be a small constant shown. The right for spatio-temporal trajectories. The x-axis is tion is simple, it is natural for many applications with spatio- normalized to the interval [-1, 1], and the y-axis is normal- temporal trajectories, including trajectories for airplanes and ized according to the APCA framework.
It is also the distance function adopted by Notice that for n equal to a power of 2, the PAA approx- most studies on indexing time series, including .
For imation is exactly the same as the wavelet transform. Also more advanced distance functions such as time-warping  note that under APCA, because each piece is not of equal and longest common subsequence , we consider them fu- length, each piece requires two values for storage.
Thus, for ture topics of investigation. T denotes the transpose of the vector. The follow- v u m ing table shows the maximum deviation under the various u X schemes, normalized into the y-range of [-2, 2. It is weighted by the con- DFT 2. The following lemma is easy to establish. Distcby is a metric distance function.
Indexing spatio-temporal trajectories with Chebyshev polynomials | Raymond Ng –
Notice that for 3. Let S1outline below some of the key steps in the proof. This is due to the fact that the integrand is the Chebyshev approximation of Z based on Equation 6. In the following, we only focus on ci for trajectorise. Then we present algorithms for indexing and kNN searches. Then S is decomposed At this point, we need to use a known result for Chebyshev into d 1-dimensional series: Let each of approximation. Let S, R be d-dimensional spatio-temporal weight function. Then it is the case that: This is because record the maximum max the d-dimensional distance is based on the sum-of-squares 5 invoke the range search RangeSearch Q, Index, max distances along each dimension.
The data set was obtained from dimensional index. Both of these data sets consist of of the algorithm is O Nwhere N is the length of each long 1-dimensional trajectoriez series.
In both cases, points. Figure 4 shows a skeleton of the range search season. The data were provided to us by an electronic algorithm, and Figure 5 shows a skeleton of the kNN search games company. The Slips, Kungfu and Angle data sets were obtained from http: