Published in Volume XXVIII, Issue 2, 2018, pages 161-198, doi: 10.7561/SACS.2018.2.161

Authors: C. Bertrand, F. Peschanski, H. Klaudel, M. Latapy

Abstract

Link streams model the dynamics of interactions in complex distributed systems as sequences of links (interactions) occurring at a given time. Detecting patterns in such sequences is crucial for many applications but it raises several challenges. In particular, there is no generic approach for the speci fication and detection of link stream patterns in a way similar to regular expressions and automata for text patterns. To address this, we propose a novel automata framework integrating both timed constraints and finite memory together with a recognition algorithm. The algorithm uses structures similar to tokens in high-level Petri nets and includes non-determinism and concurrency. We illustrate the use of our framework in real-world cases and evaluate its practical performances.

Full Text (PDF)

References

[1] J. Agrawal, Y. Diao, D. Gyllstrom, and N. Immerman. Efficient Pattern Matching Over Event Streams. In J. T. Wang, editor, Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada, June 10-12, 2008, pages 147-160. ACM, 2008. doi:10.1145/1376616.1376634.

[2] R. Alur and D. L. Dill. A Theory of Timed Automata. Theoretical Computer Science, 126(2):183-235, 1994. doi:10.1016/0304-3975(94)90010-8.

[3] E. Asarin, P. Caspi, and O. Maler. Timed Regular Expressions. J. ACM, 49(2):172-206, 2002. doi:10.1145/506147.506151.

[4] J. Bengtsson and W. Yi. Timed Automata: Semantics, Algorithms and Tools, volume 3098 of Lecture Notes in Computer Science, pages 87-124. Springer, 2003. doi:10.1007/978-3-540-27755-2_3.

[5] C. Bertrand, H. Klaudel, M. Latapy, and F. Peschanski. Pattern Matching in Link Streams: A Token-Based Approach. In PETRI NETS 2018, volume 10877 of Lecture Notes in Computer Science, pages 227-247. doi:10.1007/978-3-319-91268-4_12.

[6] C. Câmpeanu, K. Salomaa, and S. Yu. A Formal Study of Practical Regular Expressions. Int. J. Found. Comput. Sci., 14(6):1007-1018, 2003. doi:10.1142/s012905410300214x.

[7] B. Carle and P. Narendran. On Extended Regular Expressions. In A. Dediu, A. Ionescu, and C. Martín-Vide, editors, Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings, volume 5457 of Lecture Notes in Computer Science, pages 279-289. Springer, 2009. doi:10.1007/978-3-642-00982-2_24.

[8] A. Deharbe and F. Peschanski. The Omniscient Garbage Collector: A Resource Analysis Framework. In ACSD 2014. IEEE Computer Society, 2014. doi:10.1109/acsd.2014.18.

[9] A. Deharbe and F. Peschanski. The Omniscient Garbage Collector: a Resource Analysis Framework. Research report, LIP6 UPMC Sorbonne Universités, France, 2014.

[10] D. L. Dill. Timing Assumptions and Verifi cation of Finite-State Concurrent Systems. In J. Sifakis, editor, Automatic Veri fication Methods for Finite State Systems. CAV 1989, volume 407 of Lecture Notes in Computer Science, pages 197-212. Springer. doi:10.1007/3-540-52148-8_17.

[11] R. Fontugne, P. Borgnat, P. Abry, and K. Fukuda. Mawilab: Combining Diverse Anomaly Detectors for Automated Anomaly Labeling and Performance Benchmarking. In CoNEXT 2010, page 8. ACM. doi: 10.1145/1921168.1921179.

[12] V. K. Garg and M. T. Ragunath. Concurrent Regular Expressions and Their Relationship to Petri Nets. Theoretical Computer Science, 96(2):285-304, 1992. doi:10.1016/0304-3975(92)90339-h.

[13] M. Kaminski and N. Francez. Finite-Memory Automata. Theoretical Computer Science, 134(2):329-363, Nov. 1994. doi:10.1016/0304-3975(94)90242-9.

[14] M. Latapy, T. Viard, and C. Magnien. Stream Graphs and Link Streams for the Modeling of Interactions Over Time. CoRR, abs/1710.04073, 2017.

[15] A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in Temporal Networks. volume abs/1612.09259, 2016.

[16] N. Tzevelekos. Fresh-Register Automata. In T. Ball and M. Sagiv, editors, Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 295-306. ACM, 2011. doi:10.1145/1925844.1926420.

[17] D. Ulus, T. Ferrère, E. Asarin, and O. Maler. Timed Pattern Matching. In FORMATS 2014, volume 8711 of Lecture Notes in Computer Science, pages 222-236. doi:10.1007/978-3-319-10512-3_16.

[18] D. Ulus, T. Ferrère, E. Asarin, and O. Maler. Online Timed Pattern Matching Using Derivatives. In Tools and Algorithms for the Construction and Analysis of Systems, volume 9636 of Lecture Notes in Computer Science, pages 736-751, 2016. doi:10.1007/978-3-662-49674-9_47.

[19] T. Viard, R. Fournier, C. Magnien, and M. Latapy. Discovering Patterns of Interest in IP Traffic Using Cliques in Bipartite Link Streams. In (CompleNet’18) International Conference on Complex Networks, pages 233-241, Mar. 2018. doi:10.1007/978-3-319-73198-8_20.

[20] T. Viard, R. Fournier-S’niehotta, C. Magnien, and M. Latapy. Discovering Patterns of Interest in IP Traffic Using Cliques in Bipartite Link Streams. CoRR, abs/1710.07107, 2017.

[21] M. Waga, T. Akazaki, and I. Hasuo. A Boyer-Moore Type Algorithm for Timed Pattern Matching. In 14th International Conference, FORMATS 2016, volume 9884 of Lecture Notes in Computer Science, pages 121-139. doi:10.1007/978-3-319-44878-7_8.

[22] M. Waga, I. Hasuo, and K. Suenaga. Efficient Online Timed Pattern Matching by Automata-Based Skipping. In 15th International Conference, FORMATS 2017, volume 10419 of Lecture Notes in Computer Science, pages 224-243. doi:10.1007/978-3-319-65765-3_13.

[23] H. Zhang, Y. Diao, and N. Immerman. On Complexity and Optimization of Expensive Queries in Complex Event Processing. In SIGMOD 2014, pages 217-228. ACM. doi:10.1145/2588555.2593671.

Bibtex

@article{sacscuza:bertrand2018pmilstwfm,
  title={Pattern Matching in Link Streams: Timed-Automata with Finite Memory},
  author={C. Bertrand, F. Peschanski, H. Klaudel, M. Latapy},
  journal={Scientific Annals of Computer Science},
  volume={28},
  number={2},
  organization={``A.I. Cuza'' University, Ia\c si, Rom\^ania},
  year={2018},
  pages={161--198},
  publisher={``A.I. Cuza'' University Press, Ia\c si}
}