MSSUTop-k: Determining the Minimum Scan Scope for UTop-k Query over Uncertain Data

Zhibin Zhao, Lan Yao, Ge Yu, Yubin Bao and Zhengbing Ma

International Journal of Distributed Sensor Networks, 2015, vol. 11, issue 10, 359137

Abstract: The semantics of UTop- k query is based on the possible world model, and the greatest challenge in processing UTop- k 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- k and quick MSSUTop- k , for determining the minimum scan scope for UTop- k query processing. This work is important because before UTop- k query processing is started, users hope to know in advance how many and which tuples will be involved in UTop- k query processing. Then, they can make a balance between result precision and processing cost. So, it should be the prerequisite for answering UTop- k queries. MSSUTop- k can achieve accurate results but is relatively more costly in time complexity. Oppositely, quick MSSUTop- k 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- k queries.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1155/2015/359137 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:intdis:v:11:y:2015:i:10:p:359137

DOI: 10.1155/2015/359137

Access Statistics for this article

More articles in International Journal of Distributed Sensor Networks
Bibliographic data for series maintained by SAGE Publications ().