Research on multiple enhanced k combination reverse Skyline query method - Song Li; Xinyuan Zhang; Liping Zhang (Journal of Big Data)
Abstract The reverse Skyline query aims to identify a set of data points that dynamically dominate a query point from the decision-makers’ perspective. It has been widely applied in business decision-making, recommendation systems, location-based services, knowledge discovery, and data mining. However, existing reverse Skyline queries mainly focus on single-point queries, overlooking multi-point combination queries. To address this, we propose the concept of combination reverse Skyline query (CRSQ), based on single query combinations. Furthermore, to handle multiple combinations with different cardinalities, we develop the Multiple Enhanced k combination reverse Skyline query method (MkECRSQ). MkECRSQ includes three main phases. Initially, we prove that k combination reverse Skyline query (kCRSQ) is NP-hard and propose a novel index structure called QR-GMap for combination queries to significantly accelerate kCRSQ. Subsequently, we compare the multiple kCRSQ results of various k values to determine the most dominant combinations. Finally, we expand the result set by proving the monotonicity of the ECRSQ algorithm. The final MkECRSQ results consist of the obtained combinations and the expanded result set. Theoretical and experimental results show that MkECRSQ not only rapidly yields results for CRSQ but also recommends the most dominant combinations to decision-makers among multiple combinations in the query dataset, while also overcoming the challenge of limited cardinality in the result sets. By introducing CRSQ and MkECRSQ, our work fills a significant research gap in reverse Skyline queries, extending their applicability to multi-point combination queries and offering enhanced decision-making support.