k-nearest reliable neighbor search in crowdsourced LBSs

Abstract

To improve the quality of spatial information in a location-based services (LBS), crowdsourced LBS (cLBS) applications that receive additional information such as the visit time of static spatial objects from users have appeared. In this paper, we propose a new type of nearest neighbor (NN) query called the k-nearest reliable neighbor (kNRN) query, which searches for objects that are likely to exist. Suppose that in cLBSs, the user wants to find a restaurant that is likely to exist and is close to the user. In such a case, a kNRN query is highly recommended. In this paper, we formally define a data model in cLBSs and define reliable objects and a kNRN problem. As a brute-force approach to this problem in a massive dataset that has large computational and I/O costs, we propose a 3DR-tree-based baseline algorithm, 2DR-tree-based incremental algorithm, and an a3DR-tree-based branch-and-bound algorithm for kNRN queries. A performance study is conducted on both synthetic and real datasets. Our experimental results show the efficiency of our proposed methods.