flink-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Till Rohrmann <trohrm...@apache.org>
Subject Re: Cep NFA formal declaration
Date Thu, 07 Jul 2016 11:41:22 GMT
Hi Bence,

Flink's CEP implementation is mainly based on this paper [1]. It mainly
describes how the shared buffer is used to store efficiently the internal
state of the NFA.

The translation of the Pattern API into the NFA happens in the
NFACompiler.compileFactory method. For every pattern entry, we create a NFA
state and insert transition between these states with the corresponding
constraints. In case of a followedBy relation, we additionally add a
reflexive transition where we ignore the current input symbol.

I hope this helps you a bit to better understand the implementation.

[1] https://people.cs.umass.edu/~yanlei/publications/sase-sigmod08.pdf

Cheers,
Till

On Thu, Jul 7, 2016 at 1:00 PM, Bence Ágocsi Kiss <akbence007@gmail.com>
wrote:

> Hi,
>
> I'm trying to use the CEP library, and for that, i've read the tutorial on
> the site and I tried the given examples. However, I would need a more
> accurate description to understand the behavior. I haven't found any formal
> description, about how the NFA works, and how they are built from the
> pattern language. I would really appreciate that, if somebody could give an
> paper or some formal explanation of its mechanism
>
> Thanks and regards
> Bence Agocsi-Kiss
>

Mime
View raw message