Query Processing in Spatial Databases Containing Obstacles

Despite the existence of obstacles in many database applications, traditional spatial query processing assumes that points in space are directly reachable and utilizes the Euclidean distance metric. In this paper, we study spatial queries in the presence of obstacles, where the obstructed distance b...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHANG, Jun, Papadias, Dimitris, Mouratidis, Kyriakos, ZHU, Manli
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2005
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/174
https://ink.library.smu.edu.sg/context/sis_research/article/1173/viewcontent/IJGIS05_SODB.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-1173
record_format dspace
spelling sg-smu-ink.sis_research-11732016-04-29T06:02:09Z Query Processing in Spatial Databases Containing Obstacles ZHANG, Jun Papadias, Dimitris Mouratidis, Kyriakos ZHU, Manli Despite the existence of obstacles in many database applications, traditional spatial query processing assumes that points in space are directly reachable and utilizes the Euclidean distance metric. In this paper, we study spatial queries in the presence of obstacles, where the obstructed distance between two points is defined as the length of the shortest path that connects them without crossing any obstacles. We propose efficient algorithms for the most important query types, namely, range search, nearest neighbours, e-distance joins, closest pairs and distance semi-joins, assuming that both data objects and obstacles are indexed by R-trees. The effectiveness of the proposed solutions is verified through extensive experiments. 2005-11-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/174 info:doi/10.1080/13658810500286935 https://ink.library.smu.edu.sg/context/sis_research/article/1173/viewcontent/IJGIS05_SODB.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University spatial databases query processing visibility graph Databases and Information Systems Numerical Analysis and Scientific Computing
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic spatial databases
query processing
visibility graph
Databases and Information Systems
Numerical Analysis and Scientific Computing
spellingShingle spatial databases
query processing
visibility graph
Databases and Information Systems
Numerical Analysis and Scientific Computing
ZHANG, Jun
Papadias, Dimitris
Mouratidis, Kyriakos
ZHU, Manli
Query Processing in Spatial Databases Containing Obstacles
description Despite the existence of obstacles in many database applications, traditional spatial query processing assumes that points in space are directly reachable and utilizes the Euclidean distance metric. In this paper, we study spatial queries in the presence of obstacles, where the obstructed distance between two points is defined as the length of the shortest path that connects them without crossing any obstacles. We propose efficient algorithms for the most important query types, namely, range search, nearest neighbours, e-distance joins, closest pairs and distance semi-joins, assuming that both data objects and obstacles are indexed by R-trees. The effectiveness of the proposed solutions is verified through extensive experiments.
format text
author ZHANG, Jun
Papadias, Dimitris
Mouratidis, Kyriakos
ZHU, Manli
author_facet ZHANG, Jun
Papadias, Dimitris
Mouratidis, Kyriakos
ZHU, Manli
author_sort ZHANG, Jun
title Query Processing in Spatial Databases Containing Obstacles
title_short Query Processing in Spatial Databases Containing Obstacles
title_full Query Processing in Spatial Databases Containing Obstacles
title_fullStr Query Processing in Spatial Databases Containing Obstacles
title_full_unstemmed Query Processing in Spatial Databases Containing Obstacles
title_sort query processing in spatial databases containing obstacles
publisher Institutional Knowledge at Singapore Management University
publishDate 2005
url https://ink.library.smu.edu.sg/sis_research/174
https://ink.library.smu.edu.sg/context/sis_research/article/1173/viewcontent/IJGIS05_SODB.pdf
_version_ 1770568910417952768