Implement of a Fast Time Series Evaluation Algorithm

HI,

I currently want to compute the similarity of time series and have found an algorithm called:
Fast Time Series Evaluation<
An Efficient and Accurate Method for Evaluating Time
Series Similarity>

However, I fail to clearly understand this algorithm and don't know how to implement it in C.

Could some friends give me some help?

Thank you,
here is the detail:

Quote:

---

The first step in the FTSE algorithm is to find all intersecting
pairs between elements of R and elements of S. The technique
used to obtain these intersecting pairs is shown in Algorithm 1.
First, a grid of dimensionality d is constructed (line 4 of the algorithm).
The edge length of each element of the grid is .
In lines 6 to 8 of the algorithm, a Minimum Bounding Rectangle
(MBR) is constructed for each element ri of R. This MBR has
a side length of 2 in each dimension, and its center is the point
ri. This construction method ensures that ri overlaps with no more
than 3d elements in the grid.
The MBR construction is illustrated in Figure 4 for one and two
dimensions. In one dimension, the MBR of ri is flattened into a
line and intersects with 3 grid elements, as shown in Figure 4a. In
two dimensions, the MBR of ri intersects with 9 grid elements, as
shown in Figure 4b.
A FIFO queue is associated with each cell g of the grid. The
queue for each g is used to maintain a reference to all ri that are
within  of g, in order of increasing i. This is done in line 9 of
Algorithm 1.
The intersections between R and S are found in lines 11-18 of
Algorithm 1. The grid cell g that contains each sj ∈ S is located.
The elements of R in the queue associated with g are compared
with sj to see if they are within  of one another. For each element
rk of R that is within  of sj , the index of rk, i.e. k, is inserted into
the intersection list Lj of sj . The entries of Lj are also maintained
in order of increasing k.
Note that the size of the grid is likely to be small for the following
reason: Since data is normalized with mean zero and standard
deviation σ = 1, most data will fall between -3 and 3. If the 
value is not exceptionally small relative to σ (which is common
– for example, [29] uses 0.5σ), the size of the grid is reasonably
small. Outliers beyond -3 or 3 are rare and can be captured into an
additional grid cell.



http://www.liang-chen.com/images/200...rithm_2.pg.jpg

---

Show us what you've done so far.

--
Mats

Pretty no... because I can't understand the "Grid" and "Queue q".

Need help, it's beyond my ability and experience now,,, maybe i should begin from a algorithm book?

Quote:

---

The MBR construction is illustrated in Figure 4 for one and two
dimensions. In one dimension, the MBR of ri is flattened into a
line and intersects with 3 grid elements, as shown in Figure 4a. In
two dimensions, the MBR of ri intersects with 9 grid elements, as
shown in Figure 4b.

---

We've no idea what these figures are.

A grid would suggest a 2D array, like
queue grid[3][3];

Here is an explanation for a queue.
If you're doing this in C (it would be a hell of a lot easier in C++ BTW), then start with some simple queue primitives to say
- initialise a queue
- append (to either end) of the queue
- iterate over the items in the queue.

Like I said, in C++, there is already a std::queue you could use right off the bat without any more effort.

Quote:

---

Originally Posted by BiGreat

Need help, it's beyond my ability and experience now,,, maybe i should begin from a algorithm book?

---

As a hobby programmer only, I don't fully understand the reason for this algorithmic solution. I understand the data structures, but I don't understand why they're a good fit for this.

That font in the algo, looks a lot like Knuth, doesn't it?

I believe you have two alternatives:

1) Using the descripition provided, solve the problem yourself BY HAND (with paper and pencil). If you can't solve it yourself using the description provided, you'll have a hell of a time trying to code up a program that will solve it.

By doing that, you may find an easier (perhaps less computationally efficient) way, to solve the program, with code. With all the advances in computer hardware, the efficiency may not make a difference. So what if it takes an extra 0.12 seconds of run-time? :)

2) Consult other algorithm books and see if they have anything either simpler and easier to understand, or perhaps provide a functional example of a program snippet.

Naturally, Google is your friend on this.

HI,
The original PDF is here, because the author released on his website, I believe it will be fine for i posting at here:
http://www.eecs.umich.edu/~jignesh/publ/swale.pdf

I'm not sure about the two "instruction" described in nature language:
Line 4: Initialize G: each grid element contains a queue that stores references to all intersecting elements.
Line 9: Insert Mi into the queue associated with each grid square g of G which Mi intersects.



Thank you.

The queue in my idea of it, would simply be a 3rd dimension of the (2d) array which forms the grid. It would be up to you to use that 3rd dimension data ONLY as a FIFO queue. (which itself is not hard to do).

grid[row][col][depth] = Mi; would be such an insertion, where the depth # would be the next empty element. If the depth might over-run, the list queue would be the way to go, however.

Using a list queue, you might want to have a pointer in each grid element, which would point to the head of it's respective list node. Then the insertion would amount to adding another node with the new data, to the end of the list.

I want to emphasize that if you can't do this problem, by hand, then you'll find it very difficult or impossible to code up a program for it. The coding for it might be tricky, but it's understanding the whole problem to work up an algorithm, that requires the real knowledge.

That is knowledge that I simply don't have, and I wouldn't expect anyone on any forum to take the time to study the 12 page PDF to assist you.

If you can do it by hand (with paper and pencil), then work it out in English in small steps, which can be broken up into separate functions, according to their purpose. Once the steps are small enough, and arranged functionally, then it's not nearly so difficult to code up a program that changes those small steps in English, into working code.

If you can't do it by hand, you need to contact your professor or assistant, a peer, or other material, that can assist you to gain that knowledge.

Good luck!