Thread: Implement of a Fast Time Series Evaluation Algorithm

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    4

    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:

    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

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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.

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    4
    Pretty no... because I can't understand the "Grid" and "Queue q".

  4. #4
    Registered User
    Join Date
    Nov 2007
    Posts
    4
    Need help, it's beyond my ability and experience now,,, maybe i should begin from a algorithm book?

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by BiGreat View Post
    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.

  7. #7
    Registered User
    Join Date
    Nov 2007
    Posts
    4
    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.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. I apologize. Good bye.
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 05-03-2002, 06:51 PM
  2. Is this really true or it's just science fiction?
    By Nutshell in forum A Brief History of Cprogramming.com
    Replies: 145
    Last Post: 04-09-2002, 06:17 PM
  3. time class
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-11-2001, 10:12 PM
  4. First time on the forum, need help fast!!
    By JFK in forum C Programming
    Replies: 2
    Last Post: 10-07-2001, 02:17 PM
  5. relating date....
    By Prakash in forum C Programming
    Replies: 3
    Last Post: 09-19-2001, 09:08 AM