For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Top (k1,k2) Query in Uncertain Datasets
Fei LIU Jiarun LIN Yan JIA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/11/01
Online ISSN: 1745-1361
Type of Manuscript: LETTER
Category: Artificial Intelligence, Data Mining
uncertain query, top k, x-tuple, possible world,
Full Text: PDF(323.1KB)>>
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.