By Emanuele Della Valle https://orcid.org/0000-0002-5176-5885

Review Details

---

Reviewer has chosen not to be Anonymous

Summary of paper in a few sentences:

The paper focuses on sequential pattern mining. The authors claim that finding subsequences in sequences is helpful for many applications, such as those cited by the author: weather forecasting and mobility. To address this issue, the authors propose an algorithm called Minits-AllOcc to find sequential patterns and transition times between events. They also introduce a parallel version of the algorithm called MMinits-AllOcc, which runs on a multi-core CPU. The authors bring experimental evidence that Minits-AllOcc outperforms brute-force methods and that MMinits-AllOcc is 2.5X faster than the single-core version.

Reasons to accept:

The paper is very well written. It is well organized, and it reads smoothly. The motivation of the paper is strong. The proposed method is sound. The experimental campaign is extensive and proves the claims of the authors.

Reasons to reject:

I have severe doubts about the novelty of the paper. I am not an expert in sequential pattern mining; thus, I read the reviews referenced in the paper (citations 9 and 10). I discovered that state-of-the-art algorithms ignore the temporal information between itemsets in a sequential pattern.

As my stream processing area of expertise, temporal information is essential for many situations, and engines are optimized for it. While basic stream processing queries can use the order of events coming on a stream (e.g., A followed by B or A followed by B and not C), expressive queries require at least one temporal annotation per event. Temporal annotations allow computing intervals and reason on time (e.g., A followed by B within N seconds).

Indeed, in stream processing, finite state machines (FSMs) and trees are used to improve the efficiency and accuracy of processing systems by reducing the need for brute-force pattern matching. FSMs and Trees represent the states and the transitions in modeling sequences, time intervals, and causality and recognizing complex event patterns [*]. Moreover, as in the authors' setting, stream processing cannot re-scan the data because the input is an unbounded data structure that the engine cannot memorize. Last but not least, in both settings, latency matters. In stream processing, patterns of events must be detected in real-time since actions must be triggered based on those patterns. In the authors' settings, the real-time requirement does not hold, but it is clear that the faster, the better requirement holds.

[*] Artikis, A., Margara, A., Ugarte, M., Vansummeren, S. and Weidlich, M., 2017. Tutorial: Complex event recognition languages. In Proceedings of the 11th ACM International Conference on Distributed and Event-based Systems (pp. 7-10). ACM. https://cer.iit.demokritos.gr/publications/papers/2017/2017_debs_tut_pap...

Nanopublication comments:

Further comments:

* The quality of the tables is low: the font is too tiny, and pixelled.
* References 22, 23, 28, 29, and 32 are written in different fonts.
* The first paragraph in each section should be either indented or not indented. Currently, there is a mix.
* Figure 18 and figure 19 have different resolutions.
* I would avoid short sections (e.g., 4.5.*, and 5.* )

By Tobias Kuhn https://orcid.org/0000-0002-1267-0234

Review Details

---

Reviewer has chosen not to be Anonymous

Summary of paper in a few sentences:

The paper motivates and introduces the concept of timed sequential patterns. It then reports on the development of two algorithms and implementations, a plain one and one optimized for multi-core processing. Finally, it presents evaluation results in term of execution time and effect of different parameters.

Reasons to accept:

- Interesting and relevant topic
- Overall model and approach seem sound and valuable
- Good comparison of two versions of the algorithm/implementation

Reasons to reject:

- The novelty could be better established
- The formal definitions and arguments are quite hard to follow (at least to me) due to sometimes unconventional (at least to me) notation and omissions
- No "sanity check" with other existing implementations of plain (non-timed) sequences, to see whether outputs are consistent and execution times are reasonable

Nanopublication comments:

Further comments:

- The table in Figure 1 could be presented better: unclear why elements are shown in this order; use of color could make it easier to understand; as an introductory illustration, this could possibly also be made more into an actual figure and less like a strict table

- In the introduction about patterns being "extended": It wasn't clear to me why "extending" a pattern isn't treated like creating a new pattern (so then obviously the result has to be calculated again). Are such "extension" just things that happen frequently and therefore need specific support? Or did I misunderstand what these "extensions" are? This should clarified either way.

- In the end of the introduction: "The time can be any descriptive statistic based on the user's preference, such as range, average, etc." could have been better introduced in the example and motivations before.

- "The idea of incorporating transition time ...": I'd use a word that's a bit stronger than "idea", e.g. "concept" or "model".

- It took me a bit to understand the first paragraph of Section 2. I was confused by the notation <{a1},{a2},...>, where {a1} etc seem to be sets with a single element. But I think they should just be sequences of sets, so where a1, a2, etc are sets? I believe that the curly brackets are in this case superfluous and confusing. Also, it's not explicitly specified in the text that a1 etc are itemsets.

- "A timed event is a pair e = (I, t), where I am an item set that ...": I suppose it should be "where I *is*"

- "ei.x subsetof I (1 ≤ i ≤ n)": here it's unclear what x and I stand for.

- Definition of "delta": what do p and j stand for here?

- {a, 10} seem to be a tuple (not a set). I might not be familiar with the conventions of this particular community, but to me using curly brackets normally indicate a set, and round brackets are more usual for tuples, so (a, 10). But again, there might be different conventions in this community.

- I cannot really judge the novelty, as I am not an expert in the field. Based on the Related Work section, it seems novel, but it would be good to see in a bit more detail (at some point in the paper, maybe based on examples) how the presented approach differs from some other recent approaches.

- "The drawback of these methods is ..." in Related Work: I was wondering what happens if these methods are used with an arbitrarily high ("infinite") time interval. Does it break or would it still work? If the latter, how does it then compare to your method?

- "A node can have multiple parent nodes": this confused me. Does it mean "multiple direct parents"? Then it's not a tree! Or "multiple indirect parents going up the tree hierarchy"? The latter is kind of obvious, and I would remove this part to avoid confusion.

- "<{a,2},<{a,b,19},{d,25}>" this seems mal-formed.

- I got lost following the algorithm/method somewhere around Figure 8. It wasn't clear to me here what example exactly we are seeing here. Where do all these numbers come from? Are the upper ones (<{a}> and <{b}>) just given as an example, and they then produce the bottom onces? Is TS3 in <{a}> the same as TS3 in <{b}>? If so, why are the trees different? If not, why are they called the same?

- "For air temperature ...": This paragraph (and some other parts) in Section 5 are not very pleasant to read. It would be better to put this into some kind of table or figure.

- "Competing Algorithms": I would have liked to see some rough comparison to other algorithms. For example, I suppose the timed sequences can be used to "simulate" plain sequences, so you could create some such cases, which would allow you to test whether our algorithms get you the same results as the established ones do for the plain sequences (as a kind of sanity check). Measuring the execution time in this scenario would also be an interesting thing to do. It's perfectly fine if your algorithm would be slower in this scenario, but it would be interesting to see how much slower (like doubled execution time or 100x execution time or ...?).