Show simple item record

dc.contributor.authorNutanong, S
dc.contributor.authorTanin, E
dc.contributor.authorAli, ME
dc.contributor.authorKulik, L
dc.identifier.citationNutanong, 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.
dc.descriptionACM International Conference on Advances in Geographic Information Systems (SIGSPATIAL)
dc.description.abstractContinuous 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.
dc.sourceProceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems
dc.subjectInformation Systems
dc.titleLocal network Voronoi diagrams
dc.typeConference Paper
melbourne.peerreviewPeer Reviewed
melbourne.affiliationThe University of Melbourne
melbourne.affiliation.departmentComputer Science and Software Engineering
melbourne.source.title18th SIGSPATIAL International Conference on Advances in Geographic Information Systems
melbourne.contributor.authorNUTANONG, SARANA
melbourne.contributor.authorTanin, Egemen
melbourne.contributor.authorKulik, Lars
melbourne.contributor.authorALI, MOHAMMED
melbourne.event.locationNew York
melbourne.accessrightsThis item is currently not available from this repository

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record