Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-23T09:23:30.687Z Has data issue: false hasContentIssue false
  • English
  • Français

A Distributed Approach to LARS Stream Reasoning (System paper)

Published online by Cambridge University Press:  20 September 2019

THOMAS EITER ,
PAUL OGRIS Open the ORCID record for PAUL OGRIS [Opens in a new window]  and
KONSTANTIN SCHEKOTIHIN Open the ORCID record for KONSTANTIN SCHEKOTIHIN [Opens in a new window]
THOMAS EITER
Affiliation:
Technische Universität Wien, Institut für Logic and Computation, KBS Group (e-mail: [email protected])
PAUL OGRIS
Affiliation:
Alpen-Adria-Universität, Klagenfurt, Austria (e-mail: [email protected], [email protected])
KONSTANTIN SCHEKOTIHIN
Affiliation:
Alpen-Adria-Universität, Klagenfurt, Austria (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Stream reasoning systems are designed for complex decision-making from possibly infinite, dynamic streams of data. Modern approaches to stream reasoning are usually performing their computations using stand-alone solvers, which incrementally update their internal state and return results as the new portions of data streams are pushed. However, the performance of such approaches degrades quickly as the rates of the input data and the complexity of decision problems are growing. This problem was already recognized in the area of stream processing, where systems became distributed in order to allocate vast computing resources provided by clouds. In this paper we propose a distributed approach to stream reasoning that can efficiently split computations among different solvers communicating their results over data streams. Moreover, in order to increase the throughput of the distributed system, we suggest an interval-based semantics for the LARS language, which enables significant reductions of network traffic. Performed evaluations indicate that the distributed stream reasoning significantly outperforms existing stand-alone LARS solvers when the complexity of decision problems and the rate of incoming data are increasing.

Keywords

Stream reasoningdistributed systemsAnswer Set Programming
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 19 , Special Issue 5-6: 35th International Conference on Logic Programming , September 2019 , pp. 974 - 989
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley.Google Scholar
Allen, J. F. 1983. Maintaining Knowledge about Temporal Intervals. CACM 26, 11, 832–843.CrossRefGoogle Scholar
Alur, R., Feder, T., and Henzinger, T. A. 1996. The Benefits of Relaxing Punctuality. Journal of the ACM 43, 1, 116–146.Google Scholar
Anicic, D., Rudolph, S., Fodor, P., and Stojanovic, N. 2012. Stream reasoning and complex event processing in ETALIS. Semantic Web 3, 4, 397–407.Google Scholar
Apt, K. R., Blair, H. A., and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann, 89–148.Google Scholar
Arasu, A., Babu, S., and Widom, J. 2006. The CQL continuous query language: Semantic foundations and query execution. VLDB J. 15, 2, 121–142.Google Scholar
Barbieri, D. F., Braga, D., Ceri, S., Valle, E. D., and Grossniklaus, M. 2010. Incremental reasoning on streams and rich background knowledge. In ESWC (1). Lecture Notes in Computer Science, vol. 6088. Springer, 1–15.Google Scholar
Bazoobandi, H. R., Beck, H., and Urbani, J. 2017. Expressive stream reasoning with laser. In ISWC (1). Lecture Notes in Computer Science, vol. 10587. Springer, 87–103.Google Scholar
Beck, H. 2018. Expressive rule-based stream reasoning. Ph.D. thesis, Faculty of Informatics, Vienna University of Technology (TU Wien), Austria.Google Scholar
Beck, H., Bierbaumer, B., Dao-Tran, M., Eiter, T., Hellwagner, H., and Schekotihin, K. 2017. Stream reasoning-based control of caching strategies in CCN routers. In IEEE International Conference on Communications (ICC). IEEE Press, 1–6.Google Scholar
Beck, H., Dao-Tran, M., and Eiter, T. 2015. Answer update for rule-based stream reasoning. In IJCAI. AAAI Press, 2741–2747.Google Scholar
Beck, H., Dao-Tran, M., and Eiter, T. 2018. LARS: A logic-based framework for analytic reasoning over streams. Artif. Intell. 261, 16–70.Google Scholar
Beck, H., Eiter, T., and Folie, C. 2017. Ticker: A system for incremental asp-based stream reasoning. TPLP 17, 5-6, 744–763.Google Scholar
Brandt, S., Kalayci, E. G., Kontchakov, R., Ryzhikov, V., Xiao, G., and Zakharyaschev, M. 2017. Ontology-based data access with a horn fragment of metric temporal logic. In AAAI. AAAI Press, 1070–1076.Google Scholar
Doyle, J. 1979. A truth maintenance system. Artif. Intell. 12, 3, 231–272.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T. 2014. Clingo = ASP + control: Preliminary report. CoRR abs/1405.3694.Google Scholar
Gent, I. P., Jefferson, C., and Nightingale, P. 2017. Complexity of n-queens completion. J. Artif. Intell. Res. 59, 815–848.Google Scholar
Heintz, F. and Doherty, P. 2004. DyKnow: An Approach to Middleware for Knowledge Processing. Journal of Intelligent and Fuzzy Systems 15, 1, 3–13.Google Scholar
Heintz, F., Kvarnström, J., and Doherty, P. 2010. Stream-based reasoning in dyknow. In Cognitive Robotics. Dagstuhl Seminar Proceedings, vol. 10081. Schloss Dagstuhl, Germany.Google Scholar
Maler, O. and Nickovic, D. 2004. Monitoring temporal properties of continuous signals. In FORMATS/FTRTFT. Lecture Notes in Computer Science, vol. 3253. Springer, 152–166.Google Scholar
Pham, T., Ali, M. I., and Mileo, A. 2019. Enhancing the scalability of expressive stream reasoning via input-driven parallelization. Semantic Web 10, 3, 457–474.CrossRefGoogle Scholar
Phuoc, D. L., Dao-Tran, M., Parreira, J. X., and Hauswirth, M. 2011. A native and adaptive approach for unified processing of linked streams and linked data. In ISWC (1). Lecture Notes in Computer Science, vol. 7031. Springer, 370–388.Google Scholar
Ren, X. 2018. Distributed RDF stream processing and reasoning. Ph.D. thesis, Université Paris-Est, France. https://tel.archives-ouvertes.fr/tel-02083973/document.Google Scholar
Ren, X., Curé, O., Naacke, H., and Xiao, G. 2018. RDF stream reasoning via answer set programming on modern big data platform. In International Semantic Web Conference (P&D/Industry/BlueSky). CEUR Workshop Proceedings, vol. 2180. CEUR-WS.org.Google Scholar
Valle, E. D., Ceri, S., van Harmelen, F., and Fensel, D. 2009. It’s a streaming world! reasoning upon rapidly changing information. IEEE Intelligent Systems 24, 6, 83–89.Google Scholar