中文摘要：

SOPDS是一种概率数据流上的skyline查询算法，它主要采用网格索引结构，使用概率定界、逐步求精、提前淘汰和选择补偿等启发式规则从时间和空间两个方面进行系统的优化。通过对对象间支配关系的进一步分析，在SOPDS算法的基础上，增加有效的过滤策略和对象身份判定规则，实现了改进的算法（ISOPDS）。实验表明，ISOPDS算法能有效地减少查询响应时间。

英文摘要：

SOPDS is a kind of skyline query algorithm over probabilistic data stream. Based on grid index, a set of heuristic rules like probability bounds, progressive refinement, pre-elimination and selective compensation are devel- oped to improve the comprehensive performance of SOPDS on both CPU overhead and memory consumption. Through the analysis of the dominance relationship between uncertain objects, more effective filtering strategy and object iden- tity decision rule are added to SOPDS. And SOPDS is improved to a novel algorithm, ISOPDS. The experimental results show that ISOPDS could reduce the response time of skyline query effectively.