Top (k1,k2) Query in Uncertain Datasets

Fei LIU; Jiarun LIN; Yan JIA

doi:10.1587/transinf.2015EDL8077

Top (k₁,k₂) Query in Uncertain Datasets

Fei LIU, Jiarun LIN, Yan JIA

Full Text Views

0

Share
Cite this

Summary :

In this letter, we propose a novel kind of uncertain query, top (k₁,k₂) query. The x-tuple model and the possible world semantics are used to describe data objects in uncertain datasets. The top (k₁,k₂) query is going to find k₂ x-tuples with largest probabilities to be the result of top k₁ query in a possible world. Firstly, we design a basic algorithm for top (k₁,k₂) 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.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.11 pp.1998-2002

Publication Date: 2015/11/01

Publicized: 2015/07/22

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2015EDL8077

Type of Manuscript: LETTER

Category: Artificial Intelligence, Data Mining

Authors

Fei LIU
  National University of Defense Technology
Jiarun LIN
  National University of Defense Technology
Yan JIA
  National University of Defense Technology

Keyword

uncertain query, top k, x-tuple, possible world

Cite this

Copy

Fei LIU, Jiarun LIN, Yan JIA, "Top (k1,k2) Query in Uncertain Datasets" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 11, pp. 1998-2002, November 2015, doi: 10.1587/transinf.2015EDL8077.
Abstract: In this letter, we propose a novel kind of uncertain query, top (k₁,k₂) query. The x-tuple model and the possible world semantics are used to describe data objects in uncertain datasets. The top (k₁,k₂) query is going to find k₂ x-tuples with largest probabilities to be the result of top k₁ query in a possible world. Firstly, we design a basic algorithm for top (k₁,k₂) 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2015EDL8077/_p

Copy

@ARTICLE{e98-d_11_1998,
author={Fei LIU, Jiarun LIN, Yan JIA, },
journal={IEICE TRANSACTIONS on Information},
title={Top (k1,k2) Query in Uncertain Datasets},
year={2015},
volume={E98-D},
number={11},
pages={1998-2002},
abstract={In this letter, we propose a novel kind of uncertain query, top (k₁,k₂) query. The x-tuple model and the possible world semantics are used to describe data objects in uncertain datasets. The top (k₁,k₂) query is going to find k₂ x-tuples with largest probabilities to be the result of top k₁ query in a possible world. Firstly, we design a basic algorithm for top (k₁,k₂) 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.},
keywords={},
doi={10.1587/transinf.2015EDL8077},
ISSN={1745-1361},
month={November},}

Copy

TY - JOUR
TI - Top (k1,k2) Query in Uncertain Datasets
T2 - IEICE TRANSACTIONS on Information
SP - 1998
EP - 2002
AU - Fei LIU
AU - Jiarun LIN
AU - Yan JIA
PY - 2015
DO - 10.1587/transinf.2015EDL8077
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2015
AB - In this letter, we propose a novel kind of uncertain query, top (k₁,k₂) query. The x-tuple model and the possible world semantics are used to describe data objects in uncertain datasets. The top (k₁,k₂) query is going to find k₂ x-tuples with largest probabilities to be the result of top k₁ query in a possible world. Firstly, we design a basic algorithm for top (k₁,k₂) 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.
ER -