Continuous Visible Nearest Neighbour Queries
In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q, a CVNN query returns a set of (p, R) tuples such that p ? P is the nearest neighbor (NN) to every point r a...
Saved in:
Main Authors: | , , , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2009
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/311 https://ink.library.smu.edu.sg/context/sis_research/article/1310/viewcontent/1516360.1516378.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-1310 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-13102024-01-04T01:47:20Z Continuous Visible Nearest Neighbour Queries GAO, Yunjun ZHENG, Baihua LEE, Wang-Chien CHEN, Gencai In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q, a CVNN query returns a set of (p, R) tuples such that p ? P is the nearest neighbor (NN) to every point r along the interval R ? q as well as p is visible to r. Note that p may be NULL, meaning that all points in P are invisible to all points in R, due to the obstruction of some obstacles in O. In this paper, we formulate the problem and propose efficient algorithms for CVNN query processing, assuming that both P and O are indexed by R-trees. In addition, we extend our techniques to several variations of the CVNN query. Extensive experiments verify the efficiency and effectiveness of our proposed algorithms using both real and synthetic datasets. 2009-03-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/311 info:doi/10.1145/1516360.1516378 https://ink.library.smu.edu.sg/context/sis_research/article/1310/viewcontent/1516360.1516378.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 LEE, Wang-Chien CHEN, Gencai Continuous Visible Nearest Neighbour Queries |
description |
In this paper, we identify and solve a new type of spatial queries, called continuous visible nearest neighbor (CVNN) search. Given a data set P, an obstacle set O, and a query line segment q, a CVNN query returns a set of (p, R) tuples such that p ? P is the nearest neighbor (NN) to every point r along the interval R ? q as well as p is visible to r. Note that p may be NULL, meaning that all points in P are invisible to all points in R, due to the obstruction of some obstacles in O. In this paper, we formulate the problem and propose efficient algorithms for CVNN query processing, assuming that both P and O are indexed by R-trees. In addition, we extend our techniques to several variations of the CVNN query. Extensive experiments verify the efficiency and effectiveness of our proposed algorithms using both real and synthetic datasets. |
format |
text |
author |
GAO, Yunjun ZHENG, Baihua LEE, Wang-Chien CHEN, Gencai |
author_facet |
GAO, Yunjun ZHENG, Baihua LEE, Wang-Chien CHEN, Gencai |
author_sort |
GAO, Yunjun |
title |
Continuous Visible Nearest Neighbour Queries |
title_short |
Continuous Visible Nearest Neighbour Queries |
title_full |
Continuous Visible Nearest Neighbour Queries |
title_fullStr |
Continuous Visible Nearest Neighbour Queries |
title_full_unstemmed |
Continuous Visible Nearest Neighbour Queries |
title_sort |
continuous visible nearest neighbour queries |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2009 |
url |
https://ink.library.smu.edu.sg/sis_research/311 https://ink.library.smu.edu.sg/context/sis_research/article/1310/viewcontent/1516360.1516378.pdf |
_version_ |
1787136855129456640 |