Combining CP−Nets with the Power of Ontologies

Abstract

The Web is currently shifting from data on linked Web pages towards less interlinked data in social networks on the Web. Therefore, rather than being based on the link structure between Web pages, the ranking of search results needs to be based on something new. We believe that it can be based on user preferences and ontological background knowledge, as a means to personalized access to information. There are many approaches to preference representation and reasoning in the literature. The most prominent qualitative ones are perhaps CP-nets. Their clear graphical structure unifies an easy representation of preferences with nice properties when computing the best outcome. In this paper, we introduce ontological CP-nets, where the knowledge domain has an ontological structure, i.e., the values of the variables are constrained relative to an underlying ontology. We show how the computation of Pareto optimal outcomes for such ontological CP-nets can be reduced to the solution of constraint satisfaction problems. We also provide several complexity and tractability results.