Top (k1,k2) Query in Uncertain Datasets

Fei LIU  Jiarun LIN  Yan JIA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.11   pp.1998-2002
Publication Date: 2015/11/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015EDL8077
Type of Manuscript: LETTER
Category: Artificial Intelligence, Data Mining
Keyword: 
uncertain query,  top k,  x-tuple,  possible world,  

Full Text: PDF(323.1KB)>>
Buy this Article




Summary: 
In this letter, we propose a novel kind of uncertain query, top (k1,k2) query. The x-tuple model and the possible world semantics are used to describe data objects in uncertain datasets. The top (k1,k2) query is going to find k2 x-tuples with largest probabilities to be the result of top k1 query in a possible world. Firstly, we design a basic algorithm for top (k1,k2) query based on dynamic programming. And then some pruning strategies are designed to improve its efficiency. An improved initialization method is proposed for further acceleration. Experiments in real and synthetic datasets prove the performance of our methods.