Answering Closest-Pair Nearest Neighbor Using Voronoi Diagram For LocNNation Dependent Information System In Mobile Environment

摘要

Location dependent information system (LDIS) has received more and more attention recently with the wide availability of mobile devices (smart phones, tablet, notebook, iPad etc.). Location dependent queries (LDQ) such as range query, window query and nearest neighbor (NN) query are gaining popularity. One of the most important LDQ is the closest pair nearest neighbor (CPNN) query, which is to find the closest pair of objects among the two data sets close to the user's current location where the query is issued. User may be interested in finding the closest restaurant and medical store or the closest supermarket and parking, etc. Users may request successive NN queries for theatre and restaurant. In previous works, CPNN query for LDIS, considers two items of the closest pair from two different points of interest (POI) data set indexed by R-trees. In this work, we address the closest pair nearest neighbor query using the Voronoi index structure and cache management strategies. The experiments conducted on our proposed cache strategies show an increase in cache hits which in turn help reduce communication costs and support rapid spatial query processing.