Continuous Nearest Neighbor Search in the Presence of Obstacles
Despite the ubiquity of physical obstacles (e.g., buildings, hills, and blindages, etc.) in the real world, most of spatial queries ignore the obstacles. In this article, we study a novel form of continuous nearest-neighbor queries in the presence of obstacles, namely continuous obstructed nearest-n...
Saved in:
Main Authors: | , , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2011
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/1407 https://ink.library.smu.edu.sg/context/sis_research/article/2406/viewcontent/CONN_TODS_2010.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-2406 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-24062018-07-13T02:54:07Z Continuous Nearest Neighbor Search in the Presence of Obstacles GAO, Yunjun ZHENG, Baihua CHEN, Gang CHEN, Chun LI, Qing Despite the ubiquity of physical obstacles (e.g., buildings, hills, and blindages, etc.) in the real world, most of spatial queries ignore the obstacles. In this article, we study a novel form of continuous nearest-neighbor queries in the presence of obstacles, namely continuous obstructed nearest-neighbor (CONN) search, which considers the impact of obstacles on the distance between objects. Given a data setP, an obstacle set O, and a query line segment q, in a two-dimensional space, a CONN query retrieves the nearest neighbor p ∈ P of each point p′ on q according to the obstructed distance, the shortest path between p and p′ without crossing any obstacle in O. We formalize CONN search, analyze its unique properties, and develop algorithms for exact CONN query-processing assuming that both P and O are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle CONN retrieval by performing a single query for the entire query line segment, and only process the data points and obstacles relevant to the final query result via a novel concept of control points and an efficient quadratic-based split point computation approach. Then, we extend our techniques to handle variations of CONN queries, including (1) continuous obstructed k nearest neighbor (COkNN) search which, based on obstructed distances, finds the k(≥ 1) nearest neighbors (NNs) to every point along q; and (2) trajectory obstructed k nearest-neighbor (TOkNN) search, which, according to obstructed distances, returns the k NNs for each point on an arbitrary trajectory (consisting of several consecutive line segments). Finally, we explore approximate COkNN (ACOkNN) retrieval. Extensive experiments with both real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings. 2011-05-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/1407 info:doi/10.1145/1966385.1966387 https://ink.library.smu.edu.sg/context/sis_research/article/2406/viewcontent/CONN_TODS_2010.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 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 |
Databases and Information Systems Numerical Analysis and Scientific Computing |
spellingShingle |
Databases and Information Systems Numerical Analysis and Scientific Computing GAO, Yunjun ZHENG, Baihua CHEN, Gang CHEN, Chun LI, Qing Continuous Nearest Neighbor Search in the Presence of Obstacles |
description |
Despite the ubiquity of physical obstacles (e.g., buildings, hills, and blindages, etc.) in the real world, most of spatial queries ignore the obstacles. In this article, we study a novel form of continuous nearest-neighbor queries in the presence of obstacles, namely continuous obstructed nearest-neighbor (CONN) search, which considers the impact of obstacles on the distance between objects. Given a data setP, an obstacle set O, and a query line segment q, in a two-dimensional space, a CONN query retrieves the nearest neighbor p ∈ P of each point p′ on q according to the obstructed distance, the shortest path between p and p′ without crossing any obstacle in O. We formalize CONN search, analyze its unique properties, and develop algorithms for exact CONN query-processing assuming that both P and O are indexed by conventional data-partitioning indices (e.g., R-trees). Our methods tackle CONN retrieval by performing a single query for the entire query line segment, and only process the data points and obstacles relevant to the final query result via a novel concept of control points and an efficient quadratic-based split point computation approach. Then, we extend our techniques to handle variations of CONN queries, including (1) continuous obstructed k nearest neighbor (COkNN) search which, based on obstructed distances, finds the k(≥ 1) nearest neighbors (NNs) to every point along q; and (2) trajectory obstructed k nearest-neighbor (TOkNN) search, which, according to obstructed distances, returns the k NNs for each point on an arbitrary trajectory (consisting of several consecutive line segments). Finally, we explore approximate COkNN (ACOkNN) retrieval. Extensive experiments with both real and synthetic datasets demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings. |
format |
text |
author |
GAO, Yunjun ZHENG, Baihua CHEN, Gang CHEN, Chun LI, Qing |
author_facet |
GAO, Yunjun ZHENG, Baihua CHEN, Gang CHEN, Chun LI, Qing |
author_sort |
GAO, Yunjun |
title |
Continuous Nearest Neighbor Search in the Presence of Obstacles |
title_short |
Continuous Nearest Neighbor Search in the Presence of Obstacles |
title_full |
Continuous Nearest Neighbor Search in the Presence of Obstacles |
title_fullStr |
Continuous Nearest Neighbor Search in the Presence of Obstacles |
title_full_unstemmed |
Continuous Nearest Neighbor Search in the Presence of Obstacles |
title_sort |
continuous nearest neighbor search in the presence of obstacles |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2011 |
url |
https://ink.library.smu.edu.sg/sis_research/1407 https://ink.library.smu.edu.sg/context/sis_research/article/2406/viewcontent/CONN_TODS_2010.pdf |
_version_ |
1770571111061258240 |