MEASURING EFFICIENCY OF INFERENCE ENGINES
DOI:
https://doi.org/10.26906/SUNZ.2020.4.081Keywords:
production systems, pattern matching, benchmarks, ReteAbstract
The subject of research is the pattern matching algorithms that are used in software tools for developing rule-based systems. The goal of this work is to stipulate the characteristics for the selection and generation of benchmarks for pattern matching algorithms, depending on the specifics of the problems being solved. The following tasks have been fulfilled: determination of test task problematic, analysis of pattern matching algorithms, underlining the main approaches and methods of establishing benchmarks. The analyzed methods include Rete, Treat and their modifications, as well as approaches to the generation of benchmarks for analyzing the performance of pattern matching algorithms and rule-based systems. The following results were obtained. The concepts of basic pattern matching algorithms are presented to highlight significant characteristics that affect matching performance in terms of runtime and knowledge base structure. The definition of characteristics was done according to two approaches: the first approach relates to inference in systems based on rules (rule-base) and second one is used for systems of the Semantic Web. Basic test problems that are commonly used as benchmarks have been defined. The main benchmarks of the pattern matching algorithms are presented, with the corresponding definition of the specifics of their area of use. Conclusions. The problems of analyzing the efficiency of inference mechanisms for various types of applied systems are defined. The conceptual differences of the basic pattern matching algorithms are presented. Features which affect the requirements for the establishing or selection of benchmarks are identified. Based on the analysis, the main characteristics of benchmarks for productive systems and Semantic Web systems are provided. The main approaches and methods for the formation of benchmarks are defined. A promising direction for further research is the expansion of the proposed solution by the development of new solutions to enable representations of the generated knowledge bases in terms of first order logic
Downloads
References
Riley G. Rearchitecting CLIPS. Business Rules Knowledge Base. October Rulefest 2008. available at: http://bizrules.info/conference/ORF2008DFW/GaryRiley_RearchitectingCLIPS_ORF2008.pdf (last accessed 20.10.20).
Miranker D. P. Treat: A better match algorithm for AI production systems. ArtificialIntelligence: SixthNationalConference AAAI-87. 1987. P.42—47.
Riley G. The CLIPS Implementation of the Rete Pattern Matching Algorithm. 2009. Corpus ID: 33742322
Bobek, S., Misiak, P. (2017), "Framework for Benchmarking Rule-Based Inference Engines", Artificial Intelligence and Soft Computing, ICAISC 2017, Lecture Notes in Computer Science, vol. 10246, Springer, Cham. P. 399-410. DOI:https://doi.org/10.1007/978-3-319-59060-8_36
S. Liang, P. Fodor, H. Wan, and M. Kifer, (2009), "OpenRuleBench: An analysis of the performance of rule engines", Proc.18th International Conference on World Wide Web, P.601–610. DOI: https://doi.org/10.1145/1526709.1526790.
Rattanasawad, T., Buranarach, M., Saikaew, K.R., Supnithi, T. (2018), "A Comparative Study of Rule-Based Inference Engines for the Semantic Web", IEICE Transactions on Information and Systems, January 2018, P. 82-89. DOI:https://doi.org/10.1587/transinf.2017SWP0004
Шаповалова С.І., Мажара О.О. Вибір оптимального алгоритму співставлення зі зразком при проектуванні продукційної системи. Східно-Європейський журнал передових технологій. 2014, Вип.2/2(68). С. 43-49.
Forgy C. On the Efficient Implementation of Production System. Ph.D. Dissertation. Carnegie Mellon University. 1979.210 p.
H. Cirstea C. Kirchner M. M., Moreau P. Production Systems and Rete Algorithm Formalisation. Research Report: ILOG,INRIA, 2004. URL: https://hal.inria.fr/inria-00280938/file/rete.formalisation.pdf.
Шаповалова С.І., Мажара О.О. Формалізація базових алгоритмів співставлення зі зразком в продукційних системах.Східно-Європейський журнал передових технологій. 2015. Вип.4/3(76). С. 22-27. DOI: 10.15587/1729-4061.2015.46571
Ligeza A. Logical Foundations for Rule-Based Systems. Studies in Computational Intelligence (SCI). 2006. 11.P.191-198.
Wright I. Marshall J. The execution kernel of RC++: RETE*, a faster RETE with TREAT as a special case. Int. J. Intell.Games & Simulation 2 (1). 2003. P.36-48.URL: https://books.google.com.ua/books?id=R5EHCAAAQBAJ
Hicks R.C., Wright K. (2009), "Performance Testing of Propositional Logic Inference Engines", Journal of ComputerInformation Systems, Published online. Vol. 49, P. 122-126.
Doorenbos R. Production Matching for Large Learning Systems. Ph.D. Dissertation. Carnegie Mellon University. 1995.208 p.
Hanson E.N., Hasan M.S. Gator: Anoptimized discrimination network for active database rule condition testing. Tech. Rep.93-036, CIS Department University of Florida. 1993. 27 p.
Kim M., Lee K., Kim Y., T. Kim, Lee Y, Cho S., Lee C. RETE-ADH: An Improvement to RETE forCompositeContextAware Service. International Journal of Distributed Sensor Networks. 2014 —11p. 69.DOI: 10.1155/2014/507160
Bouaud J., Zweigenbaum P. A reconstruction of conceptual graphs on top of a production system. Conceptual Structures:Theory and Implementation Ed. by H. Pfeiffer, T. Nagle. 1993. Vol. 754. P.125–136.
Shapovalova S. Generation of test bases of rules for the analysis of productivity of logical inference engine. InnovativeTechnologies and Scientific Solutions for Industries. 2020. No. 3(13). P. 88–96. DOI: https://doi.org/10.30837/ITSSI.2020.13.088.
