Forming the Best Team for a Composite Competition

摘要

In a large database, the top-k query is an important mechanism to retrieve the most valuable information for the users, which ranks data objects with a ranking function and reports the k objects with the highest scores. However, as an object usually has various scores in the real world, ranking objects without information loss becomes challenging. In this paper, we model the object with multiple scores as an uncertain data object, where the uncertainty of the object is captured by a distribution of the scores, and address a novel problem named Best-kTEAM query, which discovers the best team with k players for a composite competition consisting of several games each of which requires a distinct number of players. To tackle the problem, we develop a dynamic programming based approach TeamGen to generate all possible solutions. Then, we introduce the notion of skyline teams with the property that none of them has a higher aggregated probability to be the top one for all games against the others and propose a filtering approach SubsetFilter to fast retrieve candidate solutions. Furthermore, instead of TeamGen, two heuristic approaches IgnoreTeamGen and LimitTeamGen are proposed to attempt to obtain possible solutions with better efficiency. The simulation shows the superiority of Best-kTEAM query in a composite competition and the proposed algorithms outperform the baseline approaches.