Context Matching for Ambient Intelligence Applications

Reliable and scalable Ambient Intelligence means a distributed system of agents that are capable of working together or autonomously, depending on the requirements of the situation. In previous research we have argued in favor of the use of a representation for context information that can be distributed among agents, so that each agent knows only the information that is relevant to its activity. Recognizing interesting information or relevant situations is done by using context patterns -- graph patterns with potentially unknown nodes and edges labeled with regular expressions. In this context, a major challenge is for agents to use a graph matching algorithm that is adequate to the possibilities of the devices on which the agents are running. Moreover, it is necessary that the algorithm is able to provide partial matches. This paper presents an algorithm specifically designed for this problem, that uses growing partial matches to obtain the maximum sub-graph of the context graph that matches (part of) the context pattern. Experiments were performed with the algorithm and its performance has been compared with that of other algorithms adapted to our problem.