Improved RETE Algorithm in Context Reasoning for Web of Things Environments
Teng Gao, Xiaofeng Qiu, Lijuan He · 2013
RETE is the most efficient forward inference algorithm for the development of context-aware rule-based systems. The performance of context reasoning engines in context-aware systems depends mainly on the efficiency of the pattern matching in "Cognition-Execution Loop". Nowadays many real-world contexts from WoT (Web of Things) environments have data characteristics such as large amount, quick change and lots of constant operation, imposing a trade-off between the cost of time and space of RETE algorithm. Thus, in this paper RETE+ - an improved RETE network is proposed, capable of handling context from WoT environment, which actually includes different types of data for reasoning with new characteristics. RETE+ algorithm applies shortcut memory using LRU (Least-Recently-Used) algorithm to the matching process of alpha network and solves the problems of intensive computation with all the alpha nodes. This approach takes advantage of the LRU algorithm to select alpha nodes with the highest possibility to be executed, which considerably reduces the computation overhead. The proposed approach is applied to context reasoning engine and evaluated through contrast experiments using real-world WoT data. The case study and experimental analysis demonstrate the capability of the proposed algorithm.