Web Service Selection with Incomplete or Inconsistent User Preferences

Hongbing Wang, Shizhi Shao, Xuan Zhou, Cheng Wan, Athman BouguettayaLecture Notes in Computer Science 2009 · DOI · OpenAlex

Introduction

Selecting the ideal Web service—whether it's a cloud storage provider, an API for financial data, or a travel booking engine—is increasingly complex. Users often have qualitative, conditional preferences (e.g., "I prefer a database over a file system, but only if the provider is based in the USA"). To model these requirements, researchers frequently employ Conditional Preference Networks (CP-Nets). However, a significant gap exists between theoretical CP-Net models and real-world human input. Human preferences are often incomplete, leaving too many options, or inconsistent, creating logical contradictions that result in no valid options.

The Challenge of Real-World Preferences

CP-Nets use dependency graphs to represent how preferences for one attribute depend on the values of others. While powerful, they are brittle. If a user provides an inconsistent set of rules, the resulting preference graph may contain cycles, making it impossible to determine an optimal choice. Conversely, if a user is too vague, the system may return hundreds of "optimal" services, overwhelming the user.

Figure 2: Representation of a CP-Net, including its dependency graph (a), the induced preference graph (b), and a dependency cycle (c).

Proposed Methodology: A Collaborative Pipeline

The authors propose a framework that bridges the gap between recommender systems and service selection. Instead of recommending services directly, the system uses collaborative filtering to "repair" the user's preference model. The process is organized into a multi-stage pipeline.

Figure 5: The proposed framework for service selection, highlighting the consistency checking, conflict removal, and preference complementation stages.

1. Consistency Checking and Conflict Removal

The system first scans the user's CP-Net for logical cycles. If a conflict is detected, it identifies "like-minded" historical users. Using a specialized voting scheme, the system determines which preference in the cycle is the most likely error (the least popular among similar users) and removes it to restore logical consistency.

2. Efficient Similarity Detection

To find similar users in real-time, the authors developed a distance formula for CP-Nets. They proved (Theorem 1) that if users share a common underlying dependency structure, the distance can be calculated in linear time. This is a major breakthrough, as induced preference graphs normally grow exponentially with the number of attributes.

3. Preference Complementation

When a search query is too broad and returns an unmanageable number of results, the system looks at the preferences of similar users to suggest additional constraints. By automatically adding these "borrowed" preferences, the system narrows the result set to a manageable size (e.g., fewer than 20 services).

Experimental Results

The framework was evaluated using simulated data consisting of 10,000 services and 5,000 historical users. The results demonstrated significant pruning power: in scenarios with six attributes, adding just three borrowed preferences reduced the matching service count from 800 down to 20.

Furthermore, the system proved highly scalable. Even with complex attributes, the conflict removal and complementation processes took only a few dozen milliseconds on standard hardware. This confirms that the linear-time optimizations allow the system to function effectively in real-time environments.

Conclusion

By applying collaborative filtering to the structure of user preferences rather than just the end products, this research offers a robust solution for handling the "messiness" of human requirements in Web service selection. While the reliance on a shared dependency graph and the need for a "warm" historical database are noted limitations, the approach successfully transforms a computationally hard problem into a scalable, user-friendly service selection tool.

Summary updated

BibTeX
@inproceedings{wang2009web,
  author = {Hongbing Wang and Shizhi Shao and Xuan Zhou and Cheng Wan and Athman Bouguettaya},
  title = {{Web Service Selection with Incomplete or Inconsistent User Preferences}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2009},
  doi = {10.1007/978-3-642-10383-4\_6},
}
Figure