Hello,

Let's say I have a traffic monitoring system. The stream of data
coming in records a timestamp and a speed for each vehicle.

I'd like to know what all the groups of vehicles larger than X whose
with average speed over Y is.

Any ideas how to approach this?

Cheers,
David
--
David Fetter <david (AT) fetter (DOT) org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter (AT) gmail (DOT) com

Build it, and they will come^Hplain.

On Mon, 22 Mar 2010 15:42:09 -0500, david (AT) fetter (DOT) org (David Fetter)
wrote:

First, define your terms. What is a group? What does "larger
than X" mean? (Size of vehicle? Number of vehicles in the group?)

Sincerely,

Gene Wirchenko

On 22 mar, 21:42, da... (AT) fetter (DOT) org (David Fetter) wrote:
help it ....

If this a traffic monitoring system, you may want to approach it from
the I35 taking the I45 West...

Gene Wirchenko <genew (AT) ocis (DOT) net> wrote:
Number of vehicles in the group.

Cheers,
David.
--
David Fetter <david (AT) fetter (DOT) org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter (AT) gmail (DOT) com

Just because you do not take an interest in politics doesn't mean
politics won't take an interest in you.
Pericles, statesman (430 BCE)

On Mon, 22 Mar 2010 16:12:50 -0500, david (AT) fetter (DOT) org (David Fetter)
wrote:

And what is a group?

Sincerely,

Gene Wirchenko

Gene Wirchenko <genew (AT) ocis (DOT) net> wrote:
Those vehicles, grouped in time, whose average speed is >= Y.

Let's say we're looking for groups of 20 or more vehicles whose
average speed is >= 175 kph.

The first 20 vehicles pass by at 200 kph, then another 20 pass at 100,
each at distinct times.

When vehicle 6 of the slower bunch passes, the average speed of cars
up until now is (20*200+6*100)/26 or ~176.92 kph. Vehicle 7 passes,
and the average is now ~174.07, which is under 175, so the first group
has 26 vehicles in it, and we're now looking to start the next group.

Cheers,
David.
--
David Fetter <david (AT) fetter (DOT) org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter (AT) gmail (DOT) com

To the extent that we overreact, we proffer the terrorists the
greatest tribute.
High Court Judge Michael Kirby

On 3/22/2010 2:48 PM, David Fetter wrote:
That seems to be the missing detail.

If you are grouping them in time already, then you have your answer,
just calculate the X and Y for that group, and filter out the ones that
don't match.

On Mar 22, 11:48*pm, da... (AT) fetter (DOT) org (David Fetter) wrote:
Perhaps a variation of Kadane's algorithm?

On Mar 22, 10:56*pm, Cimode <cim... (AT) hotmail (DOT) com> wrote:

David Fetter wrote:

What do you count as a vehicle? Is it just one measurement in the
record, or do you have any way of cross-identiying different
measurements as belonging to the same vehicle? Your use of
the term 'average' suggests that you do.

If you do, do you want to correct your computation of average speed
by combining measurements? E.g. when you have two speed measurements
of the same vehicle, both at 50 mph, taken 70 miles and 1 hour
apart, do you want to correct both 50s to 70?

Do you want to take averages over all measurements on a vehicle
ever done? Or per month, week, day, or some other interval?

Once this is sorted out you can write a query that will list
all vehicles and their average speeds, sorted by average speed
if you like.

Now comes the part that is very awkward in SQL: grouping based on
the ordering. (If that is what you really want, that is.)
SQL doesn't support the use of total orderings on domains very well.

The only way I see to do it is a follows. First you join the query
result against itself (so I'd put it into a table first):
the result has three attributes, namely, a vehicle V1, a
vehicle V2, and the average speed A of all vehicles with an average
speed between that of V1 and V2, inclusive. Next you select from
that table all tuples V1, V2, A such that for all V1, V2, A', either
A' < A or A' > 25 (which requires another selfjoin). Finally you
need to select all V1, V2, A from this selection such that either A
is the heighest average speed or for some vehicle V'1 with maximum speed,
there is a natural number k >=1 such that there are V'k and Ak
such that V'k = V1 and V'1, V'2, A1, ... V'k-1, V'k, Ak are
in the selection. This requires transitive closure,
which is apparently supported in modern standard SQL
by the means of recursive subqueries, which I've never used.

ALl this is awkward and extremely expensive for an operation that, if we
could just perform aggregations along a totel ordering of the domain,
would be linear. So if you have a "wrapper" language such as TSQL or
PL/SQL, write a procedure to do this.

In summary:

1) if you described your intention more clearly,
we wouldn't have to guess so much
2) if I understand your intention correctly,
I doubt your query can be expressed in relational algebra,
which may explain why you have trouble expressing it.

--
Reinier