The Islands Approach to Nearest Neighbor Querying in Spatial Networks

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

52 Citations (Scopus)

Abstract

Much research has recently been devoted to the data management foundations of location-based mobile services. In one important scenario, the service users are constrained to a transportation network. As a result, query processing in spatial road networks is of interest. We propose a versatile approach to k nearest neighbor computation in spatial networks, termed the Islands approach. By offering flexible yet simple means of balancing re-computation and pre-computation, this approach is able to manage the trade-off between query and update performance. The result is a single, efficient, and versatile approach to k nearest neighbor computation that obviates the need for using several k nearest neighbor approaches for supporting a single service scenario. The experimental comparison with the existing techniques uses real-world road network data and considers both I/O and CPU performance, for both queries and updates.
Original languageEnglish
Title of host publicationAdvances in Spatial and Temporal Databases : Proceedings of 9th International Symposium, SSTD 2005, Angra dos Reis, Brazil, August 22-24, 2005
EditorsClaudia Bauzer Medeiros, Max Egenhofer, Elisa Bertino
Number of pages18
PublisherIEEE Computer Society Press
Publication date2005
Edition3633
Pages73-90
ISBN (Electronic)3540281274
DOIs
Publication statusPublished - 2005
EventInternational Symposium on Spatial and Temporal Databases - Angra dos Reis, Brazil
Duration: 22 Aug 200524 Aug 2005
Conference number: 9th

Conference

ConferenceInternational Symposium on Spatial and Temporal Databases
Number9th
CountryBrazil
CityAngra dos Reis
Period22/08/200524/08/2005
SeriesLecture Notes in Computer Science
Number3633

Fingerprint Dive into the research topics of 'The Islands Approach to Nearest Neighbor Querying in Spatial Networks'. Together they form a unique fingerprint.

Cite this