Top-k Dominating Queries on Incomplete Data

Abstract

The top-k doming (TKD) query returns k objects that exceed the maximum number of objects in a given dataset. It combines the advantages of skype and top k queries, and plays an important role in many decision support applications. There is incomplete data in a wide range of real data sets, due to hardware failure, privacy preservation, data loss, etc. In this paper, for the first time, we conduct a systematic study of TKD queries on incomplete data, which include data that contains some missing dimension values (dimensions). We formalize this problem and suggest a set of effective algorithms to answer TKD queries on incomplete data. Our methods use some new techniques, such as high point pruning, point pruning, and partial evaluation, to enhance query efficiency. Intensive experimental evaluation using real and industrial data sets demonstrates the effectiveness of advanced exploration and evolution methods for the performance of our submitted algorithms.