Algorithm on Computing Skyline over Probabilistic Data Stream
Zhou Li-xin · Dianzi xuebao · 2009
Management and analysis of uncertain,probabilistic data stream has attracted considerable attention within database community.Skyline query processing is an open question recently.Although previous work has addressed skyline computations over static data or traditional data stream,skyline computation over probabilistic data stream is still at large.We propose an efficient algorithm SOPDS to handle this issue.Based on more adaptable grid index,a set of heuristic rules like probability bounding,progressive refinement,pre-elimination and selective compensation are developed to improve the comprehensive performance of SOPDS from point of reducing both CPU overhead and memory consumption.Massive experiments demonstrate that SOPDS is of high overall performance.