Jump label

Service navigation

Main navigation

You are here:

Main content

Complex Event Detection at Wire Speed with FPGAs — VLDB 2010 Reviews

Author feedback for paper Complex Event Detection at Wire Speed with FPGAs, submitted to VLDB 2010.

We would like to thank the reviewers for their comments and insights. We believe that all their concerns can be easily addressed:

(1) Time-outs (Reviewer_3, W1; Reviewer_4, W3)
Time-outs are essential to limit the necessary amount of state. This is no different in conventional complex event detection (when looking for A followed by B, how long do we keep A?) as otherwise any event that is a prefix of match would have to be kept in memory indefinitely. In our design the time-out is a parameter. Both the update rate of the time-out (the number of clock ticks) and the actual value of the time-out (the space reserved for the counter) can be adjusted. The one-second example and the four bits used in the text are just sample values.

(2) Swapping Algorithm (Reviewer_3, W3)
Indeed, there is a typo in Figure 7 (we noticed after submission), although the description in the text is correct. An additional check on line four in the first part of the algorithm is missing:

  if pe_i.partitionidentifier = x 
     or (pe_i = free and pe_{i+1}.partitionidentifier != x) then 

S is the input data stream, from which we only inspect partition identifiers here (remaining tuple parts are considered inside the state automaton). We will correct the typo in the final version.

(3) Latency (Reviewer_3, W2)
It is true that a longer pipeline increases latency. However, the latency is still very low. A tuple progresses from one pipeline element to the next every 16ns (half the outside clock frequency of 125MHz). Therefore, with an 800 element-deep pipeline the latency is 800x16ns = 12.8 micro-seconds. This is why we are not concerned with the latency as it is irrelevant when compared with the arrival rate of standard streams.

(4) Relation to other work (Reviewer_4, W1)
The two main differences between earlier work (mostly on network intrusion detection, such as [16]) and ours are:

  1. Earlier work used FPGAs for pattern matching on strings, i.e., they evaluate character-based regular expressions. In our work, we detect complex event patterns in sequences of events and events are based on arbitrary predicates.
  2. We are interested in event patterns that span multiple (potentially far-apart) packets, while existing techniques exclusively consider the inspection of single packets.

Both differences are due to the nature of stream processing and add significant complexity to the problem. They amplify the state explosion problem (cf. Section 4.2); necessitate partitioning functionality (and thus our pipelining strategy); and introduce the need for, e.g., time-outs (as discussed above). We add this explanation to the final version of the paper.

(5) (Reviewer_1, Detailed Comments)
We would welcome the chance to explain the differences between FPGAs and conventional programming in more detail as we believe they are really crucial when dealing with highly parallel hardware. However, in our earlier papers (VLDB'09), (ICDE'10) we got very mixed feedback on such material (some reviewers asked us to remove it as being off-topic for a database venue, others were enthusiastic about it). It is no problem at all to add one page in the appendix where we clarify FPGA specifics and the differences to conventional programming. We will also add some clarifications regarding related work (such as Netezza, which we know well, but it is only remotely related to what we present in this paper beyond the fact that they also use FPGAs for data processing).

Related Information

Sub content


Prof. Dr. Jens Teubner
Tel.: 0231 755-6481