SKETCHING THE ORDER OF EVENTS
TERRY LYONS AND HARALD OBERHAUSER

arXiv:1708.09708v1 [stat.ML] 31 Aug 2017

Abstract. We introduce features for massive data streams. These stream features can be
thought of as “ordered moments” and generalize stream sketches from “moments of order
one” to “ordered moments of arbitrary order”. In analogy to classic moments, they have
theoretical guarantees such as universality that are important for learning algorithms.

1. Introduction
L
is a sequence of events. An event σi
1.1. The streaming problem. A stream σ = (σi )i=1
is a tuple σi = (λi, ai ) ∈ R × A where A denotes a finite but typically very large set. Our
task is to compute a summary of the stream

Φ (σ1, . . ., σL )
and to update it on arrival of a new event. This summary Φ (σ) should be rich enough
to efficiently describe the effects of the stream σ = (σ1, . . ., σL ), that is allow to make
inference about functions f (σ) of the stream. We refer to Φ as feature map and in this
article we focus on so-called cash register streams, that is the space of events E = R>0 × A
has only positive increments. We callÐσi = (λi, ai ) ∈ E the event with counter increase
λi ≥ 0 in the letter a and we call S = L≥1 E L the set of cash register streams; see [24]
for more background on data streaming.

1.2. Examples. Streams taking values in large sets arise in many applications: parsing a
text word-by-word or letter-by-letter (λi ≡ 1 with | A| ≃ 27 if ASCII characters or | A| ≃ 105
if English dictionary words are parsed); recording network traffic in a router (λi > 0
is the data volume and | A| ≃ 1038 IP adresses); in the order book of a stock exchange
(λi > 0 denoting trading volume, | A| ≃ 104 traded assets); etc. Effects of streams are
functions f (σ1, . . ., σL ): the function that categorizes texts into “drama”, “comedy”,
“news”, “gossip”; the function that decides if a network traffic stream contains abnormal
patterns; the functions that detects trading patterns in stocks; etc. In all these examples,
the order in which elements of the stream are received carries relevant information.
1.3. Features. We construct a map Φ from the space of streams into a linear space
σ = (λi, ai ) 7→ Φ (σ)
such that
(1) (Efficient algorithms) Φ (σ) can be well approximated
(a) in logarithmic space complexity in | A|,
(b) in “streaming fashion”: with a single pass over the stream σ = (σi ).
(2) (Universal features) Φ linearizes non-linear functionals f of streams, i.e.
f (σ) ≃ hℓ, Φ (σ)i
where ℓ is a linear functional of Φ (σ) and above holds uniformly over streams σ.
This is known as “universality” in the machine learning literature and justifies the
use of standard learning algorithms such as linear classifiers.
1

SKETCHING THE ORDER OF EVENTS

2

(3) (Pattern queries) The coordinates of Φ (σ) are indexed by words build from the
alphabet A and have natural
Í interpretation as counting patterns in σ, e.g. Φa (σ) =
Í
=
λ
1
,
Φ
(σ)
ab
i< j λi λ j 1ai =a,ai =b . Operations on streams become algei i ai =a
braic operations in feature space, e.g. stream concatenation amounts to a (noncommutative!) multiplication in feature space.
(4) (Scaling limits) the feature map allows to understand the scaling limit, that is when
the number of events in the stream becomes very large, L → ∞. Additionally, it is
robust under noisy observations.
Point (1) is a central theme in the streaming community with spectacular progress in recent
years [1, 3, 9, 24]; Point (2) is a standard requirement for guarantees of most machine
learning algorithms (“universality of features”); Point (3) and Point (4) are a central theme
in stochastic analysis [21, 11]. Providing features that address all four points is the goal
of this article.
L

L
as an element of R| A| and apply standard features
Remark 1. One can identify σ = (σi )i=1
for vector-valued data. This approach becomes computationally infeasible for large L.
Further, methodological problems arise since streams of different lengths are mapped to
different feature spaces, etc.

Remark 2. In analogy to the count-min sketch [3, 4], our feature sketch can be modified to
deal with with ℓ2 -error bounds (instead of ℓ1 ) to deal with turnstile instead of cash-register
streams etc.; the needed modifications are analogous to the classic case, see Remark 12.
1.4. Sketching. Already for simple features Φ it is not easy to address Point (1) and often
it can be shown that the computational problem is NP-hard in space. A very successful
approach to reduce the computational complexity are so-called sketches, that is small data
structures that rely on randomized algorithms
 [1, 3, 9, 24]. These algorithms compute for
given ǫ, δ > 0 a random variable Φ̂ (σ) = Φ̂i (σ) , such that the relative error is small in
probability
!
Φi (σ) − Φ̂i (σ)
P
< ǫ > 1 − δ for every coordinate Φi (σ) of Φ (σ) = (Φi (σ)) .
kΦ (σ)k
An important case is when the feature map are letter frequencies, that is Φ (σ) ∈ R| A| with
each coordinate being the frequency of an element1 in A and kΦ (σ)k denotes the 1-norm.
Cormode and Muthukrishnan [6] show that in this case, Φ̂ (σ) can be constructed by
sampling a random matrix L ∈ Rm×| A| with m ≪ | A| and storing only the m-dimensional,
random vector
(1.1)

LΦ (σ) .

In contrast to compressed sensing, the entries of L are not i.i.d. but have a rich structure.
This allows to construct the estimator Φ̂ (σ) from the low-dimensional, random vector
(1.1) without solving a constrained minimization problem. Moreover this sketch is linear
in the sense that,
Φ̂ (ασ, βτ) = αΦ̂ (σ) + βΦ̂ (γ) for α, β ∈ R
where multiplication with scalars of streams is defined as ασ = (αλi, ai ) and (ασ, βτ) is
simply the concatenation of the streams ασ and βτ. A drawback of the such choices for
L
1That is, if σ = (λi, ai )i=1
the coordinate for a ∈ A equals

Í

i:ai =a λi .

SKETCHING THE ORDER OF EVENTS

3

Φ (such as letter frequencies, number of distinct letters, moments of frequencies, etc.) is
that they are order agnostic,
Φ (σ) = Φ (σ π )


where σ π = σπ(1), . . ., σπ(L) and π is a permutation of {1, . . ., L}. While such order
agnostic features are useful and widely used in practice, they only very partially fulfill
Points (2), (3), (4) and for many applications the order information carries important
information, see the above examples 1.2.
1.5. Related work and contributions. Finding efficient summaries of patterns in sequences (also called substrings, motifs, etc.) is a classic theme in computer science, data
mining and machine learning [18]:
(1) A standard machine learning approach are string kernels. These capture the order
of events and have already been combined with sketches [29]. However, they only
apply to constant counter-increases λi ≡ 1, and the behavior and universality as
L → ∞ (Point 2 and Point 4) is not discussed.
(2) The engineering community developed algorithms such as SPADE, APriori, Freespan,
[14, 33], etc. to find patterns. Usually, properties such as universality that are relevant to machine learning tasks are not discussed (Point (2),(3),(4) above).
(3) Describing a sequence as a formal power series in non-commutative variables is a
well-known technique in many areas of mathematics [5, 13, 21]. For small alphabets, this was used for for various learning/statistical tasks [25, 31, 12, 17]; further,
the kernelization developed in [16] covers large alphabets and string/ANOVA/time
warping kernels arise as a special cases; however, the latter restricts to kernelized
learning algorithms and gives no pattern queries.
(4) Sketches have been used for learning and optimization tasks [10, 26, 32], see
for example [15] for detection of trends in time series, but in a stream/sequential
context these results are usually discussed without theoretical guarantees such as
universality or scaling limits, Points (2) and (4).
To sum up: some classic constructions (such as string kernel features, frequency sketches,
etc.) arise as special cases or are realted to our approach. However, the central theme of
our approach is to focus on the functions of stream and how sketches of features allow
to linearize such functions. The key to to this is the algebraic-analytic background that
allows to prove properties that address Points (2), (3), (4). More precisely, is capture in
the interplay of two algebras
• a graded, non-commutative algebra as the feature space (to capture order information),
• a graded, commutative algebra of linear functionals of features (that is dense
among function on streams),
which can be elegantly formulated as an Hopf algebra. Another perspective that we
develop in a streaming context is to identify a stream as a lattice path in the free vector
space spanned by the alphabet A. This elementary observation allows us to apply insights
from stochastic analysis and rough path theory to the study of streams, e.g. it gives a useful
topology on S and clarifies the behaviour as then number of events goes to infinity, etc.
In turn, developing sketching ideas from this perspective allows for efficient computation,
thus also addressing Point (1) which ultimately allows to learn nonlinear functions of
massive data streams.

SKETCHING THE ORDER OF EVENTS

4

Remark 3. We are motivated by the count-min sketch. The underlying principle (streams
as paths that are injected into the algebra of non-commutative polynomials) is not restricted
to the count-min sketch and it is an interesting question how it can be applied to other
classic sketching algorithms such as [1, 7], or other approaches to summarize massive
streams such as sampling [8].
1.6. Applications and experiments. In Section 4 we discuss applications. These include
pattern queries and building the list of patterns of heavy hitters with a single parse over
the stream; M = 1 recovers the usual heavy hitter sketch. Many effects of streams are
given by functions f (σ) that are well approximated
by considering only the substream


H
H
σ consisting of heavy hitters, f (σ) ≈ f σ . By combining universality of Φ and our
sketching result this allows to approximate

 D

E
f (σ) ≈ f σ H ≈ ℓ, Φ̂ σ H .
For example, f could assign a label to streams (normal/abnormal stream) and one can
train a standard learning algorithm to find the linear functional ℓ.
In Section 5 we give numerical examples. Our algorithms are easy to parallelize and
thus can make use of multi-threading on several CPUs or GPUs to parse high-volume
streams. We implemented our algorithms in C++ and ran the following experiments on
synthetic data:
(1) (Speed and ground truth). We evaluated our algorithms on a deterministic
stream. The dimensions of the stream was chosen such one can still calculate the
ground truth for ordered moments up to M = 3. We then compared it to the error
introduced by sketching and the speed.
(2) (Classifying Markov chains). We sample streams from two Markov chains in a
state space A consisting of | A| = 105 letters. Even in such a simple toy model of
high-dimensional streams, order-agnostic features can become quickly useless but
sketches of patterns allow to efficiently train classifiers.
2. from local events to global summaries
Fix a finite set A of letters and denote with
Ø
Ø
L
S =
EL =
: σi ∈ E
σ = (σi )i=1
L≥1

L≥1

the set of turnstile streams consisting of an arbitrary number of elements, so-called events,
in E = R>0 × A. Further, denote with
A⋆ = {a1 · · · a M : a1, . . ., a M ∈ A, M ≥ 0}
the set of words; we denote the empty word with 1. Let
)
(
Õ
cw w : cw ∈ R
F := R hhAii :=
w∈A⋆

be the linear space of formal power series in | A| non-commuting variables. Below we
show how to construct feature maps
Õ
Φ : S → F , σ 7→ Φ (σ) =
Φw (σ) w
w

by “stitching events together in feature space”.

SKETCHING THE ORDER OF EVENTS

5

2.1. From local events to global descriptions. Fix a so-called event map
p:E→F
We evaluate p along the stream σ1, σ2, . . . and update our features by (non-commutative!)
multiplication in F
(2.1)

Φ (∅) = 1,
Φ (σ1, . . ., σL+1 ) = Φ (σ1, . . ., σL ) p (σL+1 )

The non-commutativity of the multiplication in the feature space F captures the order
information. A priori there are many possible choicesÍfor the event map p, each choice
results in different coefficients (Φw (σ))w∈A⋆ of Φ (σ) = Φw (σ) w ∈ F . More importantly,
different choices of p give rise to different algebraic structures on the dual of F .
Example 4. Consider the feature map
(2.2)

p (λ, a) = 1 + λa.

(2.3)

Φ (σ) = (1 + a) (1 + 1.5b)(1 + b) (1 + 2a)
= 1 + 3a + 2.5b + 2a2 + 2.5ab + 5.5ba + 1.5b2.


With A = {a, b} and σ = ((1, a), (1.5, b), (1, b), (2, a)). Then A⋆ = 1, a, b, a2, ab, ba, b2, a3, . . .
and

Note that each coordinate Φw (σ) counts how often w appears as subword in σ relative to the
counter-increases λi ; the map (2.2) was introduced in [16] in the context of sequentializing
kernels; e.g. for a stream with constant counter-increase λi ≡ 1, Φ (σ) recovers the classic
vanilla string kernel features [19] and similarly one recovers ANOVA features etc., see
[16].
Example 5. Let
p (λ, a) = 1 + λa +

λ2 a2
+··· .
2!

This leads to the feature map
!
!



a2
b2
(1.5b)2
(2a)2
Φ (σ) = 1 + a + + · · · 1 + 1.5b +
+ · · · 1 + b + + · · · 1 + 2a +
+···
2!
2!
2!
2!


1 22 2
(2.4)
a + (1.5 + 1) ab + · · · .
= 1 + 3a + 2.5b + 2 + +
2! 2!

The coefficients are somewhat less intuitive than in above Example 4 but lead to a classic
algebraic structure (the shuffle algebra, Appendix B). Moreover, as L → ∞ this choice of
event map still makes sense for turnstile streams, whereas Example 4 leads to problems
in the limit L → ∞ when turnstile streams are considered and rough paths appear, see the
discussion [16] for further details in a (kernel) learning context.
Remark 6. The algebraic structure of Example 5 is the classic shuffle Hopf algebra, whereas
the (Hopf) algebra arising from Example 4 was at least new to us, see Theorem 32 and
Theorem 35 in the Appendix B.
Remark 7. An interesting question is how to construct a commutative product on the dual
of F ′ for a given event map p and vice versa. Note that the non-commutative product
(formal power series multiplication) in F is the same for all choices of p.

SKETCHING THE ORDER OF EVENTS

2.2. (Pseudo-)Norms. For f =

Í

6

∈ F define
Õ
k f k1 =
|cw |

w cw w

w

(with the convention k f k 1 = ∞ if the sum does not converge). For a word w = a1 · · · a M ∈ A⋆
define its length |w| = M as the number of letters in w. For M ≥ 1 define
Õ
Õ
|cw | .
|cw | and k f k 1,(M) =
k f k 1,M =
w:|w|=M

w:|w|≤M

None of these are norms on F (but on appropriate sub- or quotient-spaces). However they
appear naturally in our calculations.
2.3. Some algebra and feature universality. Denote with
)
(
Õ
cw w : cw ∈ R and cw = 0 for infinitely many w
F ′ := R hAi =
w∈A⋆

the subset of F that consists of finite sums. We identify elements of F ′ as linear functionals
acting on F via the pairing
Õ
Õ
Õ
cw dw where ℓ =
dw w, P =
dw w.
h·, ·i : F ′ × F → R, hℓ, Pi :=
w

w

w

F′

A far reaching result is that
can be equipped with a commutative multiplication, that is
for ℓ1, ℓ2 ∈ F ′ there exists a ℓ ∈ F ′ that is given by multiplication of ℓ1, ℓ2 such that
hℓ1, Φ (σ)i hℓ2, Φ (σ)i = hℓ, Φ (σ)i .
Thus
{σ → hℓ, Φ (σ)i, ℓ ∈ F ′} ⊂ RS
is an algebra of functions on streams. Equipping S with bounded variation topology it
follows that any continuous function of the stream f ∈ C (S, R) can be approximated by a
ℓ ∈ F′
f (·) ≈ hℓ, Φ (·)i,
uniformly over compact sets in S. In the terminology of machine learning [23], the
features (Φw (σ))w are “universal” and this allows to use linear learning algorithms; we
provide the full details in the appendix A and B.
Remark 8. Algebraically it makes more sense to introduce F as the dual of F ′, see
Appendix B. However, in a learning context we regard Φ (σ) ∈ F as features and learn
about σ by linear functionals ℓ ∈ F ′.
Remark 9. The coefficients (Φw (σ))w carry redundant information: a simple calculation shows that (Φa (σ), Φb (σ), Φab (σ) − Φba (σ))a,b∈A already completely determines
(Φw (σ))w∈A⋆,|w|≤2 . The reason is that Φ (σ) lives in a nonlinear subset of F ; in the case
p (λ, a) = exp (λa) this is the free Lie group generated by | A| variables and the previous
observation is simply that we can work in the Lie algebra instead of the Lie group.

 MHow| A|
ever, a classic result of Bourbaki is that the dimension of the Lie algebra is O M as
M → ∞, i.e. this does not kill the exponential growth. Nevertheless, our main sketch can
be immediately applied to the Lie algebra which leads to a reduction of computational
cost by a constant for the price of more complicated algebraic objects.

SKETCHING THE ORDER OF EVENTS

7

2.4. Streams, paths and scaling limits. Given a stream σ ∈ S we can identify it as a
path in the free vector space spanned by the letters A. That is, identify the set of letters A
as ONB basis for R| A| and an event σi = (λi, ai ) as the vector λi ai ∈ R| A| . Consequently
L
can be seen as the continuous path γ in the free vector space spanned by A
σ = (λi, ai )i=1
given by the Donsker embedding
t 7→ γ (t) := σ ⌈Lt⌉ (Lt − ⌊Lt⌋) +




⌊Lt⌋
Õ

σi,

i=1

That is we inject S ֒→ C [0, 1], R| A| by linear interpolation, see for example Figure (2.1).
This gives a topology on streams S that captures the intuitive notion of streams as being
similar if they have similar events and length. Further, it allows to study what happens if
the number of events goes to infinity, L → ∞, and it gives another interpretation to our
features Φ (σ), namely
ˆ
dγ a1 (t1 ) · · · dγ a M (t M ) .
(2.5)
Φa1 ···a M (σ) =
0≤t1 ≤···≤t M ≤1

We give full details in the Appendix B. From this point of view, our sketch chooses
a random


but very structured linear map H from R| A| to Rd for d ≪ | A| to turn γ ∈ C [0, 1], R| A| into

γ̂ = (Hγ (t)) ∈ C [0, 1], Rd that gives good estimates for the large coordinates of (2.5).
b

a
Figure 2.1. The stream σ = ((1, a), (1.5, b), (1, b), (2, a)) as a path in the
free vector spaced spanned by the letters a, b.
3. Sketching the order of events
The algebraic construction of the feature map
Φ : S → F,

σ=

L
(σi )i=1

7→ Φ (σ) =

L
Ö

p (σi )

i=1

based on a event map p : E → F gives theoretical guarantees that address Points (2),(3),(4)
mentioned in the introduction, see Appendix A and B for details. In this section, we present
our main result that addresses the computational aspect, Point (1): although F is infinite
dimensional, it is graded by word length. Analogous to the classic case of polynomials in
commuting variables as features, a sensible approach is to truncate at a given degree M,
i.e. to consider
Õ
Φw (σ) w.
Φ M (σ) :=
|w|≤M

SKETCHING THE ORDER OF EVENTS

8

(in supervised learning tasks, M is a parameter that must be chosen as to minimize the
generalization error, e.g. in a supervised setting by cross-validation). Unfortunately, the
combinatorial explosion of coordinates is


M
|{Φw (σ) : |w| ≤ M }| = O | A|

and for many streaming applications | A| is so large that already M = 1 is infeasible. Our
main theorem is

Theorem 10. Let σ ∈ S. For every ǫ, δ > 0 there exists a F -valued random variable Φ̂ (σ)
such that
!
Φ̂w (σ) − Φw (σ)
P
> ǫ < δ, ∀w ∈ A⋆ with |w| ≤ M
kΦ (σ)k 1,(M)
and we can compute the set of coordinates

Φ̂w (σ) : |w| ≤ M


using O ǫ −M log 1δ memory units2 ,⌈− log δ⌉ log | A| random bits and a single pass over
σ using Algorithm 1.
ÍL
We can express the error estimate also in terms of the length of σ, kσk = i=1
|λi |.

Corollary 11. Let σ and Φ̂ (σ) be as above. Then


kσk M
P Φ̂w (σ) − Φw (σ) > ǫ
<δ
M!
for every word w of length |w| = M.

Note
• the appearance of the 1-norm kΦ (σ)k 1,(M) . Above is a very good estimate for
“heavy hitter patterns”, i.e. for power law type distributions in the coordinates
(Φw (σ))w∈A⋆ ,
• the alphabet size | A| appears only in a logarithm
in the computational complexity,

• that applied with M = 1, above calculates Φ̂a (σ) : a ∈ A and Algorithm 1 is then
simply the count-min frequency sketch of Cormode–Muthukrishnan [6].
Remark 12. Above can be modified for cash-register streams with simple modifications:
the first option is to replace the coordinate-wise minimum by a median; the second option
is to use a count-sketch [3, 4] giving an additional factor of ǫ −1 in space complexity.
Similarly, we can replace the 1-norm by other norms in analogy with standard sketches,
M = 1. This leads to higher computational complexity, analogous to the letter frequency
case, see [24].
The rest of Section 3 is devoted to the proof of Theorem 10. It is a simple but instructive
exercise to run through the remainder of this section for the special case M = 1 (not
patterns, just frequencies) and see how this recovers the standard proof the count-min
sketch [6].
2A memory units stores a positive real number. For implementations the usual considerations and
additional cost to deal with rounding errors, floating numbers, etc. apply.

SKETCHING THE ORDER OF EVENTS

9

3.1. Hashed streams. Fix a function h : A → B, where B is finite set with |B| < | A|. We
study how much information we can recover about Φ (σ) if we only observe the hashed
stream σ h := (λi, h (ai ))i of the stream σ = (λi, ai )i . To do so, we work with three objects:
 
Φ (σ) ∈ F , Φ σ h ∈ R hhBii, Φ h (σ) ∈ F ,

the original features Φ (σ), the features Φ σ h of the hashed stream σ h and the third
object, denoted Φ h (σ), is the “pull-back” of Φ σ h to F = R hhAii.

Definition 13. Let B be a finite set and h : A → B. For σ = (σi ) with σi = (λi, ai ) ∈ R>0 × A,
define
 
σ h := σih with σih := (λi, h (ai )) ∈ R>0 × B.

We call σ h the h-hash of σ.

We are interested in the situation where B is much smaller than the
 original alphabet
h
A such that we can afford the computational cost to calculate Φ σ ∈ R hhBii. Given
Φ σ h we “pull back” these features to F to get an approximation of Φ (σ).

Definition 14. Define Φ h (σ) ∈ F as

D  
E
hΦ h (σ), wi := Φ σ h , h (w) for w ∈ A⋆

where h (w) := h (a1 ) · · · h (a M ) ∈ B⋆ for w = a1 · · · a M ∈ A⋆.

If |B| < | A| then h is not injective, h (a) = h (b) for a , b. These collisions are the reason
Φ h (σ) overestimates Φ (σ).
Lemma 15. For any h ∈ B A we have
hΦ (σ), wi ≤ hΦ h (σ), wi for all w ∈ A⋆ .
Lemma follows directly from the formulas for Φ (σ) given in Theorem 32. In fact, we
get the following explicit expression for this bias.
L
∈ S. Then
Proposition 16. Let h ∈ B A and σ = (λi, ai )i=1
(Í
λ(i)
1
if p (λ, a) = exp (λa),
Φ h (σ) = Φ (σ) + b and hb, wi = Í(1) i! h(a(i))=h(w)
if p (λ, a) = 1 + λa.
(2) λ (i) 1 h(a(i))=h(w)
Í
where the sum (1) is taken over allÍi = (i1, . . ., i M ) such that i1 ≤ · · · ≤ i M and a (i) , w
where a (i) := ai1 · · · aiM ; for the sum (2) we additionally assume i1 < · · · < i M .

Proof. If p (λ, a) = exp (λ, a) (the other case follows by similar arguments) then we know
Í
that hΦ (σ), wi = λ(i)
i! where the sum is over i, i1 ≤ · · · ≤ i M such that a (i) = w . Now
from Theorem 32 we know that
D  
E Õ λ (i)
1 h(a(i))=h(w)
hΦ h (σ), wi ≡ Φ σ h , h (w) =
i!
with the sum over all i, i1 ≤ · · · ≤ i M . The statement follows by splitting 1 h(a(i))=h(w) =
1a(i)=w + 1a(i),w 1 h(a(i))=h(w) .

L
∈ S we have
Corollary 17. Let H be a B A-valued random variable. For σ = (λi, ai )i=1

E [ΦH (σ)] = Φ (σ) + bias (σ),
(Í
λ(i)
P (H (a (i)) = H (w))
where hbias (σ), wi = Í(1) i!
(2) λ (i) P (H (a (i)) = H (w))

if p (λ, a) = exp (λa),
if p (λ, a) = 1 + λa.

SKETCHING THE ORDER OF EVENTS

10

As a consequence, if P (H (w) = H (w′)) ≤ q for words w , w′, |w| = |w′ | = M then
0 ≤ hbias (σ), wi ≤ q kΦ (σ)k 1,(M) for w ∈ A⋆ with |w| = M .
Í
Í
Í
λ(i) Í
1a(i)=w = w:|w|=M Φw (σ) ≡ kΦ (σ)k 1,(M) ,
Proof. Note that i:i1 ≤···≤iM λ(i)
w
≤···≤i
1
M
i! = i:i
i!
hÍ
i
Í
hence the statement follows since E (1) λ(i)
≤ q i:i1 ≤···≤iM λ(i)
1

H(a(i))=H(w)
i!
i! .

3.2. Combining independent hashes. We get tail estimates for ΦH (σ) for a randomly
chosen H.
Proposition 18. Let M ∈ N and H be a B A-valued random variable. Then
 kbias(σ)k 1, M
for x > kbias (σ)k 1,M ,
(1) P kΦH (σ) − Φ (σ)k 1,M > x ≤
x
(2) P (hΦ (σ), wi ∈ [hΦH (σ), wi − x, hΦH (σ), wi]) ≥ 1 − hbias(σ),wi
for w ∈ A⋆, x >
x
hbias (σ), wi
As a consequence, if P (H (w) = H (v)) ≤ q for words w , v, |w| = |v| = M then

 1

P hΦ (σ), wi ∈ hΦH (σ), wi − 2q kΦ (σ)k 1,(M) , hΦH (σ), wi ≥ .
2
Proof. We apply the Markov inequality and Corollary 17 to
Õ
hΦH (σ) − Φ (σ), wi
kΦH (σ) − Φ (σ)k 1,M =
w:|w|≤M

to get

 kbias (σ)k 1,M
P kΦH (σ) − Φ (σ)k 1,M > x ≤
.
x
Similarly, applying Markov’s inequality coordinate-wise shows
hbias (σ), wi
.
P (|hΦH (σ), wi − hΦ (σ), wi| > x) ≤
x
Hence,
hbias (σ), wi
P (hΦ (σ), wi ∈ [hΦH (σ), wi − x, hΦH (σ), wi]) ≥ 1 −
.
x
By Corollary 17,
(Í
λ(i)
P (H (a (i)) = H (w)) if p (λ, a) = exp (λa),
hbias (σ), wi = Í(1) i!
if p (λ, a) = 1 + λa.
(2) λ (i) P (H (a (i)) = H (w))
and hbias (σ), wi ≤ q kΦ (σ)k 1,(M) . This shows

P (hΦ (σ), wi ∈ [hΦH (σ), wi − x, hΦH (σ), wi]) ≥ 1 − q

kΦ (σ)k 1,(M)
x

for x > q kΦ (σ)k 1,(M)

The statement follows by choosing x = 2q kΦ (σ)k 1,(M) .



Since ΦH overestimates Φ, Lemma 15, we can take independent copies of H and take
the coordinate-wise minimum to combine these estimators.
Proposition 19. Let H1, . . . Hr be independently and identically distributed B A-valued
random variables. Assume there exists a q > 0 such that for

P H j (w) = H j (w′) ≤ q for j = 1, . . ., r and w, w′ ∈ A⋆, w , w.

Then for any w ∈ A⋆


(1) P min j=1,...,r ΦH j (σ), w − hΦ (σ), wi > 2q kΦ (σ)k 1,(M) ≤ 2−r ,

SKETCHING THE ORDER OF EVENTS

11




≥ 1−2−r
(2) P hΦ (σ), wi ∈ min j ΦH j (σ), w − 2q kΦ (σ)k 1,(M) , min j ΦH j (σ), w

where M = |w| denotes the length of the word w ∈ A⋆.

Proof. Using Proposition 18 with x = 2q kΦ (σ)k 1,(M) , independence and ΦH j (σ), w ≥
hΦ (σ), wi yields


r
Ö

P min ΦHi (σ), w − hΦ (σ), wi > x =
P ΦHi (σ), w − hΦ (σ), wi > x
i=1,...,r

=

i=1
r
Ö

P hΦ (σ), wi <

i=1
−r

≤ 2 .



ΦHi (σ), w − x, ΦHi (σ), w


Unfortunately, sampling uniformly from B A is too expensive: there are |B| | A| such
functions to choose from, so specifying an element of B A requires | A| log |B| bits of
memory. This is prohibitively expensive for our applications where A is a very large set.
Fortunately, this a classic topic in computer science solved by universal hashes.
3.3. Universal hashes. We sample uniformly from a subset H ⊂ B A. Our goal is to
construct a set H such that the assumptions of Proposition 19 are met, that is we need to
bound P (H (w) , H (w)) for w , w′. Constructing such families of functions is not trivial
but a classic topic in hashing.
Definition 20. Fix H ⊂ B A. Let H be a chosen uniformly at random from H . We call H
a 2-universal family of hash functions if
P (H (a) = H (b)) ≤ |B| −1
for a , b.
Since P (H (a1 · · · a M ) = H (b1 · · · b M )) ≤ supi P (H (ai ) = H (bi )) this is enough to apply
Proposition 19.
Example 21. Let A = {1, . . ., m}, B = {1, . . ., n}. For any prime p ≥ m, the set

H = ha,b |ha,b (x) = (((ax + b) mod p) mod n), 1 ≤ a ≤ p − 1, 0 ≤ b ≤ p − 1 ⊂ B A

is 2-universal. Hence choosing a random element of H requires 2 log p random bits.

3.4. Sketching features. Since for every random hash, the estimator ΦH (σ) overestimates
Φ (σ) we simply take the minimum to get a better estimator Φ̂ (σ) for Φ (σ). The specific
choice of alphabet size and number of hashes will become clear from the probabilistic
bounds given in Proposition 23.
Definition 22. For ǫ,
δ > 0 let H ⊂ B A be a 2-universal family into an alphabet B of car
dinality |B| = 2ǫ −1 . Draw r = ⌈log δ⌉ elements H1, . . ., Hr independently and uniformly
from H and define the random map
σ 7→ Φ̂ (σ) ∈ F by Φ̂w (σ) := min

i=1,...,M

We call Φ̂ (σ) the (ǫ, δ)-count-min-sketch of Φ (σ).
Applying the previous estimates yields

ΦHi (σ), w for w ∈ A⋆ .



SKETCHING THE ORDER OF EVENTS

12

Proposition 23. Let Φ̂ (σ) be the (ǫ, δ)-count-min-sketch of Φ (σ). Then




P Φw (σ) ∈ Φ̂w (σ) − ǫ kΦ (σ)k 1,(M) , Φ̂w (σ) ≥ 1 − δ for all w ∈ A⋆ with |w| = M .

Algorithm 1 computes for given (ǫ, δ, M) the set of coordinates

Φ̂w : |w| ≤ M


1
1
with a single pass over σ using O ε M log δ memory units and ⌈− log δ⌉ log | A| random
bits.
Proof. By universality of H we have P (H (w) = H (w′)) ≤ supa,b∈A,a,b P (H (a) = H (b)) ≤
|B| −1 . Thus the assumptions of Proposition 19 are met with q = 2−1 ǫ. Using the 2-universal
hash family, we can store
rhash functions in 2r log | A| random bits. Each hΦH (σ), wi for


M
|w| ≤ M requires O |B| = O ǫ −M of storage, thus for r ≡ ⌈− log δ⌉ hashes we need


1
1

O ε M log δ memory units.
4. Applications: pattern queries and heavy hitter patterns

4.1. Pattern queries. Theorem 10 allows to estimate patterns in the stream σ. For the
event map p (λ, a) = 1 + λa, recall that the resulting features are
Õ
λi1 · · · λiM
Φw (σ) =
(1)

with the sum taken over all i1 < · · · < i M such that ai1 · · · aiM = w. Thus they count how
often a word w appears within the stream σ, weighted by the counter increases. Algorithm
1 calculates the estimator Φ̂(M) (σ) that is given in Theorem 10. The same applies with
p (λ, a) = exp (λ, a) though in this case we allow for i1 ≤ · · · ≤ i M and account for this with
a factorial i!1 . .
4.2. Patters of heavy hitters. Fix a threshold ρ > 0 and M ∈ N. Denote
H (σ) = {a ∈ A : Φa (σ) ≥ ρ}
Í
where we recall the definition kΦ (σ)k 1,M = w:|w|=M Φw (σ). The standard (count-min)
sketch produces a random set Ĥ such that H ⊂ Ĥ and Ĥ \H is small. Recall one of our
motivations in the introduction was to learn effects/functions of streams
f :S→R
from the sketch Φ̂ (σ). A common scenario

 is that f (σ) is well approximated by the
H
stream of heavy hitters, i.e. f (σ) ≈ g σ
where g denotes simply the restriction of f

to streams in letters in H ≡ H (σ), and σ H = (ai, λi )ai ∈H . Combining the universality Φ,
Proposition 30, with the sketch of Theorem 10 yields


f (σ) ≈ g σ H
D

E
H
≈ ℓ, Φ σ


Õ
=
ℓw Φw σ H .
w∈(H (σ))⋆

SKETCHING THE ORDER OF EVENTS



Thus we can train a linear learning algorithm with Φ̂w (σ)
ℓ ∈ F ′.

13

w∈H (σ)⋆

as features to find

Definition 24. Let ρ > 0 and M ≥ 1. We call
H (σ) = {a ∈ A : Φa (σ) > ρ}
the set of heavy hitter letters of threshold ρ for the stream σ. We call
o
n
HM (σ) = w ∈ H (σ)⋆ : Φw (σ) > ρ |w|
the set of heavy patterns of length M of threshold ρ of the stream σ.

Remark 25. A subtlety is that coordinates of words of different lengths scale differently:
if we replace σ = (λi, ai ) with σ c = (cλi, ai ) for some c > 0 then Φw (σ c ) = c |w| Φw (σ)).
Thus it is natural to scale the threshold accordingly as done in above definition.
To carry out the above
learning
method (find the heavy hitter patterns HM , train a


learning algorithm on Φ̂w (σ)
) we need to compute the set of heavy hitter patterns
w∈HM


HM . We could use Theorem 10 and query the sketch for all O | A| M coordinates but this
is too expensive. Instead, as in the M = 1 case, one can approximate the list HM while
parsing the stream.
Theorem 26. For given threshold ρ > 0, Algorithm 2 computes for a given stream σ a
random set of words Ĥ such that
• HM (σ) ⊂ Ĥ ,


• If w < HM (σ) with Φw (σ) < ρ − ǫ kΦ (σ)k 1,(M) then P w ∈ Ĥ < δ.


1
−M
Algorithm 2 uses one pass over σ, O ǫ log δ memory units and ⌈− log δ⌉ log | A|
random bits.
Proof. Since the sketch of Theorem 10 overestimates,
Φ̂w (σ) ≥ Φw (σ) for all w ∈ A⋆
it follows that every w ∈ A⋆ with Φw (σ) > ρ will be an element of Ĥ . On the other hand,
by Theorem 10 Φ̂w (σ) > Φw (σ) + ǫ kΦ (σ)k 1,(M) occurs with probability smaller than δ.
Hence, if Φw (σ) < ρ − ǫ kΦ (σ)k 1,(M) , the probability of erroneously including w is less
than δ. The computational complexity is the same as in Theorem 10 up to a constant since
we only additionally check Φ h (σ) > ρ at every event.

Remark 27. Similar to the count-min sketch for finding the set of heavy hitter letters,
choosing the threshold ρ can be an issue: if ρ is too big, the set of heavy hitters stays
empty, if it is choose too small it the set HM (σ) becomes quickly too large. One approach
is to run above heavy hitter pattern sketch simultaneous for different thresholds and stop
calculating the associated heavy hitter list as soon as it becomes too big. Note that this
can be done with the same sketch Φ̂, thus the additional computational overhead is minor.
5. Experiments
The sketch of Theorem 10 provides an estimate for every coordinates Φw (σ), not only
the heavy hitter coordinates. In general it is an interesting question how to summarize the

SKETCHING THE ORDER OF EVENTS

14

quality of a sketch, that is to find a “loss function”. Since the ℓ1 norm naturally appears in
the estimates, we record in the experiments the difference between Φ (σ) and Φ̂w (σ), i.e.
(5.1)

M
1 Õ
errorm , where errorm :=
Error M :=
M m=1

Í

|w|=m

Φw (σ) − Φ̂w (σ)

kΦ (σ)k 1,(M)

denotes the relative error on the level of the m-th ordered moments. Recall that the sketch
always overestimates, Φ̂w (σ) ≥ Φw (σ), hence Φ̂ (σ) 1,(M) ≥ kΦ (σ)k 1,(M) .
L
5.1. Experiment 1. Stream sketch. We apply Theorem 10 to a fixed stream σ = (σi )i=1
consisting of L = 106 events that are drawn from an alphabet with | A| = 100 letters. This
is a toy example in the sense that | A| = 100 is not sufficient for many real-world examples.
However, we find it instructive since it allows to calculate and store the ground truth,
i.e. Φ (σ) (6 hours on a multicore machine for words up to length 3) to compare it with
the quality of the sketch. Table 1 and summarizes the performance of the sketch from
Theorem 10.

|B| Nr. of hashes Events/second
4
2
64368
4
4
33529.3
4
8
17651.8
4
16
9120.63
4
32
4620.79
8
2
13231.9
8
4
6688.18
8
8
3411.47
8
16
1712.27
8
32
850.85
16
2
1567.09
16
4
781.82
16
8
390.48
16
16
194.98
16
32
97.213
32
2
775.96
32
4
388.06
32
8
195.25
32
16
97.93
32
32
49.21
5

memory for Φ(σ)
memory for Φ̂(σ)

6012.50
3006.25
1503.13
751.56
375.78
864.81
432.41
216.20
108
54.05
115.63
57.81
28.91
14.45
7.23
1.87
7.47
3.73
1.87
0.99

Error3
3923.47
3048.61
2927.01
2086.38
2061.50
484.71
364.40
293.34
268.00
230.30
57.52
42.94
38.66
33.14
26.29
8.15
6.59
5.01
4.41
3.60

10
Table 1. The stream σ = (1, ai )i=1
with ai ∈ A, | A| = 100. There are 10
letters that make about 10 percent of the events, the rest of the events
is uniformly distributed among the remaining 90 letters. Calculating the
ground-truth (Φw (σ))|w|≤3 took 6 hours on a modern multicore computer
(Intel Xeon, CPU E5-2690 v4, 2.60GHz, 56 CPUs with 2 threads per
core). Without sketching, one needs to update for every of the 105 events
102 + 104 + 106 real numbers.

SKETCHING THE ORDER OF EVENTS

15

5.2. Experiment 2: classifying Markov chains. We sampled two types of random
streams of constant counter increase λi ≡ 1 from an alphabet consisting of| A| = 105 letters.
Each stream contains L = 105 events and two heavy hitters which we denote below wlog
as {1, 2}. The first type of stream was sampled as follows: in the first 2500 events we
choose at each step with probability p the letter 1 and with probability 1 − p uniformly
from A\ {1, 2}; in the following 2500 events we do the same with 2 instead of ; in the last
5000 events we choose with probability p uniformly from {1, 2} and with 1 − p uniformly
form A\ {1, 2}. The second type of streams was constructed analogous but the heavy
hitters were run in reverse order (i.e. 2 as heavy hitter in first 2500 events occurring with
probability p, followed by 1 as heavy hitter in next 2500 events occurring with probability
q, uniformly from both in the last 5000 events). Note that these are Markov chains (adding
time as state space to account for the change of regime). It is trivial for standard sketches
to identify the heavy hitters {1, 2}, but as p approaches q, it becomes harder to distinguish
the streams. On the other hand, taking order information into account allows for perfect
classification, see Table 2 below.
q−p
q
Mean accuracy M = 1 Mean accuracy M = 2
0.001 0.101
0.57
1.0
0.005 0.105
0.63
1.0
0.01 0.11
0.785
1.0
0.02 0.12
0.89
1.0
0.03 0.13
0.975
1.0
Table 2. For p = 0.1 and each of above values for q we sampled 500
streams for each type. We then ran heavy hitter pattern sketch (using
20 hash functions to an alphabet of 10letters) for each stream and computed the corresponding features (i.e. Φ̂w (σ) : w ∈ {1, 2, 11, 12, 21, 22}

for M = 2 resp. Φ̂w (σ) : w ∈ {1, 2} for M = 1) and trained a logistic regression classifier (ℓ1 penalty via 5-fold cross-validation over the training
set, training-test splitted as 0.8 to 0.2). Above shows the mean accuracy on
the testing set. As |p − q| becomes small, M = 1 approaches the uninformed
baseline of guessing the type (0.5 mean accuracy is achieved by choosing
uniformly at random the type of the stream). In contrast, M = 2 uses second
order information which allows for perfect classification. Calculating the
heavy hitter sketch took approximately 0.15 seconds per stream.
Acknowledgement 28. This work was supported by ERC advanced grant ESig (no. 291244).

SKETCHING THE ORDER OF EVENTS

16

References
[1] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency
moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages
20–29. ACM, 1996.
[2] Pierre Cartier. A primer of hopf algebras. In Frontiers in number theory, physics, and geometry II,
pages 537–615. Springer, 2007.
[3] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams.
In International Colloquium on Automata, Languages, and Programming, pages 693–703. Springer,
2002.
[4] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams.
Theoretical Computer Science, 312(1):3–15, 2004.
[5] Kuo-Tsai Chen. Integration of paths—a faithful representation of paths by non-commutative formal
power series. Trans. Amer. Math. Soc., 89:395–407, 1958.
[6] Graham Cormode and S Muthukrishnan. An improved data stream summary: the count-min sketch
and its applications. Journal of Algorithms, 55(1):58–75, 2005.
[7] Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over
sliding windows. SIAM journal on computing, 31(6):1794–1813, 2002.
[8] N. Duffield, Y. Xu, L. Xia, N. Ahmed, and M. Yu. Stream Aggregation Through Order Sampling.
ArXiv e-prints, March 2017.
[9] Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applications.
Journal of computer and system sciences, 31(2):182–209, 1985.
[10] Jaroslav Fowkes and Charles Sutton. A subsequence interleaving model for sequential pattern mining.
arXiv preprint arXiv:1602.05012, 2016.
[11] Peter K Friz and Martin Hairer. A course on rough paths: with an introduction to regularity structures.
Springer, 2014.
[12] Ben Graham. Sparse arrays of signatures for online character recognition. preprint.
[13] Ben Hambly and Terry Lyons. Uniqueness for the signature of a path of bounded variation and the
reduced path group. Ann. of Math. (2), 171(1):109–167, 2010.
[14] Jiawei Han, Jian Pei, Behzad Mortazavi-Asl, Qiming Chen, Umeshwar Dayal, and Mei-Chun Hsu.
Freespan: frequent pattern-projected sequential pattern mining. In Proceedings of the sixth ACM
SIGKDD international conference on Knowledge discovery and data mining, pages 355–359. ACM,
2000.
[15] Piotr Indyk, Nick Koudas, and S Muthukrishnan. Identifying representative trends in massive time
series data sets using sketches. In VLDB, pages 363–372, 2000.
[16] F. J Király and H. Oberhauser. Kernels for sequentially ordered data. ArXiv e-prints, 1601.08169.
[17] A. Kormilitzin, K. E. A. Saunders, P. J. Harrison, J. R. Geddes, and T. Lyons. Detecting early signs
of depressive and manic episodes in patients with bipolar disorder using the signature-based model.
ArXiv e-prints, August 2017.
[18] Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive datasets. Cambridge
university press, 2014.
[19] Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins. Text classification using string kernels. The Journal of Machine Learning Research, 2:419–444, 2002.
[20] M_ Lothaire. Combinatorics on words, volume 17. Cambridge University Press, 1997.
[21] Terry Lyons. Rough paths, signatures and the modelling of functions on streams. arXiv preprint
arXiv:1405.4537, 2014.
[22] Terry J Lyons and Weijun Xu. Hyperbolic development and inversion of signature. Journal of Functional
Analysis, 272(7):2933–2955, 2017.
[23] Charles A Micchelli, Yuesheng Xu, and Haizhang Zhang. Universal kernels. Journal of Machine
Learning Research, 7(Dec):2651–2667, 2006.
[24] Shanmugavelayutham Muthukrishnan. Data streams: Algorithms and applications. Now Publishers
Inc, 2005.
[25] Anastasia Papavasiliou and Christophe Ladroue. Parameter estimation for rough differential equations.
The Annals of Statistics, 39(4):2047–2073, 2011.
[26] Mert Pilanci and Martin J Wainwright. Randomized sketches of convex programs with sharp guarantees.
IEEE Transactions on Information Theory, 61(9):5096–5115, 2015.

SKETCHING THE ORDER OF EVENTS

17

[27] Christophe Reutenauer. Free Lie algebras. The Clarendon Press Oxford University Press, New York,
1993. Oxford Science Publications.
[28] Gian-Carlo Rota. Hopf algebra methods in combinatorics. In Problèmes combinatoires et théorie des
graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 of Colloq. Internat. CNRS,
pages 363–365. CNRS, Paris, 1978.
[29] Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alexander J. Smola, Alexander L. Strehl,
and S. V. N. Vishwanathan. Hash kernels. In AISTATS, 2009.
[30] Moss E. Sweedler. Hopf algebras. Mathematics Lecture Note Series. W. A. Benjamin, Inc., New York,
1969.
[31] Weixin Yang, Terry Lyons, Hao Ni, Cordelia Schmid, Lianwen Jin, and Jiawei Chang. Leveraging the
path signature for skeleton-based human action recognition. arXiv preprint arXiv:1707.03993, 2017.
[32] Yun Yang, Mert Pilanci, and Martin J Wainwright. Randomized sketches for kernels: Fast and optimal
non-parametric regression. arXiv preprint arXiv:1501.06195, 2015.
[33] Mohammed J Zaki. Spade: An efficient algorithm for mining frequent sequences. Machine learning,
42(1):31–60, 2001.

SKETCHING THE ORDER OF EVENTS

18

Appendix A. A topology on streams and universality
We want to regard streams that have similar length and similar events as close to each
other. It is therefore natural to view them as paths in the vector space spanned by letters
in A. To make this precise, we use the Donsker embedding


ι : S ֒→ C [0, 1], R| A|



by identifying σ as a continuous path γσ ∈ C [0, 1], R| A| by using a1, . . ., a | A| as a
orthonormal basis of R| A| and setting

(A.1)

γσ (t) := (t L − ⌊t L⌋) λ ⌈t L⌉ a ⌈t L⌉ +

⌊t L⌋
Õ

λi ai for j = 1, . . ., L.

i=1

In words: the path γσ is a lattice path starts at t = 0 at the origin in R| A| and upon receiving
an event (λ, a) goes with constant speed in direction a for a time proportional to λ. Denote
with
(
)
M−1




Õ
sup
C 1−var [0, 1], R| A| = γ ∈ C [0, 1], R| A| : kγk 1 =
|γ (ti+1 ) − γ (ti )| < ∞
0≤t1 <···<t M ≤1 i=1

the set of bounded variation paths.



Definition 29. Denote with ι : S → C 1−var [0, 1], R| A| the Donsker embedding. We

−1
equip S with the pullback
topology
 of ι, that is the open sets in S are ι (U) where U is

an open set in C 1−var [0, 1], R| A| .

Proposition 30. Let the event map p : E → F and resulting feature map Φ : S → F be as
in Theorem 32. For every f ∈ C (S, R) ǫ > 0, and compact set K ⊂ S there exists a ℓ ∈ F ′
such that
sup | f (σ) − hℓ, Φ (σ)i| < ǫ .
σ∈K

Proof. By Stone–Weierstrass we need to verify that {σ 7→ hℓ, Φ (σ)i, ℓ ∈ F ′ } is a pointseparating subalgebra of C (S, R). The subalgebra property follows since
hℓ, Φ (σ)i hℓ′, Φ (σ)i = hm (ℓ ⊗ ℓ′), Φ (σ)i
where m denotes the shuffle (resp. infiltration product) on F ′ as detailed in Appendix
B. The fact that σ 7→ Φ (σ) is point-separating follows in the case of the event map
p (λ, a) = exp λa from classic results (injectivity of the signature for non-treelike paths);
K
L
and L < K then
and τ = (τi )i=1
in the case p (λ, a) = 1 + λa note that if σ = (σi )i=1
Φw (σ) = 0 , Φw (τ) > 0 since Φw (τ) is a sum over disjoint time indices. If L = K,
and σi = (λi, ai ), τi = (ρi, bi ) and there exists a i such that ai , bi then the result follows
immediately by comparing at the coordinate w = a1 · · · a L . Finally, if L = K and ai = bi
for all i, we can argue as in [22].

Appendix B. Some (Hopf) algebras
We describe the interplay between feature and dual space using Hopf algebras. This
is a concise way to capture the interplay between F and its dual space; a reader less
familiar with algebra might want to skip this appendix after a brief look at Theorem 32
and Theorem 35.

SKETCHING THE ORDER OF EVENTS

19

B.1. Hopf algebras. Hopf algebras arise naturally when a linear space H as well
 as
⋆
⋆
⋆
⋆
its dual H are equipped with products m and m such that (H, m) and H , m are
algebras and m,m⋆ are “compatible”. This is of interest to us, since the feature space F
has the concatenation product (“a new event happens”) and we will that its dual F ′ can
be equipped with commutative product. This elegantly describes the interplay between
dual and feature space and allows us to address Points (2), (3) (universality of features and
structure preserving) from Section 1.3

Example 31. Consider a finite dimensional, linear space H and let (H, m) and H ⋆, m⋆
be algebras. The product m can be written as a linear map
m :H ⊗H →H
that fulfills associativity and distributivity. By duality, m can be encoded as a linear map
∆m on the dual H ⋆
∆m : H ⋆ → H ⋆ ⊗ H ⋆
by ∆⋆ (ℓ), g ⊗ h := hℓ, m (g ⊗ h)i for f , g ∈ H, ℓ ∈ H ⋆.

⋆, m⋆ , we can work with one
Thus instead of working
with
two
algebras
m)
and
H
(H,

space H ⋆, m⋆, ∆m and two linear maps,
(B.1)

m⋆ : H ⋆ ⊗ H ⋆ → H ⋆
∆m :
H⋆
→ H⋆ ⊗ H⋆

[or vice versa with (H, m, ∆m⋆ ), ∆m⋆ defined analogous to (B.1)]. A natural way to ensure
“compatibility” of the two algebras is to require that ∆m is an algebra morphism,

m⋆ (∆m (h) ⊗ ∆m (g)) = ∆ m⋆ (h ⊗ g) for g, h ∈ H ⋆ .

Further, an algebra also has unit ǫ which can be represented as linear map ǫ : R → H .
Again by duality this unit ǫ translates to a linear map H ⋆ → R called counit. More general,
a not necessarily finite dimensional vector space H equipped with two linear maps, called
product and coproduct,
m : H ⊗ H → H and ∆ : H → H ⊗ H
that fulfill natural generalizations of above properties is called a bialgebra. If additionally
(as in our application) the space H is connected and graded, it is a non-trivial result that
there must exist a so-called antipode3
S:H →H
and we call (H, m, ∆, S) a Hopf algebra (we refer to the monographs [2, 30, 28] for details).
This antipode has an intuitive interpretation: it is simply the inverse map of a group
structure inside the linear space H , that is if we denote with
G (H ) = {h ∈ H : ǫ (h) = 1, ∆ (h) = h ⊗ h}
the set of group-like elements, then (G (H ), m) is a group with inverse given by S (g) = g −1 .
In many situations, the elements of H have a combinatorial interpretation in which case
one may think of m and ∆ as composition and decomposition. Elements that are “simple
under decomposition” with ∆, are exactly G (H ). We use below that linear functionals of
3 Takeuchi’s formula reads S =

Í

k ≥0 (−1)

k

m(k−1) (id − ηǫ) ⊗k ∆(k−1) where η,ǫ are unit and counit of H .

SKETCHING THE ORDER OF EVENTS

20

group-like elements are closed under multiplication, that is if h ∈ G (H ) ⊂ H is group-like,
then
hℓ, hi hℓ′, hi = hℓ ⊗ ℓ′, h ⊗ hi = hℓ ⊗ ℓ′, ∆ (h)i = m⋆ (ℓ ⊗ ℓ′), h for ℓ, ℓ′ ∈ H ⋆ .
B.2. Feature and dual space for streams. By construction of Φ (σ), the obvious choice
for multiplication in F — no matter what event map p : E → F is used — is the noncommutative multiplication. That is we define the so-called concatenation product mc
mc : F ⊗ F → F , mc (a1 · · · a M ⊗ a M+1 · · · a M+N ) := a1 · · · a M+N for a1, . . ., am+n ∈ ℓ
extended by linearity to F . This turns (F , mc ) into a non-commutative algebra. To learn
about σ, we apply linear functionals ℓ ∈ F ′ to Φ p (σ) ∈ F . To find a product mp that turns
the dual F ′ into an algebra, it is useful to recall that our features should be group-like.
Hence, this product
mp : F ′ ⊗ F ′ → F ′
depends highly on the choice of event map p. The existence of this product is a priori not
clear; a non-trivial results is that for both choices
p (λ, a) = 1 + λa and p (λ, a) = exp (λa)

′
such a product m p exists. This turns F , m p into a commutative algebra.
The final step

is to capture this structure of two two algebras (F , mc ) and F ′, m p by using one Hopf
algebra.
Theorem 32. Define the event map p : E → F as either
(λ, a) 7→ exp (λa) or (λ, a) 7→ 1 + λa,
and define a feature map Φ : S → F as
Φ (σ) =

L
Ö

p (σi ) for streams σ = (σi ) of events σi = (λi, ai ) .

i=1

Then
(1) The features Φ (σ) ∈ F are ordered moments, that is


(B.2)
Φ (σ) = E λi1 · · · λim ai1 · · · aim ,

with expectation taken over the order statistics of (i1, . . ., im ) sampled uniformly
without replacement from {1, . . ., L} in the case p (λ, a) = 1 + λa; in the case
p (λ, a) = exp (λa) the expectation is taken over the order statistic of (i1, . . ., i L )
sampled uniformly with replacement from {1, . . ., L}.
(2) The coordinates hΦ (σ), wi are given as
(Í
λ(i)
if p (λ, a) = exp (λa),
(1) i!
hΦ (σ), wi = Í
if p (λ, a) = 1 + λa.
(2) λ (i)
Í
where the sum (1) is taken overÍall i = (i1, . . ., i L ) ∈ N L such that i1 ≤ · · · ≤ i L
and ai1 · · · aiL = w; for the sum (2) we additionally assume i1 < · · · < i L . We
denote λ (i) = λi1 · · · λiM ∈ R and i! is recursively defined as i! = i1 ! if L = 1 and
(i1, . . ., i L, i L+1)! = (i1, . . ., i L )!k! where k = max j≥0:iL+1−j =iL+1 j.

(3) There exists a linear map mp : F ′ ⊗ F ′ → F ′ such that F ′, m p, ∆C is a commutative Hopf algebra.

SKETCHING THE ORDER OF EVENTS

21

Proof. Points (1) and (2) follow by direct calculations. For p (λ, a) = exp (λa, ), Point (3)
is a standard result in algebra and the resulting Hopf algebra is known as the shuffle Hopf
algebra, see e.g. [27]. The case p (λ, a) = 1 + λa seem to be much less known. The key is
to define the commutative product on F ′ recursively as
mI (av ⊗ bw) = a inf (v ⊗ bw) + b inf (av ⊗ b) + avw1a=b
Note the additional third term, which is 0 in the shuffle Hopf algebra case. Then one
can directly verify the properties of a Hopf algebra in a (lengthy) direct calculation. This
commutative product is known as the infiltration product, see [20].

Remark 33.
(1) Above theorem is classic for p (λ, a) = exp (λa), the product mp on F ′ is the “shuffle
product”. If p (λ, a) = 1 + λa, the product is the less standard “infiltration product”.
(2) In the special case of constant counterincrease, λi ≡ 1, the coordinates count how
often a substring w appears in σ and the choice of the event map p determines if
an event can be counted several times. The choice p (λ, a) = 1 + λa recovers the
string kernel features from [19, 16]. The Hopf algebra structure for string kernels
features seems to be new.
(3) If we replace the non-commutative product mc in F with a commutative product,
the features reduce to usual (unordered) sample moments as seen by (B.2).
(4) The event map (λ, a) 7→ 1 + λa and associated Hopf algebra generalizes classic
string kernel features. While the coordinates are more intuitive, the resulting
feature map is much less robust under scaling than (λ, a) 7→ exp (λa), see the
section below.
(5) We stick to the machine learning terminology and call F feature space and F ′
dual space. From an algebraic perspective it is the other way around: F = RhhAii
is the algebraic dual of F ′ = RhAi.

(6) A technical point: F ′, m p, ∆C is a Hopf algebra, so we expect a Hopf algebra on
feature space F by duality. However, one needs to work with a slightly smaller
subset of F (called the Sweedler dual).
Example 34. As remarked in above proof, the commutative product on F ′ known recursively. For example
(
abba + 2abba + 2baab + baba
if p (λ, a) = exp (λa),
m p (ab ⊗ ba) =
aba + bab + abab + 2abba + 2baab + baba if p (λ, a) = 1 + λa.
L
as an element of
B.3. Scaling limits and estimates. One can identify σ = (λi, ai )i=1
L
A|
|
R
and apply standard features ϕ for vector-valued data. Most reasonable choice of ϕ
guarantee that
L
f (v) ≈ hℓ, ϕ (v)i for v ∈ R| A|
However, this approach becomes infeasible for large L and additionally methodological
problems arise if our data contains streams of different length. On the other hand, we will
see that
f (σ) ≈ hℓ, Φ (σ)i
and that above expression still makes sense in the scaling limit L → ∞.

Theorem 35. Let the event map p : E → F and resulting feature map Φ : S → F be as in
Theorem 32.

SKETCHING THE ORDER OF EVENTS

22





(1) Let (σ n )n≥1 ⊂ S be a sequence of streams such that γσ n converges in C 1−var [0, 1], R| A| , k·k 1
to a path γ = (γ a )a∈A. Then for every word w = a1 · · · a M ,
n

lim hΦ (σ ), wi =
n

ˆ

dγ a1 (t1 ) · · · dγ am (tm )

0≤t1 ≤···≤tm ≤1

and limn Φ (σ n )Íis a group-like element of the Hopf algebra F .
L
(2) Define kσk 1 = i=1
|λi |. Then kσk 1 = kγσ k 1 and
kΦ (σ)k 1,M ≤

kσk 1M
and kΦ (σ)k 1 ≤ exp (kσk 1 ) for σ ∈ S.
M!

with equality if p (λ, a) = exp (λ, a).
(3) Stream concatenation is multiplication in feature space,
Φ (σ, τ) = Φ (σ) · Φ (τ) for σ, τ ∈ S.
Proof. Point (1) follows by a direct calculation for both event maps. For
´ Point (2) note that
under the event map p (λ, a) = exp (λa) we have that ha1 · · · a M , Φ (σ)i = 0<t1 <···<tM <L dγσa1 (t1 ) · · · dγσa M (t M )
where γσ denotes the path (A.1). Then

ha1 · · · a M , Φ (σ)i =

ˆ

0<t1 <···<t M <L

1
=
M!

ˆ

[0,L]
M
Öˆ

1
=
M! m=1

M

dγσa1 (t1 ) · · · dγσa M (t M )

dγσa1 (t1 ) · · · dγσa M (t M )
1 Ö
fa .
M! m=1 m
M

dγσam (t) =

[0,L]

where denoted with fa the frequency of letter a in σ, i.e. fa =
Õ
Õ
© Õ
ª
fa
fa1 · · · fa M =
hw, Φ (σ)i ® =
­
a∈A
a
,...,a
∈A
w:|w|=M
«
¬ 1 M

!M

Í

=

i:ai =a λi .
L
Õ
i=1

λi

Hence,

!M

= kσk M .

For the event map p (λ, a) = 1 + λa, Theorem 32 shows that the feature coordinates are
smaller equal than then ones for the event map p (λ, a) = exp (λ, a). Hence, the result follows.
ÎL
Point (3) follows directly from our construction of features as Φ (σ) = i=1
p (λi, ai ) for

σ = (λi, ai ).

SKETCHING THE ORDER OF EVENTS

23

Appendix C. Algorithms
Algorithm 1 (ǫ, δ, M)-sketch.
Initialize:
Set h ← −⌈log δ⌉ and d ← ⌈ 1ǫ ⌉
Sample H1, . . ., Hh hash functions from a 2-universal hash family
For each Hi initialize d + d 2 + · · · + d M counters to store Φi = Φ(Hi (σ))
Process:
Fetch event (λ, a) in stream
while (λ, a) ,  do
for i = 1, . . ., h do
Φi ← Φi ∗ p(λ, Hi (a))
end for
Fetch next event (λ, a)
end while

⊲  denotes the last element/end of the stream
⊲ power series multiplication

Output: On query w, return mini∈{1,...,h} hΦi, Hi (w)i
Algorithm 2 Heavy hitter patterns
Initialize:
Prepare (ǫ, δ) sketch structure Φ̂ as in Algorithm 1
Ĥ ← {1}

⊲ 1 denotes the empty word

Process:
Fetch event (λ, a) in stream
while (λ, a) ,  do
⊲  denotes the last element/end of the stream
for i = 1, . . ., h do
Φi ← Φi ∗ p(λ, Hi (a))
⊲ power series multiplication
end for
if mini∈{1,...,h} hΦi, Hi (a)i > ρ then
Ĥ ← Ĥ ∪ {a}
end if
Fetch next event (λ, a)
end while
for w ∈ Ĥ ⋆ do
if mini∈{1,...,h} hΦi, Hi (w)i ≥ ρ M then
ĤM ← ĤM ∪ {w}
end if
end for
Output: Return ĤM
E-mail address: tlyons@maths.ox.ac.uk
E-mail address: oberhauser@maths.ox.ac.uk
Mathematical Institute, University of Oxford

