Hi Mirek:

I enjoyed your talk at Northeastern. I came to you briefly before your talk
and we spoke in German.

We have been working on Adaptive Programming (AP)
over the last 18 years and we have automata-theoretic
techniques that I believe are useful for stream processing. 

Consider the following scenario. We have two streams of objects s1 and
s2 and a query which says that if an object in s1 satisfies p1 then
look for the first object in s2 that satisfies p2 and
if an object in s1 satisfies q1 then look for the first object
in s2 that satisfies q2.
I assume that the objects in s1 (s2) satisfy class graph G1 (G2).
The class graph is 
a schema that gives meta-information about the stream element objects.

Consider the following concrete example:
G2 = tree of {Integer, Float, Complex} // all inner nodes have a number
p2 = all subtrees with an Integer root have a diameter > 9
q2 = all subtrees with a Float root are binary search trees

p2 and q2 have the property that only a part of the trees
need to be looked at. For example, the class graph could say
that Integers are only in left.left.right and we can ignore the rest
of the tree, significantly speeding up the processing.
It is cheaper to just flip over the information rather than
computing diameters.

In AP we use programs of the form: (schema, WhereToGo, WhatToDo)
to process streams and we have an efficient way to detect
which subobjects to skip based on the information in WhereToGo 
and schema.

WhereToGo uses XPath style constructs like the // operator.

Do you using schema information is useful for stram processing?
Is it already being used?

Our technique is based on automata-theoretic techniques:

@article{973102,
author = {Karl Lieberherr and Boaz Patt-Shamir and Doug Orleans},
title = {Traversals of object structures: Specification and Efficient Implementation},
journal = {ACM Trans. Program. Lang. Syst.},
volume = {26},
number = {2},
year = {2004},
issn = {0164-0925},
pages = {370--412},
doi = {http://doi.acm.org/10.1145/973097.973102},
publisher = {ACM Press},
}

-- Karl