nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Pattern Matching in Link Streams: A Token-Based Approach

verfasst von : Clément Bertrand, Hanna Klaudel, Matthieu Latapy, Frédéric Peschanski

Erschienen in: Application and Theory of Petri Nets and Concurrency

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 specification 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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel An Efficient Characterization of Petri Net Solvable Binary Words

Nächstes Kapitel Modeling Operational Semantics with Interval Orders Represented by Sequences of Antichains

The notion of a location here corresponds to a state in classical automata theory. We rather use the term state in the sense of actual state or configuration (as in FMAs [10]), i.e., an element of the state-space: a location together with a memory content and clock values.

We reuse the token notion of high-level Petri nets because it is quite similar conceptually. The configuration roughly corresponds to the marking of a Petri net.

The MaTiNa tool repository is at: https://github.com/clementber/MaTiNA.

The data come from the Politoscope project by the CNRS Institut des Systémes Complexes Paris Ile-de-France (https://politoscope.org).

Agrawal, J., Diao, Y., Gyllstrom, D., Immerman, N.: Efficient pattern matching over event streams. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 147–160 (2008)

Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci. 126(2), 183–235 (1994)MathSciNetCrossRef

Asarin, E., Caspi, P., Maler, O.: Timed regular expressions. J. ACM 49(2), 172–206 (2002)MathSciNetCrossRef

Câmpeanu, C., Salomaa, K., Sheng, Y.: A formal study of practical regular expressions. Int. J. Found. Comput. Sci. 14(6), 1007–1018 (2003)MathSciNetCrossRef

Carle, B., Narendran, P.: On extended regular expressions. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 279–289. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00982-2_24CrossRef

Deharbe, A., Peschanski, F.: The omniscient garbage collector: a resource analysis framework. In: ACSD 2014. IEEE Computer Society (2014)

Deharbe, A., Peschanski, F.: The omniscient garbage collector: a resource analysis framework. Research report, LIP6 UPMC Sorbonne Universités, France (2014). https://hal.archives-ouvertes.fr/hal-01626770

Fontugne, R., Borgnat, P., Abry, P., Fukuda, K.: MAWILab: combining diverse anomaly detectors for automated anomaly labeling and performance benchmarking. In: ACM CoNEXT 2010 (2010)

Garg, V.K., Ragunath, M.T.: Concurrent regular expressions and their relationship to petri nets. Theor. Comput. Sci. 96(2), 285–304 (1992)MathSciNetCrossRef

10.

Kaminski, M., Francez, N.: Finite-memory automata. Theor. Comput. Sci. 134, 329–363 (1994)MathSciNetCrossRef

11.

Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions over time. CoRR, abs/1710.04073 (2017)

12.

Paranjape, A., Benson, A.R., Leskovec, J.: Motifs in temporal networks. In: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, WSDM 2017, pp. 601–610. ACM (2017)

13.

Tzevelekos, N.: Fresh-register automata. In: Proceedings of the 38th Annual ACM SIGPLAN-SIGACT, POPL 2011, pp. 295–306. ACM (2011)

14.

Ulus, D., Ferrère, T., Asarin, E., Maler, O.: Timed pattern matching. In: Legay, A., Bozga, M. (eds.) FORMATS 2014. LNCS, vol. 8711, pp. 222–236. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10512-3_16CrossRefMATH

15.

Ulus, D., Ferrère, T., Asarin, E., Maler, O.: Online timed pattern matching using derivatives. In: Chechik, M., Raskin, J.-F. (eds.) TACAS 2016. LNCS, vol. 9636, pp. 736–751. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49674-9_47CrossRef

16.

Viard, T., Fournier-S’niehotta, R., Magnien, C., Latapy, M.: Discovering patterns of interest in IP traffic using cliques in bipartite link streams. CoRR, abs/1710.07107 (2017)

17.

Waga, M., Akazaki, T., Hasuo, I.: A Boyer-Moore type algorithm for timed pattern matching. In: Fränzle, M., Markey, N. (eds.) FORMATS 2016. LNCS, vol. 9884, pp. 121–139. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44878-7_8CrossRefMATH

18.

Waga, M., Hasuo, I., Suenaga, K.: Efficient online timed pattern matching by automata-based skipping. In: Abate, A., Geeraerts, G. (eds.) FORMATS 2017. LNCS, vol. 10419, pp. 224–243. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-65765-3_13CrossRefMATH

19.

Zhang, H., Diao, Y., Immerman, N.: On complexity and optimization of expensive queries in complex event processing (2014)

Titel: Pattern Matching in Link Streams: A Token-Based Approach
verfasst von: Clément Bertrand
Hanna Klaudel
Matthieu Latapy
Frédéric Peschanski
Verlag: Springer International Publishing
Buch: Application and Theory of Petri Nets and Concurrency
Print ISBN: 978-3-319-91267-7

Electronic ISBN: 978-3-319-91268-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-91268-4_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"