Probabilistic k-skyband operator over sliding windows

Publication Type:
Conference Proceeding
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:
Filename Description Size
10.1007%2F978-3-642-38562-9_20.pdfPublished version348.7 kB
Adobe PDF
Full metadata record
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: