Approximate Evaluation of Range Nearest Neighbor Queries with Quality Guarantee

Download Now Date Added: Sep 2009
Format: PDF

The range Nearest-Neighbor (NN) query is an important query type in location-based services, as it can be applied to the case that an NN query has a spatial region, instead of a location point, as the query location. Examples of the applications of range NN queries include uncertain locations and privacy-preserving queries. Given a set of objects, the range NN answer is a set of objects that includes the nearest object(s) to every point in a given spatial region. The answer set size would significantly increase as the spatial region gets larger. Unfortunately, mobile users in wireless environments suffer from scarce bandwidth and low-quality communication, transmitting a large answer set from a database server to the user would pose very high response time.