k‐nearest reliable neighbor search in crowdsourced LBSs

• Published in: International journal of communication systems 2021-01, Vol.34 (2), p.n/a
• Main Authors: Jang, Hong‐Jun, Kim, Byoungwook, Jung, Soon‐Young
• Format: Article
• Language: English
• Subjects: Algorithms; Crowdsourcing; Datasets; k‐nearest reliable neighbor query; Location based services; nearest neighbor query; Queries; Spatial data; spatial databases; spatio‐temporal databases
• ISSN: 1074-5351; 1099-1131
• DOI: 10.1002/dac.4097

Summary 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. 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. 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. Our experimental results show the efficiency of our proposed methods.