Moving range k nearest neighbor queries with quality guarantee over uncertain moving objects

To avoid traffic accidents, drivers must constantly be aware of nearby vehicles. Unfortunately, nearby vehicles often go unnoticed because of various obstacles such as other vehicles, buildings, or poor weather. In this paper, we study Moving range k-nearest neighbor (MRkNN) queries as a tool for continuously monitoring nearby moving objects. A simple approach to processing MRkNN queries is to have each object periodically broadcast information regarding its movements (i.e., location and velocity at a particular time) to other objects. However, this simple technique cannot be used to process MRkNN queries owing to the limited network bandwidth in mobile peer-to-peer environments. Therefore, we address this bandwidth limitation by proposing a probabilistic algorithm, called MINT, for MovIng range k-NN queries with qualiTy guarantee over uncertain moving objects. MINT provides users with approximate answers with a quality guarantee, rather than exact answers, with near optimal communication costs. Using a series of simulations, we demonstrate the efficiency and efficacy of MINT in evaluating MRkNN queries with a quality guarantee.