Monochromatic and bichromatic mutual skyline queries

• We formalize and solve the monochromatic and bichromatic MSQ problem.
• We propose four algorithms to efficiently compute MSQs.
• We demonstrate the effectiveness and efficiency of our methods.
• The best algorithm is 2 orders of magnitude faster than basic algorithm.

In this paper, we study a new skyline operator, namely, mutual skyline query (MSQ), which retrieves all the data objects that are contained in the dynamic skyline and meanwhile the reverse skyline of a specified query object q. MSQ has many applications such as marketing analysis, task allocation, and personalized matching. Motivated by this, we first formalize MSQ in both monochromatic and bichromatic cases, and then propose several algorithms for processing MSQ. Our methods utilize a conventional data-partitioning index on the dataset, employ the advantage of reusing technique, and exploit effective pruning heuristics to improve the query processing. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness and efficiency of our proposed algorithms under various experimental settings.