Nearest surrounder searching in mobile computing environments

Abstract

The key issue in mobile computing environments (MCEs) is how to relieve communication congestion and provide accurate information through location-based services (LBSs). The nearest surrounder (NS) query, used to find all visible objects around a given location, is a type of spatial query that suggests broad application base in LBS domain. However, because existing works for NS query only take into account static query points, the application of the NS query is limited to various LBSs in MCEs requiring frequent location updates. Motivated by this limitation, this paper introduces the continuous nearest surrounder (CNS) query, which uses a decentralized system framework to continuously maintain updated query results in MCEs. In this framework, the LBS server executes an initial NS query to prepare a region, termed non-provoked polygon (NPP), defines a set of visible objects that cannot be changed. Conversely, a client caches the NPP and does not update request unless it leaves its NPP. We performed extensive experiments using synthetic and real datasets with various data cardinality, and query mobility to validate the accurate performance of the proposed strategy. The results show that the CNS algorithm outperforms NS, in terms of computation and communication costs as well as scalability.Copyright (c) 2012 John Wiley & Sons, Ltd.