BiGreat

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:

Attached Images

  

matsp

Show us what you've done so far.

--
Mats

__________________
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.

BiGreat

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

BiGreat

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

Salem

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.

__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
Up to 8Mb PlusNet broadband from only £5.99 a month!

Adak

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.

BiGreat

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.

Adak

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!