Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data |
| |
Authors: | Xiang Lian Lei Chen |
| |
Affiliation: | (1) Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong, China |
| |
Abstract: | Reverse nearest neighbor (RNN) search is very crucial in many real applications. In particular, given a database and a query
object, an RNN query retrieves all the data objects in the database that have the query object as their nearest neighbors.
Often, due to limitation of measurement devices, environmental disturbance, or characteristics of applications (for example,
monitoring moving objects), data obtained from the real world are uncertain (imprecise). Therefore, previous approaches proposed
for answering an RNN query over exact (precise) database cannot be directly applied to the uncertain scenario. In this paper,
we re-define the RNN query in the context of uncertain databases, namely probabilistic reverse nearest neighbor (PRNN) query,
which obtains data objects with probabilities of being RNNs greater than or equal to a user-specified threshold. Since the
retrieval of a PRNN query requires accessing all the objects in the database, which is quite costly, we also propose an effective
pruning method, called geometric pruning (GP), that significantly reduces the PRNN search space yet without introducing any
false dismissals. Furthermore, we present an efficient PRNN query procedure that seamlessly integrates our pruning method.
Extensive experiments have demonstrated the efficiency and effectiveness of our proposed GP-based PRNN query processing approach,
under various experimental settings. |
| |
Keywords: | Probablistic reverse nearest neighbor Uncertain databases Geometric pruning |
本文献已被 SpringerLink 等数据库收录! |
|