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: GAO, Yunjun, YANG, Jiacheng, CHEN, Gang, ZHENG, Baihua, Shou, Lidan
格式: text
語言:English
出版: Institutional Knowledge at Singapore Management University 2011
主題:
在線閱讀:https://ink.library.smu.edu.sg/sis_research/1457
http://dx.doi.org/10.1145/2093973.2094000
標簽: 添加標簽
沒有標簽, 成為第一個標記此記錄!
機構: Singapore Management University
語言: 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