Exploiting Symmetric Relation for Efficient Feature Interaction Detection

Masahide NAKAMURA  Tohru KIKUNO  

IEICE TRANSACTIONS on Information and Systems   Vol.E82-D   No.10   pp.1352-1363
Publication Date: 1999/10/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Networks
feature interactions,  telecommunication services,  permutation symmetry,  state reduction,  

Full Text: PDF(915.4KB)>>
Buy this Article

Feature interaction detection determines whether interactions occur or not between the new and existing telecommunication services. Most of conventional detection methods on state transition model utilize an exhaustive search. The exhaustive search is fundamentally very powerful in the sense that all 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 permutation symmetry, we succeed in reducing the size of the model while preserving the necessary information for the interaction detection. Experimental evaluation shows that, for practical interaction detection with three users, the proposed method achieves about 80% reduction in space and time, and is more scalable than the conventional ones especially for the increase of the number of users in the service.