Publication Type

Journal Article

Version

acceptedVersion

Publication Date

1-2016

Abstract

The top-k dominating (TKD) query returns the k objects that dominate the maximum number of objects in a given dataset. It combines the advantages of skyline and top-k queries, and plays an important role in many decision support applications. Incomplete data exists in a wide spectrum of real datasets, due to device failure, privacy preservation, data loss, and so on. In this paper, for the first time, we carry out a systematic study of TKD queries on incomplete data, which involves the data having some missing dimensional value(s). We formalize this problem, and propose a suite of efficient algorithms for answering TKD queries over incomplete data. Our methods employ some novel techniques, such as upper bound score pruning, bitmap pruning, and partial score pruning, to boost query efficiency. Extensive experimental evaluation using both real and synthetic datasets demonstrates the effectiveness of our developed pruning heuristics and the performance of our presented algorithms.

Keywords

Top-k dominating query, Incomplete data, Query processing, Dominance relationship, Algorithm

Discipline

Computer Sciences | Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

28

Issue

1

First Page

252

Last Page

266

ISSN

1041-4347

Identifier

10.1109/TKDE.2015.2460742

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Additional URL

http://dx.doi.org/10.1109/TKDE.2015.2460742

Download

Share

COinS