Continuous All k-Nearest-Neighbor Querying in Smartphone Networks
Authors:
- Georgios ChatzimilioudisGCGeorgios Chatzimilioudis
- Demetrios Zeinalipour-YaztiDZDemetrios Zeinalipour-Yazti
- Wang-Chien LeeWLWang-Chien Lee
- Marios D. DikaiakosMDMarios D. Dikaiakos
- 1 July 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 79-88
Abstract
Consider a centralized query operator that identifies to every smartphone 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, allowing gamers and 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.Keywords
This publication has 24 references indexed in Scilit:
- Efficient proximity detection among mobile users via self-tuning policiesProceedings of the VLDB Endowment, 2010
- Nearest neighbor search with strong location privacyProceedings of the VLDB Endowment, 2010
- Vehicular mobility simulation with VanetMobiSimSIMULATION, 2009
- Efficient Continuous K-Nearest Neighbor Query Processing over Moving Objects with Uncertain Speed and DirectionLecture Notes in Computer Science, 2008
- Algorithms for Nearest Neighbor Search on Moving Object TrajectoriesGeoInformatica, 2007
- Preserving User Location Privacy in Mobile Data Management Infrastructures2006
- Continuous K-Nearest Neighbor Queries for Continuously Moving Points with Updates2003
- Nearest Neighbor Queries in a Mobile Environment1999
- Constructing Euclidean minimum spanning trees and all nearest neighbors on reconfigurable meshesIEEE Transactions on Parallel and Distributed Systems, 1996
- AnO(n logn) algorithm for the all-nearest-neighbors ProblemDiscrete & Computational Geometry, 1989