Exploiting symmetric relation for efficient feature interaction detection

Feature interaction detection determines whether interactions occur or not between the new and existing telecommunication services. Most of convention al detection methods on state transition model utilize an exhaustive search . The exhaustive search is fundamentally very powerful in the sense that al l interactions are exactly detected. However, it may suffer from the state explosion problem due to the exponential growth of the number of states in the model when the number of users and the number of features increase. In order to cope with this problem, we propose a new detection method using a state reduction technique. By means of a symmetric relation, called permuta tion symmetry, we succeed in reducing the size of the model while preservin g the necessary information for the interaction detection. Experimental eva luation shows that, for practical interaction detection with three users, t he proposed method achieves about 80% reduction in space and time, and is m ore scalable than the conventional ones especially for the increase of the number of users in the service.