K-Dominant Skyline Join Queries: Extending the Join Paradigm to K-Dominant Skylines
Anuradha Awasthi, Arnab Bhattacharya, Sanchit Gupta, Ujjwal Kumar Singh · 2017
Skyline queries enable multi-criteria optimization by filtering objects that are worse in all the attributes of interest than another object. To handle the large answer set of skyline queries in high-dimensional datasets, the concept of k-dominance was proposed where an object is said to dominate another object if it is better in at least k attributes. However, many practical applications, such as flights having multiple stopovers, require that the preferences are applied on a joined relation. In this paper, we extend the k-dominant skyline queries to work on joined relations. We name such queries KSJQ (k-dominant skyline join queries). We show how pre-processing the base relations helps in making such queries efficient. We also extend the query to handle cases where the skyline preference is on aggregated values in the joined relation (such as total cost of the multiple legs of the flight). In addition, we devise efficient algorithms to choose the value of k based on the desired cardinality of the skyline set. Experiments demonstrate the efficiency and scalability of our algorithms.