A graph-matching approach to dynamic media allocation in intelligent multimedia interfaces

Abstract

To aid users in exploring large and complex data sets, we are building an intelligent multimedia conversation system. Given a user request, our system dynamically creates a multimedia response that is tailored to the interaction context. In this paper, we focus on the problem of media allocation, a process that assigns one or more media, such as graphics or speech, to best convey the intended response content. Specifically, we develop a graph-matching approach to media allocation, whose goal is to find a set of data-media mappings that maximizes the satisfaction of various allocation constraints (e.g., data-media compatibility and presentation consistency constraints). Compared to existing rule-based or plan-based approaches to media allocation, our work offers three unique contributions. First, we provide an extensible computational framework that optimizes media assignments by dynamically balancing all relevant constraints. Second, we use feature-based metrics to uniformly model various allocation constraints, including those cross-content and cross-media constraints, which often require special treatment in existing approaches. Third, we further improve the quality of a response by automatically detecting and repairing undesired allocation results. We have applied our approach to two different applications and our preliminary study has shown the promise of our work Copyright 2005 ACM.