Visible reverse k-Nearest neighbor queries

Yunjun Gao, Baihua Zheng, Gencai Chen, Wang Chien Lee, Ken C K Lee, Qing Li

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

30 Citations (Scopus)

Abstract

Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, data mining, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings, blindages, etc.), and their presence may affect the visibility/distance between two objects. In this paper, we introduce a novel variant of RNN queries, namely visible reverse nearest neighbor (VRNN) search, which considers the obstacle influence on the visibility of objects. Given a data set P, an obstacle set O, and a query point q, a VRNN query retrieves the points in P that have q as their nearest neighbor and are visible to q. We propose an efficient algorithm for VRNN query processing, assuming that both P and O are indexed by R-trees. Our method does not require any pre-processing, and employs half-plane property and visibility check to prune the search space.

Original languageEnglish
Title of host publicationProceedings - 25th IEEE International Conference on Data Engineering, ICDE 2009
Pages1203-1206
Number of pages4
DOIs
Publication statusPublished - 8 Jul 2009
Externally publishedYes
Event25th IEEE International Conference on Data Engineering, ICDE 2009 - Shanghai, China
Duration: 29 Mar 20092 Apr 2009

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Conference

Conference25th IEEE International Conference on Data Engineering, ICDE 2009
Country/TerritoryChina
CityShanghai
Period29/03/092/04/09

ASJC Scopus subject areas

  • Information Systems
  • Signal Processing
  • Software

Cite this