Max of series of real-time data

Hi,

I have a real-time application project for which the following problem
needs urgent input:
- an algorithm must determine the maximum (or minimum) of a series of
data (window) in an input stream from a sensor. The max. data needs be
updated every sample (5000 Hz samplerate). I need a quick way of
determining the max. element in the data window (of about 3000 - 5000
samples) without the obviously time-consuming way of comparing each
element with the next, or quicksorting, due to time constraints.

Is there a quicker way to do this?

Any input is greatly appreciated,
Andras

zimezum@gmail.com wrote:
> Hi,
> 
> I have a real-time application project for which the following problem
> needs urgent input:
> - an algorithm must determine the maximum (or minimum) of a series of
> data (window) in an input stream from a sensor. The max. data needs be
> updated every sample (5000 Hz samplerate). I need a quick way of
> determining the max. element in the data window (of about 3000 - 5000
> samples) without the obviously time-consuming way of comparing each
> element with the next, or quicksorting, due to time constraints.
> 
> Is there a quicker way to do this?

Of course there is. Keep a variable that holds the largest (or smallest) 
value so far, and compare each new sample against it. If the comparison 
fails, do nothing. If it succeeds, update the variable.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry,


Thank you for your input. One question lingers, though....when the max
data
falls out the window (so to speak) the next largest must be idetified
as the max
unless a larger value entered the window. That is, the algorithm must
have a
'forgetting factor' of some sort which is related to the size of the
window.

Suppose the input stream is a monotomic decreasing one, then all the
values in
the window must be remembered (and their order), so that when the
largest one
is leaving the window the 'max' variable will take the next largest
value, and so on,
until the smallest element is reached.

In this case every element of the window must be remembered and
compared against
the new value entering the window. Sound like a quite complicated
task...


Andras

Jerry Avins wrote:
> zimezum@gmail.com wrote:
> > Hi,
> >
> > I have a real-time application project for which the following problem
> > needs urgent input:
> > - an algorithm must determine the maximum (or minimum) of a series of
> > data (window) in an input stream from a sensor. The max. data needs be
> > updated every sample (5000 Hz samplerate). I need a quick way of
> > determining the max. element in the data window (of about 3000 - 5000
> > samples) without the obviously time-consuming way of comparing each
> > element with the next, or quicksorting, due to time constraints.
> >
> > Is there a quicker way to do this?
>
> Of course there is. Keep a variable that holds the largest (or smallest)
> value so far, and compare each new sample against it. If the comparison
> fails, do nothing. If it succeeds, update the variable.
>
> Jerry
> --
> Engineering is the art of making what you want from things you can get.
> =AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=
=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF

I think he needs to maintain the value of the maximum over the last few 
thousand samples.  This is easy to do with skip lists and data pointers on a 
small general purpose computer, maybe a PIC.  See 

http://www.nist.gov/dads/HTML/skiplist.html

or google "skip list".

In article <QLWdnXdK5fe7GDXenZ2dnUVZ_sidnZ2d@rcn.net>, Jerry Avins 
<jya@ieee.org> wrote:
>zimezum@gmail.com wrote:
>> Hi,
>> 
>> I have a real-time application project for which the following problem
>> needs urgent input:
>> - an algorithm must determine the maximum (or minimum) of a series of
>> data (window) in an input stream from a sensor. The max. data needs be
>> updated every sample (5000 Hz samplerate). I need a quick way of
>> determining the max. element in the data window (of about 3000 - 5000
>> samples) without the obviously time-consuming way of comparing each
>> element with the next, or quicksorting, due to time constraints.
>> 
>> Is there a quicker way to do this?
>
>Of course there is. Keep a variable that holds the largest (or smallest) 
>value so far, and compare each new sample against it. If the comparison 
>fails, do nothing. If it succeeds, update the variable.
>
>Jerry

Jerry Avins wrote:
> zimezum@gmail.com wrote:
> > - an algorithm must determine the maximum (or minimum) of a series of
> > data (window) in an input stream from a sensor. The max. data needs be
> > updated every sample (5000 Hz samplerate). I need a quick way of
> > determining the max. element in the data window (of about 3000 - 5000
> > samples) without the obviously time-consuming way of comparing each
> > element with the next, or quicksorting, due to time constraints.
> 
> Of course there is. Keep a variable that holds the largest (or smallest)
> value so far, and compare each new sample against it. If the comparison
> fails, do nothing. If it succeeds, update the variable.

Jerry, you gotta stop shooting from the hip on these.

What do you do when the current maximum (or minimum) value falls
out the other end of the window?

The only answer I can see would involve keeping both a queue of the
data in the window, and a separate copy of the data that's kept in
sorted order.

At each sample time, take the oldest value out of the queue, and
also delete a copy of that value from the sorted buffer (find it
using a binary search, and it doesn't matter if there's more than
one). Then insert the new value into the queue and also into the
sorted buffer, again using a binary search. Take the highest value
(or lowest value, or middle value, etc.) out of the sorted buffer
as the output of your filter.

The real trick is picking the right type of data structure to hold
the sorted data, so that the insertions and deletions themselves
aren't too computationally expensive. Ideally, you'd figure out
where the deletion needs to happen, where the insertion needs to
happen, and only shift the data in the buffer between those two
points.

-- Dave Tweed

<zimezum@gmail.com> wrote in message
news:1135117052.745749.292580@g14g2000cwa.googlegroups.com...
> Hi,
>
> I have a real-time application project for which the following problem
> needs urgent input:
> - an algorithm must determine the maximum (or minimum) of a series of
> data (window) in an input stream from a sensor. The max. data needs be
> updated every sample (5000 Hz samplerate). I need a quick way of
> determining the max. element in the data window (of about 3000 - 5000
> samples) without the obviously time-consuming way of comparing each
> element with the next, or quicksorting, due to time constraints.
>
> Is there a quicker way to do this?
>
> Any input is greatly appreciated,
> Andras

Hi Andras,
Do you have enough RAM to make 2 more arrays? 200uS is plenty of time to do
a block extrema calc. E.g. divide your N by 100 (5000/100 = 50). Keep an
array of 50 "block extrema" - that is, the max for each block of 50 data
points. Now extreme for the current window is the extreme of the 50 block
extrema and the partial blocks at each end (one incoming and one outgoing).
In parallel with your data points is an array of the running extrema
*within* the block. This array (5000 intraBlockExtrema) avoids running
through any individual data points: the extreme of the incoming block is the
current entry in the intraBlockExtrema and the extreme of the outgoing block
is intraBlockExtrema of the point you are about to dump.

I hope that makes sense. I think if you extend it and generalize it, then it
becomes the Skip List that John pointed to. Anyway, with the numbers I used
in the example, with each new data point you only make 3 comparisons. At the
end of each block, you make 50 comparisons. At some other time, you run
through the most recently full block *backwards* (making 100 comparisons)
and store those extrema to use on the outgoing comparison. On average,
around 5 comparisons per data point.

Bob

<zimezum@gmail.com> wrote in message 
news:1135117052.745749.292580@g14g2000cwa.googlegroups.com...
> Hi,
>
> I have a real-time application project for which the 
> following problem
> needs urgent input:
> - an algorithm must determine the maximum (or minimum) of 
> a series of
> data (window) in an input stream from a sensor. The max. 
> data needs be
> updated every sample (5000 Hz samplerate). I need a quick 
> way of
> determining the max. element in the data window (of about 
> 3000 - 5000
> samples) without the obviously time-consuming way of 
> comparing each
> element with the next, or quicksorting, due to time 
> constraints.
>
> Is there a quicker way to do this?
>
> Any input is greatly appreciated,
> Andras
>

Assuming that your data is integer and you have enough 
memory, here is one way to achieve what you're looking for:

1.  Allocate an array of integers that is large enough to 
hold the maximum number of different values that your data 
can take on.  For example, if you have 16-bit data, you need 
an array of 64K integers.  Each array element needs to be 
big enough to count the number of elements in your data 
window.  An array of unsigned chars will accommodate data 
windows of up to 255 points, an array of unsigned shorts 
will accommodate data windows of up to 64K-1 points and so 
on.  Initialize all the elements of this array to zero.


2.  Each time a new point is captured:

2a. use the value of the point as an index into the array 
allocated above.  Increment the array element at that index.

2b. if the value of the point is bigger than the biggest one 
previously seen, replace the old biggest value with the new 
biggest value.

2c. using the point that just shifted out of the window, 
decrement the array element whose index corresponds to that 
point's value.

2d. if the value of the point is equal to the largest value 
previously seen, and the contents of the array element 
indexed by the value of the point is zero, then search 
downward to the next array index containing a non-zero 
element.  This array index will be the new largest value in 
the data window.

This algorithm works because the big array holds an 
inventory of all the values in the data window.  When a new 
value is brought in, it is tallied in the inventory.  When 
it is dropped out, it is removed from the inventory.  Only 
values with non-zero representation in the inventory are 
candidates to be the "biggest" value in the data window, and 
then only if there are no other candidates above them in the 
inventory.

zimezum@gmail.com wrote:
> Jerry,
> 
> 
> Thank you for your input.

Too soon for that.

> One question lingers, though....when the max data falls out the window ...

I hadn't realized the significance of "(window)". Perhaps the 
parentheses threw me.

> Suppose the input stream is a monotomic decreasing one, then all the
> values in
> the window must be remembered (and their order), so that when the
> largest one
> is leaving the window the 'max' variable will take the next largest
> value, and so on,
> until the smallest element is reached.
> 
> In this case every element of the window must be remembered and
> compared against
> the new value entering the window. Sound like a quite complicated
> task...

The best I can think of is an insertion sort, done as each sample 
arrives. I can see many pitfalls trying to implement it, but maybe there 
are ways around some of them if there's enough memory. It won't be 
pretty even if it works.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

David Tweed wrote:
> Jerry Avins wrote:
> 
>>zimezum@gmail.com wrote:
>>
>>>- an algorithm must determine the maximum (or minimum) of a series of
>>>data (window) in an input stream from a sensor. The max. data needs be
>>>updated every sample (5000 Hz samplerate). I need a quick way of
>>>determining the max. element in the data window (of about 3000 - 5000
>>>samples) without the obviously time-consuming way of comparing each
>>>element with the next, or quicksorting, due to time constraints.
>>
>>Of course there is. Keep a variable that holds the largest (or smallest)
>>value so far, and compare each new sample against it. If the comparison
>>fails, do nothing. If it succeeds, update the variable.
> 
> 
> Jerry, you gotta stop shooting from the hip on these.

Yup.

> What do you do when the current maximum (or minimum) value falls
> out the other end of the window?
> 
> The only answer I can see would involve keeping both a queue of the
> data in the window, and a separate copy of the data that's kept in
> sorted order.
> 
> At each sample time, take the oldest value out of the queue, and
> also delete a copy of that value from the sorted buffer (find it
> using a binary search, and it doesn't matter if there's more than
> one). Then insert the new value into the queue and also into the
> sorted buffer, again using a binary search. Take the highest value
> (or lowest value, or middle value, etc.) out of the sorted buffer
> as the output of your filter.
> 
> The real trick is picking the right type of data structure to hold
> the sorted data, so that the insertions and deletions themselves
> aren't too computationally expensive. Ideally, you'd figure out
> where the deletion needs to happen, where the insertion needs to
> happen, and only shift the data in the buffer between those two
> points.

Another approach might be a time key with each sorted entry. Messy at 
best ... until the mental breakthrough.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

John,


So far the method you proposed seems easier for me to understand.

I'll give it a try over the next few days.

Some words about the application (so that the others will have a
better idea about what's going on);

- it is a real-time controller for (right now) a pair of magnetic
bearings
in an experimental setting at Auburn University. The h/w is a dSPACE
DS1005 board, which is in fact a PPC750 processor running at 400 MHz.
The main algorithm is a type-2 fuzzy logic controller, which takes up
most of the cycle at the 5 kHz samplerate. The adative adjustment
is still needs to be implemented, so the 200 usec is not available,
it is about 50 usec which I can affor at this point. Memory is not a
problem right now, the board is equipped with 128MB RAM which is
far more than I ever need for this kind of project.
The input sensors are connected to the 16 bit ADC (which can be
adjusted to 14,12, 10 and 8 bits for each channel).
Programming is in C language...I understand that assembly language
would give serious speed boost, but I am afraid of messing up the
proprietary dSPACE functions, interrupts, which is another can of
worms.


Andras