Efficient Maintaining of Skyline over Probabilistic Data Stream

Inherent uncertainty and unreliability of data exists widely in emerging applications, like sensor network based ubiquitous computation, results output in information extraction and data integration, etc. Multidimensional skyline analysis is crucial to multicriteria decision-making. Although previous work has addressed skyline computation over traditional data stream, skyline computation over probabilistic data stream is still at large. In this paper, we model this issue formally based on "possible worlds" semantics, furthermore an effective and efficient algorithm is proposed to handle this issue. Based on grid index, a set of heuristics like probability bounding, progressive refinement, pre-elimination and selective compensation are developed to improve the overall performance from the point of reducing both CPU and space overhead. Detailed experiments demonstrated that our algorithm is efficient, stable and scalable.