On Efficient Obstructed Reverse Nearest Neighbor Query Processing
In this paper, we study a new form of reverse nearest neighbor (RNN) queries, i.e., obstructed reverse nearest neighbor (ORNN) search. It considers the impact of obstacles on the distance between objects, which is ignored by the existing work on RNN retrieval. Given a data set P, an obstacle set O,...
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/1457 http://dx.doi.org/10.1145/2093973.2094000 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-2456 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-24562012-02-14T10:30:10Z On Efficient Obstructed Reverse Nearest Neighbor Query Processing GAO, Yunjun YANG, Jiacheng CHEN, Gang ZHENG, Baihua Shou, Lidan In this paper, we study a new form of reverse nearest neighbor (RNN) queries, i.e., obstructed reverse nearest neighbor (ORNN) search. It considers the impact of obstacles on the distance between objects, which is ignored by the existing work on RNN retrieval. Given a data set P, an obstacle set O, and a query point q in a 2D space, an ORNN query finds all the points/objects in P that have q as their nearest neighbor, according to the obstructed distance metric, i.e., the length of the shortest path between two points without crossing any obstacle. We formalize ORNN search, develop effective pruning heuristics (via introducing a novel boundary region concept), and propose efficient algorithms for ORNN query processing, assuming that both P and O are indexed by traditional data-partitioning indexes (e.g., R-trees). Extensive experiments demonstrate the effectiveness of our developed pruning heuristics and the performance of our proposed algorithms, using both real and synthetic datasets. 2011-11-01T07:00:00Z text https://ink.library.smu.edu.sg/sis_research/1457 info:doi/10.1145/2093973.2094000 http://dx.doi.org/10.1145/2093973.2094000 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 YANG, Jiacheng CHEN, Gang ZHENG, Baihua Shou, Lidan On Efficient Obstructed Reverse Nearest Neighbor Query Processing |
description |
In this paper, we study a new form of reverse nearest neighbor (RNN) queries, i.e., obstructed reverse nearest neighbor (ORNN) search. It considers the impact of obstacles on the distance between objects, which is ignored by the existing work on RNN retrieval. Given a data set P, an obstacle set O, and a query point q in a 2D space, an ORNN query finds all the points/objects in P that have q as their nearest neighbor, according to the obstructed distance metric, i.e., the length of the shortest path between two points without crossing any obstacle. We formalize ORNN search, develop effective pruning heuristics (via introducing a novel boundary region concept), and propose efficient algorithms for ORNN query processing, assuming that both P and O are indexed by traditional data-partitioning indexes (e.g., R-trees). Extensive experiments demonstrate the effectiveness of our developed pruning heuristics and the performance of our proposed algorithms, using both real and synthetic datasets. |
format |
text |
author |
GAO, Yunjun YANG, Jiacheng CHEN, Gang ZHENG, Baihua Shou, Lidan |
author_facet |
GAO, Yunjun YANG, Jiacheng CHEN, Gang ZHENG, Baihua Shou, Lidan |
author_sort |
GAO, Yunjun |
title |
On Efficient Obstructed Reverse Nearest Neighbor Query Processing |
title_short |
On Efficient Obstructed Reverse Nearest Neighbor Query Processing |
title_full |
On Efficient Obstructed Reverse Nearest Neighbor Query Processing |
title_fullStr |
On Efficient Obstructed Reverse Nearest Neighbor Query Processing |
title_full_unstemmed |
On Efficient Obstructed Reverse Nearest Neighbor Query Processing |
title_sort |
on efficient obstructed reverse nearest neighbor query processing |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2011 |
url |
https://ink.library.smu.edu.sg/sis_research/1457 http://dx.doi.org/10.1145/2093973.2094000 |
_version_ |
1770571154886492160 |