Probabilistic k-skyband operator over sliding windows

Feng, X; Zhang, W; Zhao, X; Zhang, Y; Gao, Y

Probabilistic k-skyband operator over sliding windows

Feng, X Zhang, W Zhao, X Zhang, Y

Gao, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 7923 LNCS pp. 190 - 202
Issue Date:: 2013-07-16

Closed Access

	Filename	Description	Size
	10.1007%2F978-3-642-38562-9_20.pdf	Published version	348.7 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	Feng, X	en_US
dc.contributor.author	Zhang, W	en_US
dc.contributor.author	Zhao, X	en_US
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638	en_US
dc.contributor.author	Gao, Y	en_US
dc.date.issued	2013-07-16	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2013, 7923 LNCS pp. 190 - 202	en_US
dc.identifier.isbn	9783642385612	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/120805
dc.description.abstract	Given a set of data elements in a d-dimensional space, a k-skyband query reports the set of elements which are dominated by at most k - 1 other elements in. k-skyband query is a fundamental query type in data analyzing as it keeps a minimum candidate set for all top-k ranking queries where the ranking functions are monotonic. In this paper, we study the problem of k-skyband over uncertain data streams following the possible world semantics where each data element is associated with an occurrence probability. Firstly, a dynamic programming based algorithm is proposed to identify k-skyband results for a given set of uncertain elements regarding a pre-specified probability threshold. Secondly, we characterize the minimum set of elements to be kept in the sliding window to guarantee correct computing of k-skyband. Thirdly, efficient update techniques based on R-tree structures are developed to handle frequent updates of the elements over the sliding window. Extensive empirical studies demonstrate the efficiency and effectiveness of our techniques. © 2013 Springer-Verlag Berlin Heidelberg.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-642-38562-9-20	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Probabilistic k-skyband operator over sliding windows	en_US
dc.type	Conference Proceeding
utslib.citation.volume	7923 LNCS	en_US
utslib.for	0806 Information Systems	en_US
utslib.for	080109 Pattern Recognition and Data Mining	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/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Life Sciences
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US
pubs.volume	7923 LNCS	en_US

Abstract:

Given a set of data elements in a d-dimensional space, a k-skyband query reports the set of elements which are dominated by at most k - 1 other elements in. k-skyband query is a fundamental query type in data analyzing as it keeps a minimum candidate set for all top-k ranking queries where the ranking functions are monotonic. In this paper, we study the problem of k-skyband over uncertain data streams following the possible world semantics where each data element is associated with an occurrence probability. Firstly, a dynamic programming based algorithm is proposed to identify k-skyband results for a given set of uncertain elements regarding a pre-specified probability threshold. Secondly, we characterize the minimum set of elements to be kept in the sliding window to guarantee correct computing of k-skyband. Thirdly, efficient update techniques based on R-tree structures are developed to handle frequent updates of the elements over the sliding window. Extensive empirical studies demonstrate the efficiency and effectiveness of our techniques. © 2013 Springer-Verlag Berlin Heidelberg.

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

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