Improving the Quality of Online Search Services: On the Service Multi-selection Problem

摘要

The global objective of this study is to propose solutions for improving the quality of online search services. We consider the special case where the processing of requests submitted to such services consists of: the querying of several types of sub-services followed by the composition of the output produced the sub-services. This could be the case for instance of a booking service that proposes travel packs including: hotel reservation, car rental and flight booking. We propose to improve the quality of such services with the multi-selection problem. The goal in this problem is to select the subset of sub-services of each type to use in the the processing of search request. The selection must ensure that we maximize the quality of the results we could expect from the search. The multi-selection problem is close to the service selection problem. However, while in the latter, we are interested in a unique sub-service per type, in the former, we want to choose a subset of sub-services. Our paper introduces a theoretical formulation of the problem and demonstrates its NP-hardness. We also propose two approaches for the resolution. The first approach is based on Integer Linear Programming. The second approach combines parallel algorithm portfolio and sampling techniques. Finally, we make a comparative evaluation of the approaches based on practical scenarios.