Continuous all k-nearest-neighbor querying in smartphone networks

Abstract

Consider a centralized query operator that identifies to every smart phone user its k geographically nearest neighbors at all times, a query we coin Continuous All k-Nearest Neighbor (CAkNN). Such an operator could be utilized to enhance public emergency services, allowing users to send SOS beacons out to the closest rescuers and allowing gamers or social networking users to establish ad-hoc overlay communication infrastructures, in order to carry out complex interactions. In this paper, we study the problem of efficiently processing a CAkNN query in a cellular or WiFi network, both of which are ubiquitous. We introduce an algorithm, coined Proximity, which answers CAkNN queries in O(n(k+λ)) time, where n denotes the number of users and λ a network-specific parameter (λ ≪ n). Proximity does not require any additional infrastructure or specialized hardware and its efficiency is mainly attributed to a smart search space sharing technique we introduce. Its implementation is based on a novel data structure, coined k+-heap, which achieves constant O(1) look-up time and logarithmic O(log(k*λ .)) insertion/update time. Proximity, being parameter-free, performs efficiently in the face of high mobility and skewed distribution of users (e.g., the service works equally well in downtown, suburban, or rural areas). We have evaluated Proximity using mobility traces from two sources and concluded that our approach performs at least one order of magnitude faster than adapted existing work. © 2012 IEEE.