The Islands Approach to Nearest Neighbor Querying in Spatial Networks

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

53 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

Information management
Program processors

Cite this

Huang, X., Jensen, C. S., & Saltenis, S. (2005). The Islands Approach to Nearest Neighbor Querying in Spatial Networks. In C. B. Medeiros, M. Egenhofer, & E. Bertino (Eds.), Advances in Spatial and Temporal Databases: Proceedings of 9th International Symposium, SSTD 2005, Angra dos Reis, Brazil, August 22-24, 2005 (3633 ed., pp. 73-90). IEEE Computer Society Press. Lecture Notes in Computer Science, No. 3633 https://doi.org/10.1007/11535331_5
Huang, Xuegang ; Jensen, Christian Søndergaard ; Saltenis, Simonas. / The Islands Approach to Nearest Neighbor Querying in Spatial Networks. Advances in Spatial and Temporal Databases: Proceedings of 9th International Symposium, SSTD 2005, Angra dos Reis, Brazil, August 22-24, 2005. editor / Claudia Bauzer Medeiros ; Max Egenhofer ; Elisa Bertino. 3633. ed. IEEE Computer Society Press, 2005. pp. 73-90 (Lecture Notes in Computer Science; No. 3633).
@inproceedings{311fe0e031c611db8de7000ea68e967b,
title = "The Islands Approach to Nearest Neighbor Querying in Spatial Networks",
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.",
author = "Xuegang Huang and Jensen, {Christian S{\o}ndergaard} and Simonas Saltenis",
year = "2005",
doi = "10.1007/11535331_5",
language = "English",
series = "Lecture Notes in Computer Science",
publisher = "IEEE Computer Society Press",
number = "3633",
pages = "73--90",
editor = "Medeiros, {Claudia Bauzer} and Max Egenhofer and Elisa Bertino",
booktitle = "Advances in Spatial and Temporal Databases",
address = "United States",
edition = "3633",

}

Huang, X, Jensen, CS & Saltenis, S 2005, The Islands Approach to Nearest Neighbor Querying in Spatial Networks. in CB Medeiros, M Egenhofer & E Bertino (eds), Advances in Spatial and Temporal Databases: Proceedings of 9th International Symposium, SSTD 2005, Angra dos Reis, Brazil, August 22-24, 2005. 3633 edn, IEEE Computer Society Press, Lecture Notes in Computer Science, no. 3633, pp. 73-90, International Symposium on Spatial and Temporal Databases, Angra dos Reis, Brazil, 22/08/2005. https://doi.org/10.1007/11535331_5

The Islands Approach to Nearest Neighbor Querying in Spatial Networks. / Huang, Xuegang; Jensen, Christian Søndergaard; Saltenis, Simonas.

Advances in Spatial and Temporal Databases: Proceedings of 9th International Symposium, SSTD 2005, Angra dos Reis, Brazil, August 22-24, 2005. ed. / Claudia Bauzer Medeiros; Max Egenhofer; Elisa Bertino. 3633. ed. IEEE Computer Society Press, 2005. p. 73-90 (Lecture Notes in Computer Science; No. 3633).

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

TY - GEN

T1 - The Islands Approach to Nearest Neighbor Querying in Spatial Networks

AU - Huang, Xuegang

AU - Jensen, Christian Søndergaard

AU - Saltenis, Simonas

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

U2 - 10.1007/11535331_5

DO - 10.1007/11535331_5

M3 - Article in proceeding

T3 - Lecture Notes in Computer Science

SP - 73

EP - 90

BT - Advances in Spatial and Temporal Databases

A2 - Medeiros, Claudia Bauzer

A2 - Egenhofer, Max

A2 - Bertino, Elisa

PB - IEEE Computer Society Press

ER -

Huang X, Jensen CS, Saltenis S. The Islands Approach to Nearest Neighbor Querying in Spatial Networks. In Medeiros CB, Egenhofer M, Bertino E, editors, Advances in Spatial and Temporal Databases: Proceedings of 9th International Symposium, SSTD 2005, Angra dos Reis, Brazil, August 22-24, 2005. 3633 ed. IEEE Computer Society Press. 2005. p. 73-90. (Lecture Notes in Computer Science; No. 3633). https://doi.org/10.1007/11535331_5