Efficient Processing of Top-K Dominating Queries on Incomplete Data Using MapReduce

Top-k dominating queries, which return the k best items with a comprehensive “goodness” criterion based on dominance, have attracted considerable attention recently due to its important role in many data mining applications including multi-criteria decision making. In the Big Data era, the modes of data storage and processing are becoming distributed, and data is incomplete commonly in some real applications. The related existing researches focus on centralized datasets, or on complete data in distributed environments, and do not involve incomplete data in distributed environments. In this work, we present the first study for processing top-k dominating queries on incomplete data in distributed environments. We show that, through detailed analysis, even though the dominance relation on incomplete data objects is non-transitive in general, the transitive dominance relation holds for some incomplete data objects with different bitmaps. We then propose an novel algorithm TKDI-MR based on MapReduce for processing TKD queries on incomplete data in distributed environments utilizing the aforementioned property. Extensive experiments with both real-world and large-scale synthetic datasets demonstrate that our approach is able to achieve good efficiency and stability.