期刊名称：International Journal of Distributed Sensor Networks
印刷版ISSN：1550-1329
电子版ISSN：1550-1477
出版年度：2015
卷号：2015
DOI：10.1155/2015/359137
出版社：Hindawi Publishing Corporation
摘要：The semantics of UTop- query is based on the possible world model, and the greatest challenge in processing UTop- queries is the explosion of possible world space. In this direction, several optimized algorithms have been developed. However, uncertain databases are different in data distributions under different scoring functions, which has significant influence on the performance of the existing optimizing algorithms. In this paper, we propose two novel algorithms, MSSUTop- and quick MSSUTop-, for determining the minimum scan scope for UTop- query processing. This work is important because before UTop- query processing is started, users hope to know in advance how many and which tuples will be involved in UTop- query processing. Then, they can make a balance between result precision and processing cost. So, it should be the prerequisite for answering UTop- queries. MSSUTop- can achieve accurate results but is relatively more costly in time complexity. Oppositely, quick MSSUTop- can only achieve approximate results but performs better in time cost. We conduct comprehensive experiments to evaluate the performance of our proposed algorithms and analyze the relationship between the data distribution and the minimum scan scope of UTop- queries.
