Competitive Skyline Cliques

Abstract

Decision-making is hard when presented with a large set of similar options that insignificantly tradeoff amongst a range of attributes. This phenomenon is encountered within the skyline set because no skyline point is strictly better than any other skyline point, and therefore, every skyline point can excel ever so slightly in some subspace of attributes. The objective of this work is to determine the set of all sets of skyline points that are hard to choose from and hence all points in a set compete for attention from the same type of consumer (such sets are called competitive skyline cliques) In this work, two skyline points are defined to be competitive if the differences between the two points across each attribute are bounded by specified thresholds. We introduce maximal competitive skyline cliques (MCSCs) – maximal sets of mutually competitive skyline points and provide algorithms that enumerate all MCSCs. While the problem of enumerating all MCSCs is structurally similar to the NP-Hard problem of enumerating all maximal cliques in a graph, because of properties exhibited by our competitiveness metric, we show that enumerating all MCSCs can be performed efficiently in polynomial time. Furthermore, in 2D space, we provide an optimal linear-time sweepline algorithm. We also provide a bounded approximation for MCSCs that are easier to enumerate. Our extensive experiments using both synthetic and real (UCars, FIFA22 and Pokemon) datasets demonstrate the ´ efficacy of MCSCs and the efficiency of our algorithms.