Top-$\boldsymbol{k}$ query processing over uncertain data in distributed environments |
| |
Authors: | Yongjiao Sun Ye Yuan Guoren Wang |
| |
Affiliation: | (1) Department of Computer and Information Science, NTNU, 7491 Trondheim, Norway;(2) Department of Informatics, AUEB, 10434 Athens, Greece |
| |
Abstract: | Although top-k queries over uncertain data in centralized databases have been studied widely in recent years, it is still a challenging
issue in distributed environments. In distributed environments, such as Peer-to-Peer (P2P) systems and sensor networks, there
exists an inherent uncertainty on the data objects due to imprecise measurements and network delays. Therefore, it is necessary
to study the problem of how to efficiently retrieve top-k uncertain data objects over distributed environments with minimum network overhead. In this paper, we propose a novel approach
of processing uncertain top-k queries in large-scale P2P networks, where datasets are horizontally partitioned over peers. In our approach, each peer constructs
an Uncertain Quad-Tree (UQ-Tree) index for its local uncertain data, while the P2P network constructs a global index by summarizing the local indexes. Based on the global index, we propose a spatial-pruning algorithm to reduce communication costs and a distributed-pruning algorithm to reduce computation costs. Extensive experiments are conducted to verify the effectiveness and efficiency of
the proposed methods in terms of communication costs and response time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|