Local network Voronoi diagrams
AuthorNutanong, S; Tanin, E; Ali, ME; Kulik, L
Source Title18th SIGSPATIAL International Conference on Advances in Geographic Information Systems
AffiliationComputer Science and Software Engineering
Document TypeConference Paper
CitationsNutanong, S., Tanin, E., Ali, M. E. & Kulik, L. (2010). Local network Voronoi diagrams. 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp.109-118. ACM. https://doi.org/10.1145/1869790.1869808.
Access StatusThis item is currently not available from this repository
ACM International Conference on Advances in Geographic Information Systems (SIGSPATIAL)
Continuous queries in road networks have gained significant research interests due to advances in GIS and mobile computing. Consider the following scenario: "A driver uses a networked GPS navigator to monitor five nearest gas stations in a road network." The main challenge of processing such a moving query is how to efficiently monitor network distances of the k nearest and possible resultant objects. To enable result monitoring in real-time, researchers have devised techniques which utilize precomputed distances and results, e.g., the network Voronoi diagram (NVD). However, the main drawback of preprocessing is that it requires access to all data objects and network nodes, which means that it is not suitable for large datasets in many real life situations. The best existing method to monitor kNN results without precomputation relies on executions of snapshot queries at network nodes encountered by the query point. This method results in repetitive distance evaluation over the same or similar sets of nodes. In this paper, we propose a method called the local network Voronoi diagram (LNVD) to compute query answers for a small area around the query point. As a result, our method requires neither precomputation nor distance evaluation at every intersection. According to our extensive analysis and experimental results, our method significantly outperforms the best existing method in terms of data access and computation costs.
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References