Threshold-based probabilistic top-k dominating queries

Zhang, W; Lin, X; Zhang, Y; Pei, J; Wang, W

Threshold-based probabilistic top-k dominating queries

Zhang, W Lin, X Zhang, Y

Pei, J Wang, W

Permalink

Publication Type:: Journal Article
Citation:: VLDB Journal, 2010, 19 (2), pp. 283 - 305
Issue Date:: 2010-01-01

Closed Access

	Filename	Description	Size
	2013005446OK.pdf		904.83 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, W	en_US
dc.contributor.author	Lin, X	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Pei, J	en_US
dc.contributor.author	Wang, W	en_US
dc.date.issued	2010-01-01	en_US
dc.identifier.citation	VLDB Journal, 2010, 19 (2), pp. 283 - 305	en_US
dc.identifier.issn	1066-8888	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28917
dc.description.abstract	Recently, due to intrinsic characteristics in many underlying data sets, a number of probabilistic queries on uncertain data have been investigated. Top-k dominating queries are very important in many applications including decision making in a multidimensional space. In this paper, we study the problem of efficiently computing top-k dominating queries on uncertain data. We first formally define the problem. Then, we develop an efficient, threshold-based algorithm to compute the exact solution. To overcome some inherent computational deficiency in an exact computation, we develop an efficient randomized algorithm with an accuracy guarantee. Our extensive experiments demonstrate that both algorithms are quite efficient, while the randomized algorithm is quite scalable against data set sizes, object areas, k values, etc. The randomized algorithm is also highly accurate in practice. © Springer-Verlag 2009.	en_US
dc.relation.ispartof	VLDB Journal	en_US
dc.relation.isbasedon	10.1007/s00778-009-0162-1	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Threshold-based probabilistic top-k dominating queries	en_US
dc.type	Journal Article
utslib.citation.volume	2	en_US
utslib.citation.volume	19	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	0804 Data Format	en_US
utslib.for	0805 Distributed Computing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.issue	2	en_US
pubs.publication-status	Published	en_US
pubs.volume	19	en_US

Abstract:

Recently, due to intrinsic characteristics in many underlying data sets, a number of probabilistic queries on uncertain data have been investigated. Top-k dominating queries are very important in many applications including decision making in a multidimensional space. In this paper, we study the problem of efficiently computing top-k dominating queries on uncertain data. We first formally define the problem. Then, we develop an efficient, threshold-based algorithm to compute the exact solution. To overcome some inherent computational deficiency in an exact computation, we develop an efficient randomized algorithm with an accuracy guarantee. Our extensive experiments demonstrate that both algorithms are quite efficient, while the randomized algorithm is quite scalable against data set sizes, object areas, k values, etc. The randomized algorithm is also highly accurate in practice. © Springer-Verlag 2009.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/28917