Earticle

초록

영어

CP-nets (conditional preference networks) is a graphical model for representing qualitative conditional preference statements via ceteris paribus semantics interpretation. Dominance querying, the problem of determining whether an outcome is preferred to another on this graphical model, is of fundamental importance in preference querying. However, to date, the exact dominance querying algorithm with respect to any binary-valued CP-nets has not been given, hence designing an exact dominance querying algorithm is quite necessary. Fortunately, we discover that dominance querying problem is essentially a single source shortest path problem, and the induced graph of CP-nets is a sparse graph, as a result, dominance querying problem can be solved by Johnson algorithm which is suitable for solving the single source shortest path problem on sparse graph. As a byproduct, this algorithm can determine least flip numbers if an outcome dominates another outcome. At last, we present results of experiments that demonstrate the feasibility of our approach to dominance querying on acyclic CP-nets.

목차

Abstract
 1. Introduction
 2. CP-Nets Application
  2.1 CP-Nets in Assistant Decision
  2.2 CP-Nets in Preference Database Query
  2.3 CP-Nets in Social Choice
  2.4 Challenges
  2.5 Our Approach and Contributions
 3. Some Definitions about CP-Nets
  3.1 Basic Concepts
  3.2 Syntax of CP-Nets
  3.3 Semantics of CP-Nets
 4. Dominance Querying
  4.1. Induced Graph of CP-Nets
  4.2. Dominance Querying Problem
  4.3. Dominance Querying Based on SSSP
 5. Experimental Evaluation
  5.1. Experimental Environment
  5.2. Experiments on Real Data
  5.3. Experiments on Synthetic Data
  5.4. Some Works about Dominance Query
 6. Summary and Outlook
 Acknowledgements
 References

키워드

저자

• Guanlin Xin [ School of Computer and Control Engineering Yantai University, Yantai 264005, China ] Master student
• Jinglei Liu [ School of Computer and Control Engineering Yantai University, Yantai 264005, China ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  International Journal of Database Theory and Application

• 간기

  격월간

• pISSN

  2005-4270

• 수록기간

  2008~2016

• 십진분류

  KDC 505 DDC 605